Okay, three, two, one, let's jam

503 二叉树的遍历和线索二叉树

13 min read

二叉树的遍历和线索二叉树

二叉树的遍历

二叉树的遍历方式主要有前序遍历、中序遍历、后序遍历和层次遍历。它们分别代表了不同的节点访问顺序。

即访问根结点在前、中、后的顺序。

前序遍历

概念： 前序遍历（Preorder Traversal）的顺序是：先访问根节点，然后遍历左子树，最后遍历右子树。 可以记作 根左右。

算法 PreOrder(T)
输入：二叉树T
输出：前序遍历序列
begin
    if T ≠ NULL then
        访问根节点T
        PreOrder(T->left)   // 递归遍历左子树
        PreOrder(T->right)  // 递归遍历右子树
    endif
end

中序遍历

概念： 中序遍历（Inorder Traversal）的顺序是：先遍历左子树，然后访问根节点，最后遍历右子树。 可以记作 左根右。

算法 InOrder(T)
输入：二叉树T
输出：中序遍历序列
begin
    if T ≠ NULL then
        InOrder(T->left)    // 递归遍历左子树
        访问根节点T
        InOrder(T->right)   // 递归遍历右子树
    endif
end

后序遍历

概念： 后序遍历（Postorder Traversal）的顺序是：先遍历左子树，然后遍历右子树，最后访问根节点。 可以记作 左右根。

算法 PostOrder(T)
输入：二叉树T
输出：后序遍历序列
begin
    if T ≠ NULL then
        PostOrder(T->left)   // 递归遍历左子树
        PostOrder(T->right)  // 递归遍历右子树
        访问根节点T
    endif
end

层次遍历

概念： 层次遍历（Level Order Traversal）按照树的层次从上到下，每层从左到右的顺序访问节点。

实现层次遍历需要借助队列。

算法 LevelOrder(T)
输入：二叉树T
输出：层次遍历序列
begin
    初始化队列Q
    if T ≠ NULL then T入队Q
    while 队列Q非空 do
        p = 队列Q的队头元素并出队
        访问节点p
        if p->left ≠ NULL then p->left入队Q
        if p->right ≠ NULL then p->right入队Q
    endwhile
end

由遍历序列构造二叉树

  • 中序 + 先序、后续、层序任一序列，可以唯一确定二叉树
  • 先序、后续、层序任二序列两两组合，不能唯一确定二叉树

中序 + 先序

基本思路：

  • 先序遍历的第一个节点是根节点
  • 在中序遍历中找到根节点位置，将序列分为左子树和右子树
  • 递归构造左右子树

构造步骤：

  1. 先序序列第一个元素为根节点
  2. 在中序序列中定位根节点位置 k
  3. 中序序列 [0, k-1] 为左子树，[k+1, n-1] 为右子树
  4. 先序序列 [1, k] 为左子树，[k+1, n-1] 为右子树
  5. 递归构造左右子树

时间复杂度：O(n²)（每次查找根节点位置） 空间复杂度：O(n)（递归栈深度）

中序 + 后序

基本思路：

  • 后序遍历的最后一个节点是根节点
  • 在中序遍历中找到根节点位置，划分左右子树
  • 递归构造左右子树

构造步骤：

  1. 后序序列最后一个元素为根节点
  2. 在中序序列中定位根节点位置 k
  3. 中序序列 [0, k-1] 为左子树，[k+1, n-1] 为右子树
  4. 后序序列 [0, k-1] 为左子树，[k, n-2] 为右子树
  5. 递归构造左右子树

时间复杂度：O(n²) 空间复杂度：O(n)

中序 + 层序

基本思路：

  • 层序遍历的第一个节点是根节点
  • 在中序遍历中找到根节点位置，划分左右子树
  • 将层序序列中的节点按照中序划分分配到左右子树
  • 递归构造左右子树

构造步骤：

  1. 层序序列第一个元素为根节点
  2. 在中序序列中定位根节点位置 k
  3. 中序序列 [0, k-1] 为左子树节点集合，[k+1, n-1] 为右子树节点集合
  4. 遍历层序序列，将节点分配到对应的左右子树层序序列中
  5. 递归构造左右子树

时间复杂度：O(n²) 空间复杂度：O(n)

先序 + 后序

无法唯一确定的原因：

  • 对于只有一个子树的节点，无法确定是左子树还是右子树
  • 缺少中序遍历提供的左右子树边界信息

反例：

先序：A B    后序：B A

可能的二叉树：

  A           A
 /             \
B               B

先序 + 层序

无法唯一确定的原因：

  • 层序遍历只能确定节点的层次关系
  • 无法确定同层节点之间的左右位置关系
  • 缺少子树边界的明确划分

后序 + 层序

无法唯一确定的原因：

  • 后序遍历和层序遍历都无法提供明确的左右子树划分信息
  • 对于具有相同结构但左右子树位置不同的二叉树，其后序和层序遍历可能相同

重要结论：

  • 中序遍历是关键：只有包含中序遍历的组合才能唯一确定二叉树
  • 中序遍历提供了左右子树的明确边界信息
  • 其他遍历方式的组合由于缺乏边界信息，存在构造歧义性

二叉树线索化

二叉树的线索化是一种利用二叉链表中的空指针域来存放指向结点在特定遍历次序下的前驱和后继结点的指针的技术。这样做可以方便地查找结点的前驱和后继，而无需再次执行遍历算法，从而提高某些操作（如非递归遍历）的效率。

线索二叉树概念

  • 空指针利用：在一个有 n 个结点的二叉链表中，存在 n+1 个空指针域 (每个结点 2 个指针，共 2n 个指针，其中 n-1 条边占用了 n-1 个指针，所以空指针为 2n - (n-1) = n+1)。
  • 线索：这些被利用起来指向前驱或后继结点的指针称为 ” 线索 ”。
  • 线索链表与线索二叉树：加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。
  • 遍历次序：线索化可以根据不同的遍历次序进行，如前序线索二叉树、中序线索二叉树和后序线索二叉树。中序线索二叉树最为常用。

线索链表的结点结构

为了区分指针域是指向孩子结点还是指向线索，需要在结点结构中增加两个标志位：LTag 和 RTag。

typedef enum {
    Link,   // 0，表示指针指向孩子
    Thread  // 1，表示指针是线索
} PointerTag;
 
typedef struct BiThrNode {
    char data;                      // 结点数据
    struct BiThrNode *lchild, *rchild; // 左右孩子指针
    PointerTag LTag;                // 左标志
    PointerTag RTag;                // 右标志
} BiThrNode, *BiThrTree;
  • 当 LTag 为 Link (0) 时，lchild 指向结点的左孩子；当 LTag 为 Thread (1) 时，lchild 指向结点的前驱。
  • 当 RTag 为 Link (0) 时，rchild 指向结点的右孩子；当 RTag 为 Thread (1) 时，rchild 指向结点的后继。

二叉树线索化流程（以中序线索化为例）

基本思路：按照中序遍历的顺序访问结点，对于每个结点，如果其左指针域为空，则让其指向前驱结点；如果其右指针域为空，则让其指向后继结点。

线索化算法：

全局变量：pre = NULL  // 指向当前访问结点的前驱
 
InThreading(p):
    if p != NULL then
        InThreading(p->lchild)         // 线索化左子树
      
        // 处理当前结点的前驱线索
        if p->lchild == NULL then      // 左指针域为空
            p->LTag = Thread           // 设为线索
            p->lchild = pre           // 指向前驱
        else
            p->LTag = Link            // 设为孩子指针
      
        // 处理前驱结点的后继线索
        if pre != NULL and pre->rchild == NULL then
            pre->RTag = Thread        // 设为线索
            pre->rchild = p          // 指向当前结点（后继）
        else if pre != NULL then
            pre->RTag = Link         // 设为孩子指针
      
        pre = p                      // 更新前驱为当前结点
        InThreading(p->rchild)       // 线索化右子树

完整线索化过程：

  1. 初始化 pre 为 NULL
  2. 递归进行中序线索化
  3. 为了便于遍历，通常添加头结点，使线索二叉树成为双向线索链表

中序线索二叉树的遍历

查找中序后继结点：

InOrderNext(p):
    if p->RTag == Thread then      // 右指针是线索
        return p->rchild          // 直接返回后继
    else                          // 右指针指向右孩子
        q = p->rchild            // 进入右子树
        while q->LTag == Link do  // 找最左结点
            q = q->lchild
        return q

查找中序前驱结点：

InOrderPre(p):
    if p->LTag == Thread then      // 左指针是线索
        return p->lchild          // 直接返回前驱
    else                          // 左指针指向左孩子
        q = p->lchild            // 进入左子树
        while q->RTag == Link do  // 找最右结点
            q = q->rchild
        return q

中序遍历线索二叉树：

InOrderTraverse(T):
    p = FirstNode(T)             // 找到中序遍历的第一个结点
    while p != NULL do
        visit(p)
        p = InOrderNext(p)       // 找后继结点
 
FirstNode(T):                    // 找中序遍历的第一个结点
    while T->LTag == Link do     // 一直向左走
        T = T->lchild
    return T

先序线索二叉树和后序线索二叉树

先序线索二叉树

特点：

  • 先序遍历的第一个结点是根结点
  • 查找先序后继相对复杂，需要区分多种情况

查找先序后继：

PreOrderNext(p):
    if p->RTag == Thread then      // 右指针是线索
        return p->rchild          // 直接返回后继
    else if p->LTag == Link then   // 有左孩子
        return p->lchild          // 左孩子是后继
    else                          // 无左孩子，有右孩子
        return p->rchild          // 右孩子是后继

后序线索二叉树

特点：

  • 后序遍历的最后一个结点是根结点
  • 查找后序前驱相对复杂，需要区分多种情况

查找后序前驱：

PostOrderPre(p):
    if p->LTag == Thread then      // 左指针是线索
        return p->lchild          // 直接返回前驱
    else if p->RTag == Link then   // 有右孩子
        return p->rchild          // 右孩子是前驱
    else                          // 无右孩子，有左孩子
        return p->lchild          // 左孩子是前驱

线索指向问题

关键问题：

  1. 遍历顺序的影响：不同遍历顺序下，同一结点的前驱后继关系不同
  2. 边界处理：第一个和最后一个结点的前驱后继处理
  3. 标志位设置：正确设置 LTag 和 RTag 以区分指针类型

优势：

  • 空间利用率高：充分利用空指针域
  • 遍历效率高：O(1) 时间复杂度查找前驱后继
  • 便于非递归遍历：避免使用栈结构

Graph View

Backlinks