二叉树的递归遍历详解：前序、中序与后序

二叉树是数据结构中非常重要的非线性结构其遍历是操作二叉树的基础指按照一定的顺序访问二叉树中的所有节点且每个节点仅被访问一次。递归遍历因实现逻辑简洁、符合二叉树的递归定义成为入门二叉树遍历的首选方式。本文将详细讲解二叉树的前序、中序、后序三种递归遍历的原理、实例演示并结合代码实现帮助大家彻底理解这一核心知识点。一、二叉树的递归定义二叉树的天然递归性是递归遍历的基础一棵二叉树要么是空树要么由根节点、左子树和右子树组成且左子树和右子树也都是二叉树。基于此遍历二叉树的核心思路可以拆解为先处理当前节点 / 子树的根再递归处理左子树最后递归处理右子树前序或调整三者的顺序形成中序和后序遍历这也是递归遍历的代码能高度复用的原因。二、递归遍历的三种方式三种遍历的核心区别在于访问根节点的时机左子树始终优先于右子树进行递归处理这是二叉树递归遍历的通用规则本文均讨论根左右的遍历体系。1. 前序遍历Pre-order Traversal遍历规则根节点 → 左子树 → 右子树先访问当前根节点再依次递归遍历左子树和右子树。核心特点与二叉树的构建顺序高度契合常用于二叉树的创建、复制。2. 中序遍历In-order Traversal遍历规则左子树 → 根节点 → 右子树先递归遍历左子树访问完左子树所有节点后再访问根节点最后递归遍历右子树。核心特点对于二叉搜索树中序遍历结果是有序序列是最常用的遍历方式之一。3. 后序遍历Post-order Traversal遍历规则左子树 → 右子树 → 根节点先依次递归遍历左、右子树待子树全部访问完毕后最后访问根节点。核心特点常用于二叉树销毁、计算树高、统计叶子节点。四、实例验证完整二叉树的遍历结果我们以一个结构清晰的二叉树为例直观展示三种递归遍历的结果前序遍历根→左→右A B D H E I C F G J K遍历逻辑先访问根A再遍历A的左子树B为根最后遍历A的右子树C为根子树遵循相同规则。中序遍历左→根→右H D B E I A F C J G K遍历逻辑先遍历A的左子树B为根再访问根A最后遍历A的右子树C为根子树遵循相同规则。后序遍历左→右→根H D I E B F J K G C A遍历逻辑先遍历A的左子树B为根再遍历A的右子树C为根最后访问根A子树遵循相同规则。五、测试结果与遍历过程分析本文统一测试用例str[] ABDH#K###E##CFI###G#J##运行代码后得到的遍历结果如下前序遍历A B D H K E C F I G J中序遍历H K D B E A I F C G J后序遍历K H D E B I F J G C A核心遍历过程以根节点 A 为例前序先访问 A → 递归遍历 A 的左子树B 为根 → 递归遍历 A 的右子树C 为根中序先递归遍历 A 的左子树B 为根 → 访问 A → 递归遍历 A 的右子树C 为根后序先递归遍历 A 的左子树B 为根 → 递归遍历 A 的右子树C 为根 → 访问 A。子树的遍历过程与根节点完全一致例如左子树根 B 的遍历仍按照对应规则先处理 B再处理 B 的左子树 D最后处理 B 的右子树 E以此类推直到遇到空节点#终止递归。三、代码实现基于 C 语言的递归遍历本文所有代码均基于链式存储的二叉树实现先通过前序遍历字符串#表示空节点构建二叉树再实现三种递归遍历。除满二叉树和完全二又树外其它场景使用数组存储比较浪费空间1. 基础结构体与全局定义#include stdio.h #include stdlib.h // 定义节点数据类型为字符型 typedef char ElemType; // 二叉树节点结构体 typedef struct TreeNode { ElemType data; struct TreeNode *lchild; // 左孩子指针 struct TreeNode *rchild; // 右孩子指针 }TreeNode; // 二叉树类型节点指针 typedef TreeNode* BiTree; // 前序遍历的二叉树构建字符串#表示空节点 char str[] ABDH#K###E##CFI###G#J##; int idx 0; // 遍历字符串的索引全局变量保证递归时持续递增2. 二叉树的构建前序递归构建// 构建二叉树传入二级指针实现对根节点的修改 void createTree(BiTree *T) { ElemType ch; ch str[idx]; // 读取当前字符并移动索引 if (ch #) { *T NULL; // 空节点置为NULL } else { // 分配节点内存 *T (BiTree)malloc(sizeof(TreeNode)); (*T)-data ch; // 设置节点数据 createTree((*T)-lchild); // 递归构建左子树 createTree((*T)-rchild); // 递归构建右子树 } }3. 前序递归遍历实现// 前序递归遍历 void preOrder(BiTree T) { if (T NULL) { return; // 递归终止空树无需遍历 } printf(%c , T-data); // 访问根节点 preOrder(T-lchild); // 递归遍历左子树 preOrder(T-rchild); // 递归遍历右子树 }4. 中序递归遍历实现// 中序递归遍历 void inOrder(BiTree T) { if (T NULL) { return; } inOrder(T-lchild); // 递归遍历左子树 printf(%c , T-data); // 访问根节点 inOrder(T-rchild); // 递归遍历右子树 }5. 后序递归遍历实现// 后序递归遍历 void postOrder(BiTree T) { if (T NULL) { return; } postOrder(T-lchild); // 递归遍历左子树 postOrder(T-rchild); // 递归遍历右子树 printf(%c , T-data); // 访问根节点 }6. 主函数测试int main(int argc, char const *argv[]) { BiTree T; createTree(T); // 构建二叉树 printf(前序遍历结果); preOrder(T); printf(\n); printf(中序遍历结果); inOrder(T); printf(\n); printf(后序遍历结果); postOrder(T); printf(\n); return 0; }7.完整代码如下#include stdio.h #include stdlib.h // 1. 二叉树节点结构体定义 // 定义二叉树节点存储的数据类型这里使用字符型 typedef char ElemType; // 二叉树节点结构体 typedef struct TreeNode { ElemType data; // 节点数据域 struct TreeNode *lchild; // 左孩子指针指向左子树 struct TreeNode *rchild; // 右孩子指针指向右子树 } TreeNode; // 给二叉树指针起别名方便使用 typedef TreeNode* BiTree; // 2. 全局变量构建二叉树使用 // 前序遍历序列# 代表空节点按照这个字符串递归构建二叉树 char str[] ABDH#K###E##CFI###G#J##; int idx 0; // 字符串遍历索引全局变量保证递归时索引持续递增 // 3. 前序递归创建二叉树 // 功能根据前序字符串递归创建二叉树 // 参数二级指针用于修改传入的根节点指针 void createTree(BiTree *T) { // 1. 读取当前字符索引自增 ElemType ch str[idx]; // 2. 递归终止条件遇到 # 表示空节点 if (ch #) { *T NULL; } // 3. 非空节点创建节点并递归构建左右子树 else { // 分配节点内存空间 *T (BiTree)malloc(sizeof(TreeNode)); // 给节点赋值 (*T)-data ch; // 递归创建左子树前序根 → 左 → 右 createTree((*T)-lchild); // 递归创建右子树 createTree((*T)-rchild); } } // 4. 前序递归遍历 // 遍历规则根节点 → 左子树 → 右子树 void preOrder(BiTree T) { // 递归终止条件节点为空直接返回 if (T NULL) { return; } // 1. 访问根节点打印数据 printf(%c , T-data); // 2. 递归遍历左子树 preOrder(T-lchild); // 3. 递归遍历右子树 preOrder(T-rchild); } // 5. 中序递归遍历 // 遍历规则左子树 → 根节点 → 右子树 void inOrder(BiTree T) { // 递归终止条件 if (T NULL) { return; } // 1. 递归遍历左子树 inOrder(T-lchild); // 2. 访问根节点 printf(%c , T-data); // 3. 递归遍历右子树 inOrder(T-rchild); } // 6. 后序递归遍历 // 遍历规则左子树 → 右子树 → 根节点 void postOrder(BiTree T) { // 递归终止条件 if (T NULL) { return; } // 1. 递归遍历左子树 postOrder(T-lchild); // 2. 递归遍历右子树 postOrder(T-rchild); // 3. 访问根节点 printf(%c , T-data); } // 7. 主函数测试 int main() { BiTree T; // 定义二叉树根节点指针 // 1. 递归创建二叉树 createTree(T); printf( 二叉树递归遍历结果 \n); // 2. 前序遍历 printf(前序遍历); preOrder(T); printf(\n); // 3. 中序遍历 printf(中序遍历); inOrder(T); printf(\n); // 4. 后序遍历 printf(后序遍历); postOrder(T); printf(\n); return 0; }8.运行截图六、递归遍历的核心要点1. 递归终止条件节点为 NULL 时直接返回这是避免递归死循环的关键也是二叉树递归的天然终止点。2. 代码的高度复用性三种遍历代码结构几乎一致仅根节点访问时机不同记住左子树永远优先于右子树即可。3. 递归的底层原理递归遍历底层依靠系统栈自动保存上下文无需手动管理入栈、出栈代码极简。4. 时间与空间复杂度时间复杂度O(n)每个节点仅访问一次空间复杂度O(h)h 为树的高度。七、二叉树递归遍历的核心优势逻辑直观易理解完全贴合二叉树递归定义大问题化小新手极易上手代码简洁易编写三行核心代码实现一种遍历无需额外数据结构易扩展易维护可快速扩展节点统计、树高计算、路径查找等功能。八、总结二叉树递归遍历的核心就是调整根节点的访问时机前序根在最前根→左→右中序根在中间左→根→右后序根在最后左→右→根。只要理解二叉树的递归结构与终止条件就能轻松掌握三种遍历。