Lecture 17：二叉树的遍历

17.1 二叉树的递归遍历

17.1.1 二叉树的遍历

定义：#二叉树遍历

描述： 二叉树的遍历是按某种规则访问二叉树中的每个结点，并且每个结点恰好访问一次。

递归基础

• 二叉树要么为空。
• 二叉树要么由根结点、左子树、右子树组成。
• 因此遍历二叉树，本质就是确定“根、左、右”三部分的访问顺序。

三种递归遍历

其中：

• N 表示根结点。
• L 表示左子树。
• R 表示右子树。

小例子一：左右孩子都存在

    A
   / \
  B   C

小例子二：只有左孩子

    A
   /
  B

小例子三：只有右孩子

    A
     \
      C

PDF 示例树

        A
      /   \
     B     C
    / \   / \
   D   E F   G

读图说明

• 只有左孩子与只有右孩子是两种不同形态；即使得到的部分遍历序列相同，也不能据此忽略左右位置。
• 对下方七结点树递归套用 NLR、LNR、LRN，分别得到 A B D E C F G、D B E A F C G、D E B F G C A。

17.1.2 表达式树与三种遍历

PDF 给出的算术表达式为： $$ a+b*(c-d)-e/f $$

其表达式树可以理解为：

             -
           /   \
          +     /
        /  \   / \
       a    * e   f
           / \
          b   -
             / \
            c   d

三种遍历对应三种表达式

注意

• 表达式树的中序遍历得到中缀表达式。
• 中缀表达式为了保持原来的运算含义，通常需要补充括号。
• 在运算符元数固定、词法记号可无歧义分隔的前提下，先序和后序序列不需要括号也能唯一表达运算顺序；若存在可变元运算符或记号本身无法唯一切分，还需额外的元数或分隔信息。

读图说明

• 运算符是分支结点，操作数是叶子结点；根运算符 - 最后执行。
• 直接中序遍历只给出符号顺序，必须按子树边界补括号，才能保持原表达式的运算结构。

17.2 先序、中序、后序遍历

17.2.1 先序遍历

定义：#先序遍历

描述： 先序遍历按照“根-左-右”的顺序访问二叉树。

操作过程

1. 若二叉树为空，则什么也不做。
2. 若二叉树非空：
   • 访问根结点。
   • 先序遍历左子树。
   • 先序遍历右子树。

形象解释

• 从根结点出发，沿树边画一条路。
• 若左边还有没走的路，优先向左走。
• 走到路的尽头，也就是空结点，就往回走。
• 左边没路了，再走右边。
• 左右都没路了，就向上回退。

访问时机

• 先序遍历是在第一次路过结点时访问结点。
• 每个结点在递归遍历的路线中会被路过多次，但真正访问只有一次。

空间复杂度 递归遍历需要递归工作栈，空间复杂度为： $$ O(h) $$

其中 $h$ 为二叉树高度。

先序遍历代码

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void PreOrder(BiTree T) {
    if (T != NULL) {
        visit(T);              // 访问根结点
        PreOrder(T->lchild);   // 递归遍历左子树
        PreOrder(T->rchild);   // 递归遍历右子树
    }
}

17.2.2 中序遍历

定义：#中序遍历

描述： 中序遍历按照“左-根-右”的顺序访问二叉树。

操作过程

1. 若二叉树为空，则什么也不做。
2. 若二叉树非空：
   • 中序遍历左子树。
   • 访问根结点。
   • 中序遍历右子树。

形象解释

• 从根结点出发，如果左边还有没走的路，优先向左边走。
• 走到空结点后回退。
• 第二次路过某个结点时访问该结点。
• 访问后再转向右子树。

访问时机

• 中序遍历是在第二次路过结点时访问结点。

二叉排序树中的意义

• 对二叉排序树进行中序遍历，可以得到递增序列。

中序遍历代码

void InOrder(BiTree T) {
    if (T != NULL) {
        InOrder(T->lchild);    // 递归遍历左子树
        visit(T);              // 访问根结点
        InOrder(T->rchild);    // 递归遍历右子树
    }
}

17.2.3 后序遍历

定义：#后序遍历

描述： 后序遍历按照“左-右-根”的顺序访问二叉树。

操作过程

1. 若二叉树为空，则什么也不做。
2. 若二叉树非空：
   • 后序遍历左子树。
   • 后序遍历右子树。
   • 访问根结点。

访问时机

• 后序遍历是在第三次路过结点时访问结点。
• 因为必须先处理完左、右子树，最后才能处理根结点。

后序遍历代码

void PostOrder(BiTree T) {
    if (T != NULL) {
        PostOrder(T->lchild);  // 递归遍历左子树
        PostOrder(T->rchild);  // 递归遍历右子树
        visit(T);              // 访问根结点
    }
}

17.2.4 三种递归遍历对比

共同点

• 都利用二叉树的递归定义。
• 都会访问每个结点一次。
• 时间复杂度均为： $$ O(n) $$
• 递归空间复杂度均为： $$ O(h) $$

17.3 二叉树的层次遍历

17.3.1 基础概念

定义：#层次遍历

描述： 层次遍历按照从上到下、从左到右的顺序访问二叉树中的结点。

算法思想

1. 初始化一个辅助队列。
2. 根结点入队。
3. 若队列非空，则队头结点出队。
4. 访问出队结点。
5. 若该结点有左孩子，则左孩子入队。
6. 若该结点有右孩子，则右孩子入队。
7. 重复上述过程，直到队列为空。

为什么使用队列

• 层次遍历需要先访问先进入等待区的结点。
• 同一层从左到右入队。
• 下一层按入队顺序出队，正好符合先进先出。

示例

        A
      /   \
     B     C
    / \   / \
   D   E F   G
  / \   / \   \
 H   I J   K   L

层次遍历序列为：

A B C D E F G H I J K L

读图说明

• 结点按 A,B,C,D,E,F,G,H,I,J,K,L 依次出队；每个结点出队时，再把它的非空左、右孩子按顺序入队。
• 辅助队列的峰值容量由同一时刻等待访问的结点数决定，量级为树的最大层宽 $w$。

17.3.2 层次遍历代码

void LevelOrder(BiTree T) {
    if (T == NULL) {
        return;
    }

    LinkQueue Q;
    InitQueue(Q);       // 初始化辅助队列

    BiTree p;
    EnQueue(Q, T);      // 根结点入队

    while (!IsEmpty(Q)) {
        DeQueue(Q, p);  // 队头结点出队
        visit(p);       // 访问出队结点

        if (p->lchild != NULL) {
            EnQueue(Q, p->lchild);
        }

        if (p->rchild != NULL) {
            EnQueue(Q, p->rchild);
        }
    }
}

PDF 中的队列结点结构

// 二叉树的结点（链式存储）
typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 链式队列结点
typedef struct LinkNode {
    BiTNode *data;          // 存指针，而不是存完整结点
    struct LinkNode *next;
} LinkNode;

typedef struct {
    LinkNode *front, *rear; // 队头、队尾
} LinkQueue;

注意

• 队列结点中保存的是 BiTNode *data。
• 也就是说，队列里放的是树结点的指针，而不是复制一整个树结点。
• 这样可以减少空间开销，也能直接定位原树中的结点。
• 层序遍历时间复杂度为 $O(n)$，辅助空间复杂度为 $O(w)$；最坏情况下 $w=\Theta(n)$，因此也常写为 $O(n)$。
• 上面的 InitQueue、EnQueue、DeQueue、IsEmpty 是抽象队列接口；实际 C/C++ 程序须补齐接口定义，并按接口约定传入队列及处理入队失败。

17.4 遍历序列构造二叉树

17.4.1 基本结论

定义：#遍历序列构造二叉树

描述： 根据给定的遍历序列，还原二叉树的结构。

只给一种遍历序列

• 只给前序、中序、后序、层序中的任意一种，都不能唯一确定一棵二叉树。
• 原因是同一个遍历序列可以对应不同的二叉树。

以上结论默认序列只记录结点关键字，不包含空孩子标记。若先序或后序序列同时完整记录空指针标记（例如 #），单条序列也可以唯一描述二叉树。

唯一重建的前提

• 下表中的“能唯一确定”默认所有结点关键字互不相同，否则无法在中序序列中唯一定位根。
• 两条输入序列必须包含完全相同的结点集合，且每个结点出现次数一致。

能唯一确定二叉树的组合

特殊情况

• 若已知二叉树是真二叉树（每个非叶结点都恰有两个孩子）且关键字互异，则前序 + 后序可以唯一重建；满二叉树也满足这一条件，但一般二叉树不能直接套用。真二叉树不要求所有层都填满，不能与满二叉树混称。

核心方法

1. 圈根结点：
   • 前序序列第一个元素是根。
   • 后序序列最后一个元素是根。
   • 层序序列第一个元素是根。
2. 划分左右子树：
   • 在中序序列中找到根结点。
   • 根左边是左子树的中序序列。
   • 根右边是右子树的中序序列。
3. 找父结点：
   • 在另一条序列中，根据左右子树元素集合继续找根。
4. 递归重复：
   • 对左子树重复。
   • 对右子树重复。

17.4.2 前序 + 中序

方法

• 前序序列确定根结点。
• 中序序列确定左、右子树。
• 左、右子树在前序序列中的长度分别与中序中划出的左右子树长度相同。

PDF 示例

前序遍历序列：A D B C E
中序遍历序列：B D C A E

还原过程

1. 前序第一个结点为 A，所以根结点是 A。
2. 在中序序列中找到 A：

B D C | A | E

3. A 左边 B D C 是左子树，右边 E 是右子树。
4. 左子树对应的前序序列为：

D B C

5. 左子树根为 D。
6. 在左子树中序 B D C 中，D 左边是 B，右边是 C。

还原结果

      A
    /   \
   D     E
  / \
 B   C

读图说明

• 前序首元素确定当前根；在中序中找到该根后，根左、右两侧分别给出左右子树的结点集合与规模。

17.4.3 后序 + 中序

方法

• 后序序列最后一个元素是根结点。
• 中序序列根据根结点划分左、右子树。
• 后序序列中左、右子树的长度与中序划分出的左右子树长度一致。

PDF 示例

后序遍历序列：E F A H C I G B D
中序遍历序列：E A F D H C B G I

还原过程

1. 后序最后一个结点为 D，所以根结点是 D。
2. 在中序序列中找到 D：

E A F | D | H C B G I

3. 左子树中序为 E A F，右子树中序为 H C B G I。
4. 左子树后序为 E F A，所以左子树根为 A。
5. 右子树后序为 H C I G B，所以右子树根为 B。
6. 继续递归划分。

还原结果

        D
      /   \
     A     B
    / \   / \
   E   F C   G
        /     \
       H       I

读图说明

• 后序末元素确定当前根；根据中序左右分区的长度，从后序序列中切出左右子树，再递归处理。

17.4.4 层序 + 中序

方法

• 层序序列第一个结点是根。
• 中序序列根据根结点划分左、右子树。
• 层序序列中属于左子树的元素，按原来的层序相对次序组成左子树层序。
• 层序序列中属于右子树的元素，按原来的层序相对次序组成右子树层序。

PDF 示例

层序遍历序列：D A B E F C G H I
中序遍历序列：E A F D H C B G I

还原过程

1. 层序第一个结点为 D，所以根结点是 D。
2. 在中序中找到 D：

E A F | D | H C B G I

3. 左子树元素集合为 {E,A,F}。
4. 右子树元素集合为 {H,C,B,G,I}。
5. 从层序序列中筛出左子树层序：

A E F

6. 从层序序列中筛出右子树层序：

B C G H I

7. 对左右子树继续递归。

还原结果

        D
      /   \
     A     B
    / \   / \
   E   F C   G
        /     \
       H       I

读图说明

• 层序首元素确定根；中序划分左右结点集合后，从剩余层序中按原相对次序筛出左、右子树层序。

17.5 线索二叉树的概念

17.5.1 为什么需要线索二叉树

普通二叉链表的问题

• 树的遍历通常必须从根结点开始。
• 如果只有一个普通结点指针，不知道根结点，就很难向上查找。
• 普通二叉链表无法直接找到当前结点在某种遍历序列中的前驱或后继。

线索二叉树的思想

• 二叉链表中有很多空指针。
• 可以把这些空指针改造成指向前驱或后继的线索。
• 建立整棵树的线索时，通常按相应次序遍历一次，在访问结点时确定其前驱或后继并建立线索。

定义：#线索二叉树

描述： 线索二叉树是把二叉链表中的空指针改为指向某种遍历序列中前驱或后继的指针后得到的二叉树。

17.5.2 中序线索二叉树

中序线索化过程

• 从根结点出发，重新进行一次中序遍历。
• 指针 q 记录当前访问的结点。
• 指针 pre 记录上一个被访问的结点。
• 如果当前结点 q 的左孩子为空，则让 q->lchild 指向 pre，表示前驱线索。
• 如果 pre 的右孩子为空，则让 pre->rchild 指向 q，表示后继线索。

线索标志域

判断前驱和后继

• 当 q == p 时，pre 是 p 的前驱。
• 当 pre == p 时，q 是 p 的后继。

PDF 中序遍历序列示例

D <-> G <-> B <-> E <-> A <-> F <-> C

或写成普通序列：

D G B E A F C

读图说明

• 实线仍表示真实孩子，虚线表示由空指针改造的前驱或后继线索。
• 结点中的 0/1 是 ltag/rtag；只有标志为 1 时，相应指针才解释为线索。

17.5.3 线索二叉树结点

// 线索二叉树结点
typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;      // 左、右线索标志
} ThreadNode, *ThreadTree;

字段解释

• data 保存结点数据。
• lchild 可能指向左孩子，也可能指向前驱。
• rchild 可能指向右孩子，也可能指向后继。
• ltag 用来判断 lchild 的真实含义。
• rtag 用来判断 rchild 的真实含义。

17.6 二叉树的线索化

17.6.1 老方法：通过中序遍历找前驱

思想

• 多用一次中序遍历。
• 用 pre 保存当前访问结点的前一个结点。
• 用 p 表示目标结点。
• 当当前访问结点 q 等于目标结点 p 时，pre 就是 p 的中序前驱。

代码

// 目标结点和辅助变量
BiTNode *p;              // p 指向目标结点
BiTNode *pre = NULL;     // 当前访问结点的前驱
BiTNode *final = NULL;   // 最终结果

void visit(BiTNode *q) {
    if (q == p) {
        final = pre;     // 找到 p 的前驱
    } else {
        pre = q;         // pre 指向当前访问的结点
    }
}

void InOrder(BiTree T) {
    if (T != NULL) {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

核心

• 这种方法没有真正改变树的结构。
• 每次找前驱都要重新遍历。
• 线索二叉树就是把这个“上一步结果”保存到空指针中，避免重复遍历。
• 每次重新查询前应将 p 设为新目标，并把 pre、final 重置为 NULL；若目标不在这棵树中，final 仍为 NULL。

读图说明

• 中序访问到目标 p=F 时，pre 仍指向刚访问完的 A，因此 final=A；这说明普通方法每查询一次都要从根重新遍历。

17.6.2 中序线索化

基本概念

1. 中序、先序、后序线索化，都是在遍历算法基础上改造。
2. 当访问一个结点时，连接该结点与前驱结点的线索信息。
3. 用指针 pre 记录当前访问结点的前驱结点。
4. 最后一个结点的 rchild 和 rtag 需要单独处理。

中序线索化递归算法

void InThread(ThreadTree p, ThreadTree &pre) {
    if (p != NULL) {
        InThread(p->lchild, pre);      // 递归线索化左子树

        if (p->lchild == NULL) {       // 左子树为空，建立前驱线索
            p->lchild = pre;
            p->ltag = 1;
        }

        if (pre != NULL && pre->rchild == NULL) {
            pre->rchild = p;           // 建立前驱结点的后继线索
            pre->rtag = 1;
        }

        pre = p;                       // 当前结点成为刚刚访问过的结点
        InThread(p->rchild, pre);      // 递归线索化右子树
    }
}

建立中序线索二叉树

void CreateInThread(ThreadTree T) {
    ThreadTree pre = NULL;

    if (T != NULL) {
        InThread(T, pre);      // 线索化二叉树
        pre->rchild = NULL;    // 处理遍历的最后一个结点
        pre->rtag = 1;
    }
}

注意

• 调用线索化函数前，原树所有结点的 ltag、rtag 都应初始化为 0；这些示例用于尚未线索化的树，不能对同一棵树重复线索化。
• 原树中真实存在的左、右孩子，对应的 ltag、rtag 应为 0。
• 空孩子被改造成线索时，对应标志才置为 1。
• 最后一个被中序访问的结点没有后继，所以其 rchild 置为 NULL，rtag 置为 1。

17.6.3 先序遍历线索化

普通写法的风险

void PreThread(ThreadTree T) {
    if (T != NULL) {
        visit(T);
        PreThread(T->lchild);
        PreThread(T->rchild);
    }
}

问题

• 先序遍历先访问根结点。
• 若访问根结点时发现左孩子为空，就可能把 lchild 改成前驱线索。
• 如果之后仍然无条件递归 T->lchild，就会沿着线索走回前驱，造成错误递归。

正确要点

• 只有当 ltag == 0，也就是 lchild 仍然指向真实左孩子时，才能递归线索化左子树。
• 递归处理左子树期间，当前结点原本为空的 rchild 可能被改成后继线索；因此递归右子树前也必须检查 rtag == 0，否则可能沿线索再次进入已经访问过的结点。

先序线索化代码

void PreThread(ThreadTree p, ThreadTree &pre) {
    if (p == NULL) {
        return;
    }

    if (p->lchild == NULL) {         // 左子树为空，建立前驱线索
        p->lchild = pre;
        p->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL) {
        pre->rchild = p;             // 建立前驱结点的后继线索
        pre->rtag = 1;
    }
    pre = p;

    if (p->ltag == 0) {              // 只沿真实左孩子递归
        PreThread(p->lchild, pre);
    }
    if (p->rtag == 0) {              // 左子树处理后再次确认右指针不是线索
        PreThread(p->rchild, pre);
    }
}

void CreatePreThread(ThreadTree T) {
    ThreadTree pre = NULL;

    if (T != NULL) {
        PreThread(T, pre);
        pre->rchild = NULL;           // 最后一个先序结点没有后继
        pre->rtag = 1;
    }
}

重点

• 先序线索化必须区分孩子指针与线索：左递归前检查 ltag，右递归前检查 rtag。
• pre 始终指向先序序列中刚访问过的结点；主过程还要收尾处理最后一个结点的右线索。

17.6.4 后序遍历线索化

思想

• 后序线索化顺序为左、右、根。
• 访问当前结点时，才建立当前结点和前驱结点之间的线索。

后序线索化代码

void PostThread(ThreadTree p, ThreadTree &pre) {
    if (p != NULL) {
        PostThread(p->lchild, pre);    // 递归线索化左子树
        PostThread(p->rchild, pre);    // 递归线索化右子树

        if (p->lchild == NULL) {       // 左子树为空，建立前驱线索
            p->lchild = pre;
            p->ltag = 1;
        }

        if (pre != NULL && pre->rchild == NULL) {
            pre->rchild = p;           // 建立前驱结点的后继线索
            pre->rtag = 1;
        }

        pre = p;                       // 当前结点成为刚刚访问过的结点
    }
}

建立后序线索二叉树

void CreatePostThread(ThreadTree T) {
    ThreadTree pre = NULL;

    if (T != NULL) {
        PostThread(T, pre);

        if (pre->rchild == NULL) {     // 处理遍历的最后一个结点
            pre->rtag = 1;
        }
    }
}

注意

• 后序遍历最后访问根结点。
• 根结点通常没有后继。
• 若要方便从结点向父结点找后继，常常需要三叉链表中的 parent 指针。

17.7 线索二叉树找前驱后继

17.7.1 中序线索二叉树

找中序后继

设要找结点 p 的中序后继 next。

情况一：p->rtag == 1

• p->rchild 指向后继线索。
• 因此：

next = p->rchild;

情况二：p->rtag == 0

• p 有真实右子树。
• 中序遍历顺序为左、根、右。
• 访问完 p 后，下一步应该进入右子树。
• 后继是右子树中第一个被中序遍历的结点，也就是右子树中最左下的结点。

找以 p 为根的子树中第一个被中序遍历的结点

ThreadNode *Firstnode(ThreadNode *p) {
    if (p == NULL) {
        return NULL;
    }
    while (p->ltag == 0) {
        p = p->lchild;
    }
    return p;
}

找中序后继代码

ThreadNode *Nextnode(ThreadNode *p) {
    if (p->rtag == 0) {
        return Firstnode(p->rchild);
    } else {
        return p->rchild;
    }
}

利用线索进行中序遍历

void Inorder(ThreadNode *T) {
    for (ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p)) {
        visit(p);
    }
}

空间复杂度

• 利用线索遍历不需要递归调用栈。
• 额外空间复杂度为： $$ O(1) $$

读图说明

• rtag==1 时沿后继线索一步到达；rtag==0 时进入真实右子树，并沿真实左孩子下降到该子树中序序列的第一个结点。

找中序前驱

情况一：p->ltag == 1

• p->lchild 直接指向前驱线索。

情况二：p->ltag == 0

• p 有真实左子树。
• 中序遍历中，p 的前驱是左子树中最后一个被中序遍历的结点。
• 也就是左子树中最右下的结点。

找以 p 为根的子树中最后一个被中序遍历的结点

ThreadNode *Lastnode(ThreadNode *p) {
    if (p == NULL) {
        return NULL;
    }
    while (p->rtag == 0) {
        p = p->rchild;
    }
    return p;
}

找中序前驱代码

ThreadNode *Prenode(ThreadNode *p) {
    if (p->ltag == 0) {
        return Lastnode(p->lchild);
    } else {
        return p->lchild;
    }
}

逆向中序遍历

void RevInorder(ThreadNode *T) {
    for (ThreadNode *p = Lastnode(T); p != NULL; p = Prenode(p)) {
        visit(p);
    }
}

17.7.2 先序线索二叉树

找先序后继

先序遍历顺序为：

根 -> 左 -> 右

按优先级判断

读图说明

• 先序访问根后优先进入真实左子树；没有左孩子才进入真实右子树；叶子或无可进入子树时才沿后继线索。

找先序前驱

重要结论

• 如果 p 是根结点，则 p 没有先序前驱。
• 先序线索二叉树一般不能直接找到先序前驱。
• 除非使用三叉链表，或者从根结点开始重新遍历寻找。

若能找到父结点，可以按以下规则判断

1. 如果 p 是父结点的左孩子，则父结点就是 p 的先序前驱。
2. 如果 p 是父结点的右孩子，且左兄弟为空，则父结点就是 p 的先序前驱。
3. 如果 p 是父结点的右孩子，且左兄弟非空，则 p 的先序前驱是左兄弟子树中最后一个被先序遍历的结点。

读图说明

• 前两种情况的前驱都是父结点；第三种情况要进入左兄弟子树，反复优先走真实右孩子、否则走真实左孩子，找到该子树先序序列的最后一个结点。

17.7.3 后序线索二叉树

找后序前驱

后序遍历顺序为：

左 -> 右 -> 根

情况一：p->ltag == 1

• p->lchild 是前驱线索。
• 前驱为：

p->lchild

情况二：p->ltag == 0

• 说明 p 有真实左孩子。
• 若 p 有右孩子，则后序前驱为右孩子。
• 若 p 没有右孩子，则后序前驱为左孩子。

规则

读图说明

• 后序访问根之前先完成右子树，所以有真实右孩子时前驱是右孩子；没有右孩子但有左孩子时前驱是左孩子；叶子则使用前驱线索。

找后序后继

重要结论

• 后序线索二叉树一般不能直接找到后序后继。
• 除非使用三叉链表，或者从根结点开始重新遍历寻找。

若能找到父结点，可以按以下规则判断

1. 如果 p 是父结点的右孩子，则父结点就是 p 的后序后继。
2. 如果 p 是父结点的左孩子，且右兄弟为空，则父结点就是 p 的后序后继。
3. 如果 p 是父结点的左孩子，且右兄弟非空，则 p 的后序后继是右兄弟子树中第一个被后序遍历的结点。
4. 如果 p 是根结点，则 p 没有后序后继。

读图说明

• p 是右孩子，或是没有右兄弟的左孩子时，后继就是父结点；若右兄弟存在，则后继是右兄弟子树中第一个被后序访问的结点。

17.7.4 三种线索二叉树查找能力总结

PDF 总结如下：

补充说明

• “不能直接找”不是绝对找不到。
• 可以用三叉链表中的 parent 指针辅助查找。
• 也可以从根结点开始重新遍历寻找。
• 但若只依赖普通先序或后序线索，通常无法直接得到对应方向的前驱或后继。

17.8 题型：二叉树遍历与线索化

题型一：给树写遍历序列

第一部分：解题方法

1. 先写三种顺序：

先序：根 左 右
中序：左 根 右
后序：左 右 根

2. 对每棵子树也使用同样规则。
3. 不要只看局部，必须递归到每个子树。

第二部分：典型例题

给定二叉树：

        A
      /   \
     B     C
    / \   / \
   D   E F   G

先序遍历

A B D E C F G

中序遍历

D B E A F C G

后序遍历

D E B F G C A

第三部分：知识点复盘

• 根在前就是先序。
• 根在中就是中序。
• 根在后就是后序。
• 每个子树内部仍然按同样规则递归。

题型二：表达式树与表达式转换

第一部分：解题方法

1. 表达式树先序遍历得到前缀表达式。
2. 表达式树中序遍历得到中缀表达式。
3. 表达式树后序遍历得到后缀表达式。
4. 中缀表达式可能需要补括号。

第二部分：典型例题

对表达式： $$ a+b*(c-d)-e/f $$

前缀表达式

-+a*b-cd/ef

中缀表达式

a+b*(c-d)-e/f

后缀表达式

abcd-*+ef/-

第三部分：知识点复盘

• 前缀对应先序。
• 中缀对应中序。
• 后缀对应后序。
• 中缀表达式要注意括号，否则可能改变原表达式含义。

题型三：由遍历序列构造二叉树

第一部分：解题方法

1. 判断组合中有没有中序序列。
2. 如果没有中序序列，通常不能唯一还原。
3. 如果有中序序列：
   • 前序第一个定根。
   • 后序最后一个定根。
   • 层序第一个定根。
4. 用根在中序序列中划分左右子树。
5. 对左右子树递归。

第二部分：典型例题

已知：

前序：A D B C E
中序：B D C A E

步骤

• 前序第一个 A 是根。
• 中序中：

B D C | A | E

• 左子树为 B D C，右子树为 E。
• 左子树前序为 D B C，所以左子树根为 D。
• 继续划分得到：

      A
    /   \
   D     E
  / \
 B   C

第三部分：知识点复盘

• 中序序列负责划分左右子树。
• 前序、后序、层序负责找根。
• 没有中序，一般无法确定左右边界。

题型四：线索二叉树找前驱后继

第一部分：解题方法

先看是哪一种线索二叉树：

• 中序线索二叉树：前驱、后继都能直接找。
• 先序线索二叉树：后继能直接找，前驱通常不能直接找。
• 后序线索二叉树：前驱能直接找，后继通常不能直接找。

再看标志位：

• ltag == 1，说明 lchild 是前驱线索。
• ltag == 0，说明 lchild 是左孩子。
• rtag == 1，说明 rchild 是后继线索。
• rtag == 0，说明 rchild 是右孩子。

第二部分：典型例题

例 1 在中序线索二叉树中，若 p->rtag == 1，求 p 的中序后继。

答案

p->rchild

例 2 在中序线索二叉树中，若 p->rtag == 0，求 p 的中序后继。

答案

• 进入 p 的右子树。
• 找该右子树中最左下的结点。

例 3 在先序线索二叉树中，能否直接找先序前驱？

答案

• 通常不能直接找。
• 需要三叉链表，或者从根结点重新遍历。

例 4 在后序线索二叉树中，能否直接找后序后继？

答案

• 通常不能直接找。
• 需要三叉链表，或者从根结点重新遍历。

第三部分：知识点复盘

• 线索指针只在空孩子位置建立。
• 标志位决定指针到底是孩子还是线索。
• 中序线索树最完整，前驱和后继都方便。
• 先序缺前驱，后序缺后继。

相关知识

• 科目导航：数据结构导航
• 阅读顺序：上一篇：二叉树常考性质 · 下一篇：树、森林
• 关联专题：二叉树代码

17.9 本节复盘

遍历顺序

遍历复杂度

构造二叉树 下表讨论的是只给出结点关键字序列、且各结点关键字互异的常见考试口径；若关键字重复，前序/后序/层序与中序的组合一般也不能仅凭关键字值保证唯一重建。

线索标志

线索二叉树查找能力

易错点

• 中序遍历不是“根在中间写一次”那么简单，每棵子树都要递归执行左-根-右。
• 前序和后序不能直接确定左右子树边界，通常必须配合中序。
• 高效的逐结点层次遍历通常用队列；它不是按先、中、后序递归调用栈得到的顺序。
• 线索化时，只有空指针才能改成线索。
• ltag 和 rtag 不看清，容易把线索当孩子继续遍历。
• 先序线索化时，若 ltag == 1，不能继续递归 lchild。
• 后序线索二叉树找后继通常需要父结点信息。