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; } 

六、遍历方法对比

遍历方式	时间复杂度	空间复杂度	特点
前序递归	O(n)	O(h)	栈深度=树高度
中序非递归	O(n)	O(n)	需要显式维护栈
层次遍历	O(n)	O(w)	w为树的最大宽度

七、常见问题解答

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字，包含代码示例、复杂度分析和实际应用说明）