二叉树是数据结构中非常重要的非线性结构，其遍历是操作二叉树的基础，指按照一定的顺序访问二叉树中的所有节点，且每个节点仅被访问一次。递归遍历因实现逻辑简洁、符合二叉树的递归定义，成为入门二叉树遍历的首选方式。本文将详细讲解二叉树的前序、中序、后序三种递归遍历的原理、实例演示，并结合代码实现，帮助大家彻底理解这一核心知识点。

---

一、二叉树的递归定义

二叉树的天然递归性是递归遍历的基础：

1. 一棵二叉树要么是空树；
2. 要么由根节点、左子树和右子树组成，且左子树和右子树也都是二叉树。

基于此，遍历二叉树的核心思路可以拆解为：先处理当前节点 / 子树的根，再递归处理左子树，最后递归处理右子树（前序），或调整三者的顺序，形成中序和后序遍历，这也是递归遍历的代码能高度复用的原因。

---

二、递归遍历的三种方式

三种遍历的核心区别在于访问根节点的时机，左子树始终优先于右子树进行递归处理，这是二叉树递归遍历的通用规则（本文均讨论根左右的遍历体系）。

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##"运行代码后得到的遍历结果如下：

1. 前序遍历：A B D H K E C F I G J
2. 中序遍历：H K D B E A I F C G J
3. 后序遍历：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 为树的高度。

---

七、二叉树递归遍历的核心优势

1. 逻辑直观，易理解：完全贴合二叉树递归定义，大问题化小，新手极易上手；
2. 代码简洁，易编写：三行核心代码实现一种遍历，无需额外数据结构；
3. 易扩展，易维护：可快速扩展节点统计、树高计算、路径查找等功能。

---

八、总结

二叉树递归遍历的核心就是调整根节点的访问时机：

1. 前序：根在最前，根→左→右；
2. 中序：根在中间，左→根→右；
3. 后序：根在最后，左→右→根。

只要理解二叉树的递归结构与终止条件，就能轻松掌握三种遍历。