二叉树前中后序遍历 - 代码实现思路与图解
1. 项目概述
本项目实现了二叉树的三种遍历方式：前序遍历、中序遍历和后序遍历，均采用递归实现。
2. 数据结构定义
2.1 二叉树节点结构
typedefcharBTDataType;typedefstructBinaryTreeNode{structBinaryTreeNode*left;// 指向左孩子的指针structBinaryTreeNode*right;// 指向右孩子的指针BTDataType data;// 数据元素}BTNode;结构说明：
data：存储节点数据（字符类型）left：指向左子节点的指针right：指向右子节点的指针
3. 二叉树构建过程
3.1 手动构造二叉树
BTNode*CreateTree(){BTNode*nodea=BuyBTNode('a');BTNode*nodeb=BuyBTNode('b');BTNode*nodec=BuyBTNode('c');BTNode*noded=BuyBTNode('d');BTNode*nodee=BuyBTNode('e');BTNode*nodef=BuyBTNode('f');nodea->left=nodeb;nodea->right=nodec;nodeb->left=noded;nodeb->right=nodee;nodec->right=nodef;returnnodea;}3.2 构造的二叉树结构
a / \ b c / \ \ d e f4. 遍历实现思路
4.1 前序遍历（Pre-order Traversal）
访问顺序：根节点 → 左子树 → 右子树
voidPreorder(BTNode*root){if(root==NULL){printf("NULL ");return;}printf("%c ",root->data);// 1. 访问根节点Preorder(root->left);// 2. 递归遍历左子树Preorder(root->right);// 3. 递归遍历右子树}前序遍历结果：a b d e c f
4.2 中序遍历（In-order Traversal）
访问顺序：左子树 → 根节点 → 右子树
voidInorder(BTNode*root){if(root==NULL){printf("NULL ");return;}Inorder(root->left);// 1. 递归遍历左子树printf("%c ",root->data);// 2. 访问根节点Inorder(root->right);// 3. 递归遍历右子树}中序遍历结果：d b e a c f
4.3 后序遍历（Post-order Traversal）
访问顺序：左子树 → 右子树 → 根节点
voidPostorder(BTNode*root){if(root==NULL){printf("NULL ");return;}Postorder(root->left);// 1. 递归遍历左子树Postorder(root->right);// 2. 递归遍历右子树printf("%c ",root->data);// 3. 访问根节点}后序遍历结果：d e b f c a
5. 递归执行过程图解
5.1 前序遍历递归展开图
Preorder(a) ├── printf("a ") // 访问根节点a ├── Preorder(b) │ ├── printf("b ") // 访问节点b │ ├── Preorder(d) │ │ ├── printf("d ") // 访问叶子节点d │ │ ├── Preorder(NULL) → 打印NULL并返回 │ │ └── Preorder(NULL) → 打印NULL并返回 │ └── Preorder(e) │ ├── printf("e ") // 访问叶子节点e │ ├── Preorder(NULL) → 打印NULL并返回 │ └── Preorder(NULL) → 打印NULL并返回 └── Preorder(c) ├── printf("c ") // 访问节点c ├── Preorder(NULL) → 打印NULL并返回 └── Preorder(f) ├── printf("f ") // 访问叶子节点f ├── Preorder(NULL) → 打印NULL并返回 └── Preorder(NULL) → 打印NULL并返回输出结果：a b d NULL NULL e NULL NULL c NULL f NULL NULL
5.2 中序遍历递归展开图
Inorder(a) ├── Inorder(b) │ ├── Inorder(d) │ │ ├── Inorder(NULL) → 打印NULL并返回 │ │ ├── printf("d ") // 访问叶子节点d │ │ └── Inorder(NULL) → 打印NULL并返回 │ ├── printf("b ") // 访问节点b │ └── Inorder(e) │ ├── Inorder(NULL) → 打印NULL并返回 │ ├── printf("e ") // 访问叶子节点e │ └── Inorder(NULL) → 打印NULL并返回 ├── printf("a ") // 访问根节点a └── Inorder(c) ├── Inorder(NULL) → 打印NULL并返回 ├── printf("c ") // 访问节点c └── Inorder(f) ├── Inorder(NULL) → 打印NULL并返回 ├── printf("f ") // 访问叶子节点f └── Inorder(NULL) → 打印NULL并返回输出结果：NULL d NULL b NULL e NULL a NULL c NULL f NULL
5.3 后序遍历递归展开图
Postorder(a) ├── Postorder(b) │ ├── Postorder(d) │ │ ├── Postorder(NULL) → 打印NULL并返回 │ │ ├── Postorder(NULL) → 打印NULL并返回 │ │ └── printf("d ") // 访问叶子节点d │ ├── Postorder(e) │ │ ├── Postorder(NULL) → 打印NULL并返回 │ │ ├── Postorder(NULL) → 打印NULL并返回 │ │ └── printf("e ") // 访问叶子节点e │ └── printf("b ") // 访问节点b ├── Postorder(c) │ ├── Postorder(NULL) → 打印NULL并返回 │ ├── Postorder(f) │ │ ├── Postorder(NULL) → 打印NULL并返回 │ │ ├── Postorder(NULL) → 打印NULL并返回 │ │ └── printf("f ") // 访问叶子节点f │ └── printf("c ") // 访问节点c └── printf("a ") // 访问根节点a输出结果：NULL NULL d NULL NULL e b NULL NULL f c a
6. 核心要点总结
6.1 递归三要素
- 递归终止条件：节点为空时停止
- 当前层操作：打印节点数据
- 递归调用：分别调用左子树和右子树的遍历函数
6.2 三种遍历的区别
| 遍历方式 | 访问顺序 | 输出结果 |
|---|---|---|
| 前序遍历 | 根→左→右 | a b d e c f |
| 中序遍历 | 左→根→右 | d b e a c f |
| 后序遍历 | 左→右→根 | d e b f c a |
6.3 时间复杂度分析
- 时间复杂度：O(n)，每个节点恰好被访问一次
- 空间复杂度：O(h)，递归栈的深度，h为树的高度
7. 代码优化建议
- 去掉NULL打印：实际应用中通常不需要打印NULL
- 非递归实现：使用栈模拟递归过程
- 层序遍历：使用队列实现广度优先遍历
文档说明：本文档基于代码实现，详细解释了二叉树三种遍历方式的递归思路和执行过程。
