C语言二叉树的遍历方法怎么实现

# C语言二叉树的遍历方法怎么实现

二叉树是数据结构中最基础且重要的非线性结构，其遍历操作是算法设计的核心内容。本文将详细讲解C语言中实现二叉树前序、中序、后序及层次遍历的完整方法，包含代码实现、算法原理和实际应用场景。

## 一、二叉树的基本结构与创建

### 1.1 二叉树节点定义
```c
typedef struct TreeNode {
    int data;               // 节点数据域
    struct TreeNode *left;  // 左子树指针
    struct TreeNode *right; // 右子树指针
} TreeNode;

1.2 创建二叉树节点

TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

二、递归遍历实现

2.1 前序遍历（Preorder）

顺序：根节点 → 左子树 → 右子树
应用场景：复制二叉树、表达式树的前缀表示

void preOrderRecursive(TreeNode* root) {
    if (root == NULL) return;
    
    printf("%d ", root->data);  // 访问根节点
    preOrderRecursive(root->left);
    preOrderRecursive(root->right);
}

2.2 中序遍历（Inorder）

顺序：左子树 → 根节点 → 右子树
应用场景：二叉搜索树的有序输出

void inOrderRecursive(TreeNode* root) {
    if (root == NULL) return;
    
    inOrderRecursive(root->left);
    printf("%d ", root->data);  // 访问根节点
    inOrderRecursive(root->right);
}

2.3 后序遍历（Postorder）

顺序：左子树 → 右子树 → 根节点
应用场景：释放二叉树内存、表达式树的后缀表示

void postOrderRecursive(TreeNode* root) {
    if (root == NULL) return;
    
    postOrderRecursive(root->left);
    postOrderRecursive(root->right);
    printf("%d ", root->data);  // 最后访问根节点
}

三、非递归遍历实现（使用栈）

3.1 前序遍历非递归版

#include <stdlib.h>
#define MAX_SIZE 100

void preOrderIterative(TreeNode* root) {
    if (root == NULL) return;
    
    TreeNode* stack[MAX_SIZE];
    int top = -1;
    stack[++top] = root;
    
    while (top >= 0) {
        TreeNode* node = stack[top--];
        printf("%d ", node->data);
        
        // 右子节点先入栈（后出）
        if (node->right != NULL)
            stack[++top] = node->right;
        // 左子节点后入栈（先出）
        if (node->left != NULL)
            stack[++top] = node->left;
    }
}

3.2 中序遍历非递归版

void inOrderIterative(TreeNode* root) {
    TreeNode* stack[MAX_SIZE];
    int top = -1;
    TreeNode* curr = root;
    
    while (curr != NULL || top >= 0) {
        // 遍历到最左节点
        while (curr != NULL) {
            stack[++top] = curr;
            curr = curr->left;
        }
        
        curr = stack[top--];
        printf("%d ", curr->data);
        curr = curr->right;
    }
}

3.3 后序遍历非递归版（双栈法）

void postOrderIterative(TreeNode* root) {
    if (root == NULL) return;
    
    TreeNode* stack1[MAX_SIZE];
    TreeNode* stack2[MAX_SIZE];
    int top1 = -1, top2 = -1;
    
    stack1[++top1] = root;
    while (top1 >= 0) {
        TreeNode* node = stack1[top1--];
        stack2[++top2] = node;
        
        if (node->left != NULL)
            stack1[++top1] = node->left;
        if (node->right != NULL)
            stack1[++top1] = node->right;
    }
    
    // 输出stack2中的逆序结果
    while (top2 >= 0) {
        printf("%d ", stack2[top2--]->data);
    }
}

四、层次遍历（队列实现）

特点：按层级从上到下、从左到右访问
应用场景：计算树的高度、查找某层节点

#include <stdbool.h>
#define QUEUE_SIZE 100

typedef struct {
    TreeNode* data[QUEUE_SIZE];
    int front, rear;
} Queue;

void initQueue(Queue* q) {
    q->front = q->rear = 0;
}

bool isEmpty(Queue* q) {
    return q->front == q->rear;
}

bool enqueue(Queue* q, TreeNode* node) {
    if ((q->rear + 1) % QUEUE_SIZE == q->front)
        return false; // 队列满
    q->data[q->rear] = node;
    q->rear = (q->rear + 1) % QUEUE_SIZE;
    return true;
}

TreeNode* dequeue(Queue* q) {
    if (isEmpty(q)) return NULL;
    TreeNode* node = q->data[q->front];
    q->front = (q->front + 1) % QUEUE_SIZE;
    return node;
}

void levelOrder(TreeNode* root) {
    if (root == NULL) return;
    
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    
    while (!isEmpty(&q)) {
        TreeNode* node = dequeue(&q);
        printf("%d ", node->data);
        
        if (node->left != NULL)
            enqueue(&q, node->left);
        if (node->right != NULL)
            enqueue(&q, node->right);
    }
}

五、完整示例代码

#include <stdio.h>
#include <stdlib.h>

// （此处插入前述所有代码片段）

int main() {
    /* 构建测试二叉树：
          1
        /   \
       2     3
      / \   /
     4   5 6
    */
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    
    printf("递归前序遍历: ");
    preOrderRecursive(root);
    
    printf("\n非递归中序遍历: ");
    inOrderIterative(root);
    
    printf("\n栈实现后序遍历: ");
    postOrderIterative(root);
    
    printf("\n层次遍历结果: ");
    levelOrder(root);
    
    return 0;
}

六、遍历方法对比

七、常见问题解答

Q1：如何选择递归还是非递归实现？
- 递归代码简洁但可能栈溢出
- 非递归效率更高，适合深度大的树

Q2：Morris遍历如何实现？
Morris遍历通过修改树结构实现O(1)空间复杂度：

// 中序Morris遍历示例
void inOrderMorris(TreeNode* root) {
    TreeNode *curr = root, *pre;
    while (curr != NULL) {
        if (curr->left == NULL) {
            printf("%d ", curr->data);
            curr = curr->right;
        } else {
            pre = curr->left;
            while (pre->right != NULL && pre->right != curr)
                pre = pre->right;
                
            if (pre->right == NULL) {
                pre->right = curr;
                curr = curr->left;
            } else {
                pre->right = NULL;
                printf("%d ", curr->data);
                curr = curr->right;
            }
        }
    }
}

通过掌握这些遍历方法，您将能够高效处理二叉树相关问题。建议读者手动模拟各算法执行过程以加深理解。 “`

（全文约2350字，包含代码示例、复杂度分析和实际应用说明）

亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>