1. 先序遍历(PreOrder)#

若二叉树为空，则不执行任何操作；否则，

1. 访问根结点：
2. 先序遍历左子树；
3. 先序遍历右子树。

进行先序遍历的递归算法如下：

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

2. 中序遍历(InOrder)#

若二叉树为空，则不执行任何操作；否则，

1. 中序遍历左子树：
2. 访问根结点：
3. 中序遍历右子树。

进行中序遍历的递归算法如下：

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

3. 后序遍历(PostOrder)#

若二叉树为空，则不执行任何操作；否则，

1. 后序遍历左子树：
2. 后序遍历右子树；
3. 访问根结点。

进行后序遍历的递归算法如下：

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

上述三种遍历算法中，递归遍历左右子树的顺序都是固定的，区别仅在于访问根结点的时机不同。不论采用哪种遍历方法，每个结点都被访问一次且仅一次，时间复杂度均为 $O(n)$。在递归实现中，系统工作栈的深度等于树的高度，在最坏情况下(如单支树)，空间复杂度为 $O(n)$。

4. 层次遍历#

层次遍历过程，即从上到下、从左到右逐层访问二叉树中的各结点。

层次遍历需要借助一个队列，其基本思想如下：首先将根结点入队，随后不断出队并访问队头结点，同时将其存在的左右孩子依次加入队尾，直至队列为空。

二叉树的层次遍历算法如下：

1
void LevelOrder(BiTree T){
2
    InitQueue(Q); //初始化辅助队列
3
    BiTree p;
4
    EnQueue(Q,T); //将根结点入队
5
    while(!IsEmpty(Q)) {
6
        DeQueue(Q, p); //队列不空则循环
7
        visit(p); //队头结点出队
8
        if (p->lchild != NULL)
9
            EnQueue(Q, p->lchild); //访问出队结点
10
        if (p->rchild != NULL)
11
            EnQueue(Q, p->rchild); //若左孩子不空，则左孩子入队
12
    }
13
}

读者可将上述层次遍历算法作为一个模板，熟练掌握其执行过程，并达到熟练手写的程度。

NOTE

遍历是二叉树各类操作的基础。例如，对于一棵给定二叉树，求结点的双亲、查找孩子结点、计算树的深度、统计叶结点数、判断两棵二叉树是否相同等操作，本质上都是在某种遍历过程中完成的。因此，必须深入理解并灵活运用各种遍历方法，以解决实际问题。

5. 由遍历序列构造二叉树#

对于一棵给定的二叉树，其先序序列、中序序列、后序序列和层序序列都是唯一确定的。然而，仅凭这四种遍历序列中的任意一种，却无法唯一确定这棵二叉树。但若已知中序序列，并辅以其他三种遍历序列中的任意一种，则可以唯一地重构出该二叉树。

1. 线索二叉树的基本概念#

遍历二叉树是按照特定规则将树中所有结点排列成一个线性序列，从而得到相应的遍历序列。在该序列中，除首尾结点外，每个结点都有唯一的直接前驱和直接后继。

传统的二叉链表结构仅能反映父子关系，无法直接获取结点在某种遍历序列中的前驱或后继。前面提到，在含有n个结点的二叉树中，共有 $n+1$ 个空指针域：每个叶结点贡献2个空指针，每个度为1的结点贡献1个空指针，因此空指针总数为 $2n_0 + n_1$，又 $n_0 = n_2 + 1$，可得空指针总数为 $n_0 + n_1 + n_2 + 1 = n + 1$。由此，自然想到：可否利用这些空指针，直接指向结点在遍历序列中的前驱或后继？若能实现，便可像遍历链表一样高效地遍历二叉树，线索二叉树正是基于这一思想设计的。

具体规定如下：

• 若某结点无左子树，则将 lchild 指向其在指定遍历序列中的前驱结点。
• 若某结点无右子树，则将 rchild 指向其在指定遍历序列中的后继结点。

为区分指针域指向的是孩子还是线索，需在结点结构中增设两个标志域。

标志域 ltag 和 rtag 的含义如下：

• ltag=0 表示 lchild 指向左孩子，ltag=1 表示 lchild 指向前驱。
• rtag=0 表示 rchild 指向右孩子，rtag=1 表示 rchild 指向后继。

线索二叉树的存储结构可定义为：

1
typedef struct ThreadNode{
2
    ElemType data;                          //数据元素
3
    struct ThreadNode *lchild, *rchild;     //左右孩子指针
4
    int ltag, rtag;                         //左右线索标志
5
} ThreadNode, *ThreadTree;

采用上述结构的二叉链表称为线索链表，其中指向前驱或后继的指针称为线索。这种带有线索的二叉树称为线索二叉树。

2. 中序线索二叉树的构造#

二叉树的线索化是指将二叉链表中的空指针域替换为指向前驱或后继的线索。由于结点的前驱和后继关系只能在遍历过程中确定，因此线索化本质上就是对二叉树进行一次遍历。

以中序线索二叉树的构造为例：设指针 pre 指向刚刚访问过的结点，指针 p 指向当前正在访问的结点，pre 即为 p 的中序前驱。在中序遍历过程中：检查 p 的左指针是否为空，若为空则令其指向 pre；检查 pre 的右指针是否为空，若为空则令其指向 p。

通过中序遍历对二叉树线索化的递归算法如下：

1
void InThread(ThreadTree &p, ThreadTree &pre){
2
    if(p!=null){
3
        InThread(p->lchild, pre);   //递归，线索化左子树
4
        if (p->lchild==NULL) {      //当前结点的左子树为空
5
            p->lchild=pre;          //建立当前结点的前驱线索
6
            p->ltag=1;
7
        }
8
        if (pre!=NULL&&pre->rchild==NULL) {//前驱结点非空且其右子树为空
9
            pre->rchild=p;          //建立前驱结点的后继线索
10
            pre->rtag=1;
11
        }
12
        pre=p;                      //标记当前结点成为刚刚访问过的结点
13
        InThread(p->rchild, pre);   //递归，线索化右子树
14
    }
15
}

建立中序线索二叉树的主过程如下：

1
void CreateInThread(ThreadTree T) {
2
    ThreadTree pre = NULL;
3
    if (T != NULL) {        // 非空二叉树，线索化
4
        InThread(T, pre);   // 线索化二叉树
5
        pre -> rchild = NULL;// 处理遍历的最后一个结点
6
        pre -> rtag = 1;
7
    }
8
}

为方便遍历，可在线索链表上增设一个头结点：其 lchild 指向根结点；rchild 指向中序序列的最后一个结点；中序序列的第一个结点的 lchild 和最后一个结点的 rchild 均指向头结点。如此，便形成一个双向循环线索链表，从而支持正向与反向的高效遍历。

3. 中序线索二叉树的遍历#

中序线索二叉树的结点中已隐含前驱和后继信息，因此遍历时无须借助栈或递归。只需先找到中序序列的第一个结点，然后依次查找每个结点的后继，直至后继为空(或回到头结点)。在中序线索二叉树中，查找结点后继的规则如下：若结点的 rtag 为 1，则 rchild 直接指向其后继；若 rtag 为 0，则其后继为右子树中最左下结点(右子树的中序第一个结点)。

不含头结点的中序线索二叉树遍历相关算法如下。

1. 求中序序列中的第一个结点：

1
ThreadNode *Firstnode(ThreadNode *p) {
2
    while (p->ltag==0) p=p->lchild; //沿左孩子链走到最左下结点
3
    return p;
4
}

2. 求结点p在中序序列中的后继：

1
ThreadNode *Nextnode(ThreadNode *p) {
2
    if (p->rtag==0) return Firstnode(p->rchild); //右子树中最左下结点
3
    else return p->rchild; //若rtag==1则直接返回后继线索
4
}

请读者自行完成求中序序列中的最后一个结点和结点 p 的中序前驱的运算。

3. 利用上面两个算法，可实现非递归的中序遍历：

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

4. 先序线索二叉树和后序线索二叉树#

建立先序或后序线索二叉树的方法与中序类似，只需调整递归调用顺序及线索建立的位置。以二叉树为例，手工构造先序线索二叉树的过程如下(先序序列为 ABCDF，依次处理每个结点，若其左或右指针为空，则将其替换为对应前驱或后继的线索)：

结点 A、B 均有左右孩子，无须修改指针；结点 C 无左孩子，将其 lchild 指向前驱 B，无右孩子，将其 rchild 指向后继 D；结点 D 无左孩子，将其 lchild 指向前驱 C，无右孩子，将其 rchild 指向后继 F；结点 F 无左孩子，将其 lchild 指向前驱 D，无右孩子且无后继，将其 rchild 置为空，最终得到先序线索二叉树。

构造后序线索二叉树的过程类似(后序序列为CDBFA)：

结点 C 无左孩子且无前驱，将 lchild 置空，无右孩子，将 rchild 指向后继 D；结点 D 无左孩子，将 lchild 指向前驱 C，无右孩子，将 rchild 指向后继 B；结点 F 无左孩子，将 lchild 指向前驱 B，无右孩子，将 rchild 指向后继 A，得到后序线索二叉树。

在先序线索二叉树中查找某结点的后继较为直接：若该结点有左孩子，则左孩子为其后继；若无左孩子但有右孩子，则右孩子为其后继；若为叶结点，则其rchild直接指向后继。

而在后序线索二叉树中查找后继则较为复杂，需要分以下三种情况：

1. 若结点 x 是整棵二叉树的根，则其后继为空；
2. 若结点 x 是其双亲的右孩子，或是其双亲的左孩子且该双亲无右子树，则 x 的后继即为其双亲；
3. 若结点 x 是其双亲的左孩子，且该双亲存在右子树，则 x 的后继为该右子树中按后序遍历访问的第一个结点(右子树中最左下结点)。

值得注意的是，结点B的后继是A，但无法直接通过线索找到后继，需要回溯到其双亲。因此，在后序线索二叉树中高效查找后继通常需要知道结点的父结点信息。为此，通常采用带父指针的三叉链表作为存储结构，而非标准的二叉线索链表。