数据结构：二叉树的遍历

在前面的文章中，我们介绍了树和二叉树所涉及的基本概念，今天我们来看二叉树的一个重要操作：遍历。

在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者是对树中的全部结点逐一进行处理，这就需要对二叉树进行遍历。

一、遍历二叉树

遍历二叉树（traversing binary tree）是指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。访问的含义很广，可以是对结点做各种处理，包括输出结点的信息，对结点进行运算和修改等。遍历二叉树是二叉树最基本的操作，也是二叉树其他各种操作的基础。

遍历的实质是对二叉树进行线性化的过程，即遍历的结果是将非线性结构的树中结点排成一个线性序列。由于二叉树中的每个结点都可能有两棵子树，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性序列上，从而便于遍历。

1.1、算法描述

根据二叉树的递归定义可知，二叉树由3个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。也就是说，遍历一棵非空二叉树的问题可分解为三个子问题：访问根结点、遍历左子树和遍历右子树。

假如用L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。若限定先左后右，则只有前3种情况，分别称之为先（根）序遍历、中（根）序遍历和后（根）序遍历。基于二叉树的递归定义，可以得出下述三种遍历二叉树的递归算法定义：

（1）先序遍历二叉树的递归定义。若二叉树非空，则依次进行操作：

• 访问根结点；
• 先序遍历左子树；
• 先序遍历右子树；

（2）中序遍历二叉树的递归定义。若二叉树非空，则依次进行操作：

• 中序遍历左子树；
• 访问根结点；
• 中序遍历右子树；

（3）后序遍历二叉树的递归定义。若二叉树非空，则依次进行操作：

• 后序遍历左子树；
• 后序遍历右子树；
• 访问根结点；

1.2、算法实现

1.2.1、递归实现

在有了上述遍历二叉树的递归定义之后，三种遍历算法就很容易实现了。这三种遍历算法，可用如下C语言进行描述：

// 先序遍历二叉树T的递归算法
void PreOrder(BiTree T) {
    // 二叉树为空时返回
    if(T==NULL) return;
    // 访问根结点
    printf("%c",T->data);
    // 先序遍历左子树
    PreOrder(T->lchild);
    // 先序遍历右子树
    PreOrder(T->rchild);
}

// 中序遍历二叉树T的递归算法
void InOrder(BiTree T) {
    // 二叉树为空时返回
    if(T==NULL) return;
    // 中序遍历左子树
    InOrder(T->lchild);
    // 访问根结点
    printf("%c",T->data);
    // 中序遍历右子树
    InOrder(T->rchild);
}

// 后序遍历二叉树T的递归算法
void PostOrder(BiTree T) {
    // 二叉树为空时返回
    if(T==NULL) return;
    // 后序遍历左子树
    PostOrder(T->lchild);
    // 后序遍历右子树
    PostOrder(T->rchild);
    // 访问根结点
    printf("%c",T->data);
}

通过这三种遍历算法得到的遍历序列如下图所示：

为了便于理解递归算法，接下来，我们以先序遍历为例，说明递归算法的执行过程。为了叙述方便，假设先序遍图中，结点旁边的序号是该结点的存储地址。

当一个函数调用先序遍历算法时，首先会以指向二叉树根结点的地址1作为实参，将它传递给算法中的形参T，然后执行算法。在算法执行过程中，总是先先序遍历左子树，此时的右子树并没有得到及时的遍历，所以系统要记住此时右子树的访问地址，等左子树遍历结束后再回来遍历右子树，因此需要用一个工作栈来存储右子树T->rchild的访问地址，假定该工作栈为S。

• 当一开始调用PreOrder函数时，由于T=1不为NULL，因此访问根结点，输出A，然后递归调用PreOrder函数遍历左子树T=2，此时还需要将右子树的地址5存入栈S中，如下图（a）所示。
• T=2不为NULL，访问T指向的结点，输出B，再递归调用PreOrder函数遍历左子树T=3，同时将右子树的地址4存入S中，如下图（b）所示。
• T=3不为NULL，访问T指向的结点，输出D；此时T的左、右子树均为空，所以返回到上一层，遍历T=2的右子树4。
• T=4不为NULL，访问T指向的结点，输出E；此时T的左、右子树均为空，所以继续返回到上一层，遍历T=1的右子树5。
• T=5不为NULL，访问T指向的结点，输出C，由于此时T的左子树为空，因此遍历其右子树T=6。
• T=6不为NULL，访问T指向的结点，输出F，这时T的左、右子树均为空，遍历结束。

遍历过程中，工作栈S的变化情况如下图所示：

上述先序遍历算法的执行步骤，也可通过如下逻辑图来理解：

1.2.2、非递归实现

利用栈可将递归算法改写成非递归算法。比如，从中序遍历递归算法执行过程中递归工作栈的状态可见：

• 工作记录中包含两项，其一是递归调用的语句编号（即返回地址），其二是指向根结点的指针。当栈顶记录中的指针非空时，应遍历左子树，即指向左子树根的指针进栈；
• 若栈顶记录中的指针值为空，则应退至上一层，若是从左子树返回，则应访问当前层（即栈顶记录）中指针所指的根结点；
• 若是从右子树返回，则表明当前层的遍历结束，应继续退栈。

中序遍历的非递归算法的实现步骤为：

• 初始化一个空栈S，指针p指向根结点。
• 申请一个结点空间q，用来存放栈顶弹出的元素。
• 当p非空或者栈S非空时，循环执行以下操作：
  • 如果p非空，则使p进栈，p指向该结点的左孩子；
  • 如果p为空，则弹出栈顶元素并访问根结点，将p指向该结点的右孩子。

相应的算法描述为：

void InOrderTraverse(BiTree T) {
    InitStack(S);
    p=T;
    q=new BiTNode;
    
    while(p||!StackEmpty(S)) {
        // p非空
        if(p) {
            // 根结点指针进栈
            Push(S,p);
            // 遍历左子树
            p=p->lchild;
        }
        // p为空
        else {
            // 退栈
            Pop(S,q);
            // 访问根结点
            count<<q->data;
            // 遍历右子树
            p=q->rchild;
        }
    }
}

1.4、算法分析

无论是递归还是非递归遍历二叉树，因为每个结点被访问一次，则不论按哪一种次序进行遍历，对含n个结点的二叉树，其时间复杂度均为O(n)。所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n，则空间复杂度也为O(n)。

1.5、算法的应用

以二叉链表作为存储结构，创建二叉树

为简化问题，设二叉树中结点的元素均为一个单字符。假设按先序遍历的顺序建立二叉链表，T为指向根结点的指针，对于给定的一个字符序列，依次读入字符，从根结点开始，递归创建二叉树。该算法的实现步骤为：

• 扫描字符序列，读入字符ch。
• 如果ch是一个“#”字符，则表明该二叉树为空树，即T为NULL；否则执行以下操作：
  • 申请一个结点空间T；
  • 将ch赋给T->data；
  • 递归创建T的左子树；
  • 递归创建T的右子树；

相应的算法描述为：

void CreateBiTree(BiTree &T) {
    cin>>ch;
    // 递归结束，创建空树
    if(ch=='#') T=NULL;
    // 递归创建二叉树
    else {
        // 生成根结点
        T=new BiTNode;
        // 根结点数据域置为ch
        T->data=ch;
        // 递归创建左子树
        CreateBiTree(T->lchild);
        // 递归创建右子树
        CreateBiTree(T->rchild);
    }
}

复制二叉树

复制二叉树就是利用已有的一棵二叉树复制得到另外一棵与其完全相同的二叉树。

根据二叉树的特点，复制步骤如下：若二叉树不空，则首先复制根结点，这相当于二叉树先序遍历算法中访问根结点的语句；然后分别复制二叉树根结点的左子树和右子树，这相当于先序遍历中递归遍历左子树和右子树的语句。因此，复制函数的实现与二叉树先序遍历的实现非常类似。该算法的实现步骤为：

• 如果是空树，递归结束，否则执行以下操作：
  • 申请一个新节点空间，复制根结点
  • 递归复制左子树；
  • 递归复制右子树；

相应的算法描述为：

void Copy(BiTree T, BiTree &NewT) {
    // 如果为空树，递归结束
    if(T==NULL) {
        NewT=NULL;
        return;
    } else {
        NewT=new BiTNode;
        // 复制根结点
        NewT->data=T->data;
        // 递归复制左子树
        Copy(T->lchild, NewT->lchild);
        // 递归复制右子树
        Copy(T->rchild, NewT->rchild);
    }
}

计算二叉树的深度

二叉树的深度为树中结点的最大层次，二叉树的深度为左右子树深度的较大者加1。该算法的实现步骤为：

• 递归计算左子树的深度记为m；
• 递归计算右子树的深度记为n；
• 如果m大于n，二叉树的深度为m+1，否则为n+1。

相应的算法描述为：

int Depth(BiTree T) {
    // 如果是空树，深度为0，递归结束
    if(T==NULL) return 0;
    else {
        // 递归计算左子树的深度记为m
        m=Depth(T->lchild);
        // 递归计算右子树的深度记为n
        n=Depth(T->rchild);
        // 二叉树的深度为m与n的较大者加1
        if(m>n) return(m+1);
        else return(n+1);
    }
}

显然，计算二叉树的深度是在后序遍历二叉树的基础上进行的运算。

统计二叉树中结点的个数

如果是空树，则结点个数为0；否则，结点个数为左子树的结点个数加上右子树的结点个数再加上1。相应的算法描述为：

int NodeCount(BiTree T) {
    // 如果是空树，则结点个数为0，递归结束
    if(T==NULL) return 0;
    // 否则结点个数为左子树的结点个数 + 右子树的结点个数 + 1
    else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

根据遍历序列确定二叉树

从二叉树的遍历可知，若二叉树中各结点的值均不相同，任意一棵二叉树结点的先序序列、中序序列和后序序列都是唯一的。反过来，若已知二叉树遍历的任意两种序列，能否确定这棵二叉树呢？这样确定的二叉树是否是唯一的呢？

由二叉树的先序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树。

根据定义，二叉树的先序遍历是先访问根结点，其次再按先序遍历方式遍历根结点的左子树，最后按先序遍历方式遍历根结点的右子树。这就是说，在先序序列中，第一个结点一定是二叉树的根结点。

另一方面，中序遍历是先遍历左子树，然后访问根结点，最后再遍历右子树。这样，根结点在中序序列中必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，而后一个子序列是根结点的右子树的中序序列。根据这两个子序列，可以在先序序列中找到对应的左子序列和右子序列。

在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。这样，就确定了二叉树的三个结点。同时，左子树和右子树的根结点又可以分别把左子序列和右子序列划分成两个子序列，如此递归下去，当取尽先序序列中的结点时，便可以得到一棵二叉树。

同理，由二叉树的后序序列和中序序列也可唯一地确定一棵二叉树。因为，依据后序遍历和中序遍历的定义，后序序列的最后一个结点，就如同先序序列的第一个结点一样，可将中序序列分成两个子序列，分别为这个结点左子树的中序序列和右子树的中序序列，再拿出后序序列的倒数第二个结点，并继续分割中序序列，如此递归下去，当倒着取尽后序序列中的结点时，便可以得到一棵二叉树。

二、线索二叉树

2.1、基本概念

所谓线索二叉树，是指二叉链表中的每个结点添加了指向其直接前驱和直接后继的指针。

遍历二叉树是以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先序序列、中序序列或后序序列。这实质上是对一个非线性结构进行线性化操作，使每个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。

当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一序列中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到，为此引入线索二叉树来保存这些在动态过程中得到的有关前驱和后继的信息。

虽然可以在每个结点中增加两个指针域来存放在遍历时得到的有关前驱和后继信息，但这样做使得结构的存储密度大大降低。由于有n个结点的二叉链表中必定存在n+1个空链域，因此可以充分利用这些空链域来存放结点的前驱和后继信息。

在线索二叉树中，为了区分一个结点的左、右孩子指针域是指向其孩子的指针还是指向其前趋或后继的线索，可在结点结构中增加两个线索标志域，一个是左线索标志域，用ltag表示，另一个是右线索标志域，用rtag表示。ltag和rtag的取值只能是0和1。在增加了线索标志域以后，结点的结构如下：

其中：

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

在C语言中，线索二叉树的类型描述如下：

typedef struct BiThrNode {
    TElemType data;
    // 左右孩子指针
    struct BiThrNode *lchild, *rchild;
    // 左右标志域
    int LTag,RTag;
}BiThrNode, *BiThrTree;

以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称之为线索二叉树（Threaded Binary Tree）。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

2.2、构造线索二叉树

由于线索二叉树构造的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程就是在遍历的过程中修改空指针的过程，可用递归算法。

对二叉树按照不同的遍历次序进行线索化，可以得到不同的线索二叉树，包括先序线索二叉树、中序线索二叉树和后序线索二叉树。下面重点介绍中序线索化的算法。

为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，而指针p指向当前访问的结点，由此记录下遍历过程中访问结点的先后关系。

首先，我们给出对树中任意一个以结点p为根的子树中序线索化的过程，其算法步骤为：

• 如果p非空，递归线索化左子树。
• 如果p的左孩子为空，则给p加上左线索，将其LTag置为1，让p的左孩子指针指向pre（即其前驱）；否则将p的LTag置为0。
• 如果pre的右孩子为空，则给pre加上右线索，将其RTag置为1，让pre的右孩子指针指向p（即其后继）；否则将pre的RTag置为0。
• 将pre指向刚访问过的结点p，即pre=p。
• 递归线索化右子树。

相应的算法描述为：

void InThreading(BiThrTree p) {
    if(p) {
        // 递归线索化左子树
        InThreading(p->lchild);

        // p的左孩子为空，给p加上左线索
        if(!p->lchild) {
            // 将LTag置为1
            p->LTag=1;
            // p的左孩子指向其前驱pre
            p->lchild=pre;
        } else p->LTag=0;
        // pre的右孩子为空，给pre加右线索
        if(!pre->child) {
            // 将RTag置为1
            pre->RTag=1;
            // p的右孩子指向其后继p
            pre->rchild=p;
        } else p->RTag=0;
        // pre始终指向p的前驱
        pre=p;
        
        // 递归线索化右子树
        InThreading(p->rchild);
    }
}

然后再通过调用该算法完成对整个二叉树的中序线索化。相应的算法描述为：

// 带头结点的二叉树中序线索化
void InOrderThreading(BiThrTree &Thrt, BiThrTree T) {
    // 申请头结点
    Thrt=new BiThrNode;
    // 头结点有左孩子，若树非空，则其左孩子为树根
    Thrt->LTag=0;
    // 头结点的右孩子指针为右线索，初始化时右指针指向自己
    Thrt->RTag=1;
    Thrt->rchild=Thrt;
    // 若树为空，则左指针也指向自己
    if(!T) Thrt->lchild=Thrt;
    else {
        // 头结点的左孩子指向根，pre初始值指向头结点
        Thrt->child=T;
        pre=Thrt;
        // 对以T为根的二叉树进行中序线索化
        InThreading(T);
        // 中序线索化结束后，pre为最右结点，pre的右线索指向头结点
        pre->RTag=1;
        pre->rchild=Thrt;
        // 头结点的右线索指向pre
        Thrt->rchild=pre;
    }
}

2.3、查找某结点的前驱和后继

在有了结点的前驱和后继信息后，在指定次序下查找结点的前驱和后继算法将变得简单。因此，若需经常查找结点在某种遍历序列中的前驱和后继，则应采用线索链表作为存储结构。

下面分3种情况讨论在线索二叉树中如何查找结点的前驱和后继。

在中序线索二叉树中查找

查找指针p所指结点的前驱：

• 若p->LTag为1，则p的左链指向其前驱；
• 若p->LTag为0，则说明p有左子树，结点的前驱是遍历左子树时最后访问的一个结点（左子树中最右下的结点）

查找指针p所指结点的后继：

• 若p->RTag为1，则p的右链指示其后继；
• 若p->RTag为0，说明p有右子树。根据中序遍历的规律可知，结点的后继应该是遍历其右子树时访问的第一个结点，即右子树中最左下的结点。

在先序线索二叉树中查找

查找指针p所指结点的前驱：

• 若p->LTag为1，则p的左链指向其前驱；
• 若p->LTag为0，则说明p有左子树。此时p的前驱有以下两种情况：
  • 若p所指结点是其双亲的孩子，则其前驱为其双亲结点；
  • 否则应是其双亲的左子树上先序遍历最后访问到的结点。

查找指针p所指结点的后继：

• 若p->RTag为1，则p的右链指示其后继；
• 若p->RTag为0，说明p有右子树。按先序遍历的规律可知，其后继必为其左子树根（若存在）或右子树根。

在后序线索二叉树中查找

查找指针p所指结点的前驱：

• 若p->LTag为1，则p的左链指向其前驱；
• 若p->LTag为0，则p的前驱要分两种情况进行讨论：
  • 当p->RTag为0，说明p有左右子树。根据后序遍历的规律可知，结点的前驱应是遍历其右子树时最后访问的那个结点，即右子树根，也就是p的右链所指向的结点；
  • 当p->RTag为1，说明p有左子树，没有右子树。根据后序遍历的规律可知，结点的前驱应是遍历其左子树时最后访问的那个结点，即左子树根，也就是p的左链所指向的结点；

查找指针p所指结点的后继，该运算比较复杂，要分以下情况讨论：

• 若p所指结点是二叉树的根，则其后继为空；
• 若p所指结点是其双亲的右孩子，则其后继为双亲结点；
• 若p所指结点是其双亲的左孩子，且p所指结点没有右兄弟，则其后继为双亲结点；
• 若p所指结点是其双亲的左孩子，且p所指结点有右兄弟，则其后继为其双亲的右子树上按后序遍历访问的第一个结点，即右子树中“最左下”的叶子结点。

综上所述，在先序线索二叉树上查找前驱或在后序线索二叉树上查找后继都比较复杂。此时若有需要，可直接建立含4个指针的线索链表。

2.4、遍历线索二叉树

由于有了结点的前驱和后继的信息，线索二叉树的遍历操作无需设栈，避免了频繁的进栈、出栈，因此在时间和空间上都较遍历二叉树节省。

遍历某种次序的线索二叉树，只要从该次序下的根结点出发，反复查找其在该次序下的后继，直到叶子结点。下面以遍历中序线索二叉树为例介绍该算法。

遍历中序线索二叉树的算法步骤为：

• 指针p指向根结点
• p为非空树或遍历未结束时，循环执行以下操作：
  • 沿左孩子向下，找到最左下的叶子结点*p，即中序遍历的第一结点；
  • 访问*p；
  • 沿右线索反复查找当前结点*p的后继结点并访问后继结点，直至右线索为0或遍历结束。
• 转向p的右子树

相应的算法描述为：

void InOrderTraverse_Thr(BiThrTree T) {
    // p指向根结点
    p=T->lchild;
    
    // 空树或遍历结束时，p==T
    while(p!=T) {
        // 沿左孩子向下
        while(p->LTag==0) p=p->lchild;
        // 访问其左子树为空的结点
        count<<p->data;
        // 沿右线索访问后继结点
        while(p->Rtag==1 && p->rchild!=T) {
            p=p->rchild;
            count<<p->data;
        }
        // 转向p的右子树
        p=p->rchild;
    }
}

遍历线索二叉树的时间复杂度为O(n)，空间复杂度为O(1)，这是因为线索二叉树的遍历不需要使用栈来实现递归操作。

三、小结

二叉树的遍历算法是其他运算的基础。通过遍历得到了二叉树中结点访问的线性序列，实现了非线性结构的线性化。根据访问结点的次序不同有三种遍历方法：先序遍历、中序遍历、后序遍历，时间复杂度均为O(n)。

线索二叉树利用二叉链表中的n+1个空指针域来存放指向某种遍历次序下的前驱结点和后继结点的指针，这些附加的指针就称为“线索”。引入二叉线索树的目的是加快查找结点前驱或后继的速度。

四、参考

《数据结构（C语言版 第2版）》

《数据结构 自考02331》

《数据结构与算法之美》