Warning

含AI生成内容

二叉树的遍历与线索化#

遍历概述#

遍历（Traversal）是指按照某种规则访问树中所有结点一次且仅一次的过程。二叉树的基础定义和存储结构已在树与二叉树基础中介绍。

四种遍历方式#

递归遍历#

遍历方式	访问顺序	口诀	递归思路
前序（Preorder）	根 → 左 → 右	根左右	先访问根，再遍历左子树，最后遍历右子树
中序（Inorder）	左 → 根 → 右	左根右	先遍历左子树，再访问根，最后遍历右子树
后序（Postorder）	左 → 右 → 根	左右根	先遍历左子树，再遍历右子树，最后访问根
层序（Level-order）	逐层从左到右	逐层	从根开始，从上到下、从左到右依次访问

非递归遍历（重点考点）#

非递归遍历的核心思路是手动维护栈来模拟函数调用栈，其中中序非递归遍历最常考。

前序非递归#

1
栈 <- 根
2
while 栈非空:
3
    p = pop()
4
    访问 p
5
    if p.rchild != NULL: push(p.rchild)   // 先右
6
    if p.lchild != NULL: push(p.lchild)   // 后左

中序非递归（最常考）#

1
p = 根
2
while p != NULL || 栈非空:
3
    while p != NULL:          // 一路向左入栈
4
        push(p)
5
        p = p.lchild
6
    p = pop()                 // 出栈访问
7
    访问 p
8
    p = p.rchild              // 转向右子树

中序非递归遍历是考研最高频的非递归遍历题目，必须熟练掌握。

后序非递归#

后序非递归相对复杂，常用标记法或双栈法。

标记法（辅助指针 r 记录最近访问的结点）：

1
p = 根
2
while p != NULL || 栈非空:
3
    while p != NULL:
4
        push(p)
5
        p = p.lchild
6
    p = top()                 // 取栈顶但不弹出
7
    if p.rchild != NULL && p.rchild != r:   // 右子树存在且未被访问
8
        p = p.rchild          // 转向右子树
9
    else:
10
        p = pop()
11
        访问 p
12
        r = p                 // 记录最近访问的结点
13
        p = NULL              // p 置空，继续出栈

层序非递归#

1
队列 <- 根
2
while 队列非空:
3
    p = 出队
4
    访问 p
5
    if p.lchild != NULL: 入队 p.lchild
6
    if p.rchild != NULL: 入队 p.rchild

层序遍历需要借助队列实现，详见队列（Queue）。

遍历的递归实现（代码简洁）#

1
void PreOrder(BiTree T) {        // 前序
2
    if (T != NULL) {
3
        visit(T);
4
        PreOrder(T->lchild);
5
        PreOrder(T->rchild);
6
    }
7
}
8

9
void InOrder(BiTree T) {         // 中序
10
    if (T != NULL) {
11
        InOrder(T->lchild);
12
        visit(T);
13
        InOrder(T->rchild);
14
    }
15
}
16

17
void PostOrder(BiTree T) {       // 后序
18
    if (T != NULL) {
19
        PostOrder(T->lchild);
20
        PostOrder(T->rchild);
21
        visit(T);
22
    }
23
}

由遍历序列构造二叉树#

核心结论#

必须包含中序遍历才能唯一确定一棵二叉树。

组合	能否唯一确定	说明
前序 + 中序	可以	前序确定根，中序分割左右子树
后序 + 中序	可以	后序确定根，中序分割左右子树
层序 + 中序	可以	层序确定根，中序分割左右子树
前序 + 后序	不能	当结点只有单孩子时，无法判断是左孩子还是右孩子

构造方法#

以前序 + 中序为例（递归思路）：

前序第一个元素为根结点
在中序中找到根的位置，左边为左子树中序序列，右边为右子树中序序列
根据左右子树结点个数，在前序中划分出左右子树的前序序列
对左右子树递归执行以上步骤

后序 + 中序类似，后序的最后一个元素为根结点。层序 + 中序需要从左到右扫描层序序列确定每层的根。

线索二叉树#

引入动机#

二叉链表的 n+1 个空指针域被浪费了。线索化利用这些空指针指向遍历序列的前驱和后继。

存储结构#

1
typedef struct ThreadNode {
2
    int data;
3
    struct ThreadNode *lchild, *rchild;
4
    int ltag, rtag;      // 0: 指向孩子; 1: 指向前驱/后继
5
} ThreadNode, *ThreadTree;

tag 标志含义：

标志位	值 = 0	值 = 1
ltag	lchild 指向左孩子	lchild 指向前驱
rtag	rchild 指向右孩子	rchild 指向后继

三种线索化#

线索类型	前驱	后继	特点
中序线索化	好找	好找	最常用，前驱和后继都容易找到
前序线索化	难找	好找	找后驱方便，找前驱需要三叉链表或从头遍历
后序线索化	好找	难找	找前驱方便，找后继需要三叉链表或从头遍历

注意：前序线索化时，如果当前结点有左孩子（ltag == 0），必须先处理左子树再访问后继，否则会造成死循环——因为前序访问顺序是”根左右”，给根结点设置后继指针指向右孩子后，如果 ltag == 0 时错误地通过后继指针走回根结点，就形成了循环。具体来说，当访问完左子树最后一个结点后，其后继会指向根结点的右子树，但如果左子树线索化时错误引用了当前结点的后继，就会陷入循环。约定：前序线索化时先判断 ltag == 0 再访问左子树。

中序线索化的遍历（最常用）#

寻找中序后继的代码体现了线索化的最大优势：

1
// 找到以 p 为根的子树中第一个被中序遍历的结点（最左下）
2
ThreadNode *FirstNode(ThreadNode *p) {
3
    while (p->ltag == 0)
4
        p = p->lchild;
5
    return p;
6
}
7

8
// 求 p 在中序序列中的后继
9
ThreadNode *NextNode(ThreadNode *p) {
10
    if (p->rtag == 1)
11
        return p->rchild;          // 线索直接指向后继
12
    else
13
        return FirstNode(p->rchild);  // 右子树最左下结点
14
}
15

16
// 中序线索二叉树的中序遍历（不用递归，不用栈！）
17
void InOrder(ThreadTree T) {
18
    for (ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p))
19
        visit(p);
20
}

线索二叉树的优点#

遍历无需栈：中序线索二叉树可在 O(1) 空间复杂度下完成遍历
快速找前驱后继：特别适用于需要频繁遍历或查找前驱后继的场景
充分利用空指针：将 n+1 个空指针转化为有用信息

线索二叉树的考研考点#

给定二叉树，画出中序线索二叉树（要求标注 ltag/rtag 和指针方向）
判断中序线索二叉树中某结点的前驱/后继
中序线索二叉树的遍历代码填空
前序/后序线索化找前驱后继的局限性
线索二叉树的存储密度分析

关联页面#

树与二叉树基础 — 二叉树的定义与存储结构
栈（Stack） — 非递归遍历的辅助结构
队列（Queue） — 层序遍历的辅助结构
二叉排序树与平衡二叉树 — 中序遍历的 BST 递增性质

音乐

音乐

二叉树的遍历与线索化#

遍历概述#

四种遍历方式#

递归遍历#

非递归遍历（重点考点）#

前序非递归#

中序非递归（最常考）#

后序非递归#

层序非递归#

遍历的递归实现（代码简洁）#

由遍历序列构造二叉树#

核心结论#

构造方法#

线索二叉树#

引入动机#

存储结构#

三种线索化#

中序线索化的遍历（最常用）#

线索二叉树的优点#

线索二叉树的考研考点#

关联页面#

文章分享

评论区