王道408考研数据结构-树与二叉树-第五章-第三四节

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

5.3.1 二叉树的遍历

1.先序遍历(PreOrder)

对应的递归算法如下：

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

2.中序遍历(InOrder)

对应的递归算法如下：

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

3.后序遍历(PostOrder)

对应的递归算法如下：

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

4.递归算法和非递归算法的转换

    图5.10用带箭头的虚线表示了这三种遍历算法的递归执行过程。其中，向下的箭头表示更深一层的递归调用，向上的箭头表示从递归调用退出返回；虚线旁的三角形、圆形和方形内的字符分别表示在先序、中序和后序遍历的过程中访问根结点时输出的信息。例如，由于中序遍历中访问结点是在遍历左子树之后、遍历右子树之前进行的，则带圆形的字符标在向左递归返回和向右递归调用之间。由此，只要沿虚线从1出发到2结束，将沿途所见的三角形(或圆形或方形)内的字符记下，便得到遍历二叉树的先序(或中序或后序)序列。例如，在图5.10中，沿虚线游走可以分别得到先序序列为ABDEC、中序序列为 DBEAC、后序序列为 DEBCA。 

    借助栈的思路，我们来分析中序遍历的访问过程： 

    ①沿着根的左孩子，依次入栈，直到左孩子为空，说明已找到可以输出的结点，此时栈内元素依次为 ABD。②栈顶元素出栈并访问：若其右孩子为空，继续执行②;若其右孩子不空，将右子树转执行①。栈顶D出栈并访问，它是中序序列的第一个结点；D右孩子为空，栈顶B出栈并访问；B右孩子不空，将其右孩子E入栈，E左孩子为空，栈顶E出栈并访问；E右孩子为空，栈顶A出栈并访问；A右孩子不空，将其右孩子C入栈，C左孩子为空，栈顶C出栈并访问。由此得到中序序列 DBEAC。读者可根据上述分析画出遍历过程的出入栈示意图。 

根据分析可以写出中序遍历的非递归算法如下：

void InOrder2(BiTree T)(
    InitStack(S);BiTree p=T;//初始化栈 s;p是遍历指针 
    while(p||!IsEmpty(S)){//栈不空或p不空时循环 
        if(p){ //一路向左
            Push(S,p);//当前结点入栈 
            p=p->lchild;//左孩子不空，一直向左走 
        }
        else{ //出栈，并转向出栈结点的右子树
            Pop(S,p);visit(p); //栈顶元素出栈，访问出栈结点
            p=p->rchild; //向右子树走，p赋值为当前结点的右孩子
        }//返回while 循环继续进入if-else 语句 1
    }
}

5,层次遍历

    图5.11所示为二叉树的层次遍历，即按照箭头所指方向，按照1,2,3,4的层次顺序，自上而下，从左至右，对二叉树中的各个结点进行逐层访问。

    进行层次遍历，需要借助一个队列。层次遍历的思想如下：①首先将二叉树的根结点入队。②若队列非空，则队头结点出队，访问该结点，若它有左孩子，则将其左孩子入队：若它有右孩子，则将其右孩子入队。③重复②步，直至队列为空。 

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

void Level0rder(BiTree T){
    InitQueue(Q);
    BiTree p;
    EnQueue (Q,T);
    while(!IsEmpty(Q)){
        DeQueue(Q,p);
        visit(p);
        if(p->lchild!=NULL)
            EnQueue(Q,p->1child)
        if(p->rchild!=NULL)
        EnQueue(Q,p->rchild);

    }
}

6.由遍历序列构造二叉树

    对于一棵给定的二叉树，其先序序列、中序序列、后序序列和层序序列都是确定的。然而，只给出四种遍历序列中的任意一种，却无法唯一地确定一棵二叉树。若已知中序序列，再给出其他三种遍历序列中的任意一种，就可以唯一地确定一棵二叉树。 

    (1)由先序序列和中序序列构造二叉树

    在先序序列中，第一个结点一定是二叉树的根结点；而在中序遍历中，根结点必然将中序序列分割成两个子序列，前一个子序列是根的左子树的中序序列，后一个子序列是根的右子树的中序序列。左子树的中序序列和先序序列的长度是相等的，右子树的中序序列和先序序列的长度是相等的。根据这两个子序列，可以在先序序列中找到左子树的先序序列和右子树的先序序列，如图 5.12 所示。如此递归地分解下去，便能唯一地确定这棵二叉树。 

    例如，求先序序列(ABCDEFGHI)和中序序列(BCAEDGHFI)所确定的二叉树。首先，由先序序列可知A为二叉树的根结点。中序序列中A之前的BC为左子树的中序序列，EDGHFI为右子树的中序序列。然后，由先序序列可知B是左子树的根结点，D是右子树的根结点。以此类推，就能将剩下的结点继续分解下去，最后得到的二叉树如图5.13(c)所示。 

5.3.2 线索二叉树

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

    遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点(第一个和最后一个除外)都有一个直接前驱和直接后继。 

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

    二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树。 

    以中序线索二叉树的建立为例。附设指针 pre 指向刚刚访问过的结点，指针 p指向正在访问的结点，即 pre指向p的前驱。在中序遍历的过程中，检查p的左指针是否为空，若为空就将它指向pre:检查pre的右指针是否为空，若为空就将它指向 p,如图5.18 所示。

5.4 树、森林

5.4.1 树的存储结构

1.双亲表示法

    这种存储结构采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。如图5.21所示，根结点下标为0,其伪指针域为-1。 

    双亲表示法利用了每个结点(根结点除外)只有唯一双亲的性质，可以很快地得到每个结点的双亲结点，但求结点的孩子时则需要遍历整个结构。  

2、孩子表示法

    孩子表示法是将每个结点的孩子结点视为一个线性表，且以单链表作为存储结构，则n个结点就有n个孩子链表(叶结点的孩子链表为空表)。而n个头指针又组成一个线性表，为便于查找，可采用顺序存储结构。图 5.22(a)是图 5.21(a)中的树的孩子表示法。

    与双亲表示法相反，孩子表示法寻找孩子的操作非常方便，而寻找双亲的操作则需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。  

3.孩子兄弟表示法

    孩子兄弟表示法又称二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针，以及指向结点下一个兄弟结点的指针(沿此域可以找到结点的所有兄弟结点),如图5.22(b)所示。

    孩子兄弟表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作，易于查找结点的孩子等，但缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个 parent域指向其父结点，则查找结点的父结点也很方便。 

5.4.2 树、森林与二叉树的转换

    二叉树和树都可以用二叉链表作为存储结构。从物理结构上看，树的孩子兄弟表示法与二叉树的二叉链表表示法是相同的，因此可以用同一存储结构的不同解释将一棵树转换为二叉树。 

1.树转换为二叉树

    树转换为二叉树的规则：每个结点的左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则又称“左孩子右兄弟”。由于根结点没有兄弟，因此树转换得到的二叉树没有右子树，如图5.23 所示。

2.森林转换为二叉树

    将森林转换为二叉树的规则与树类似。先将森林中的每棵树转换为二叉树，由于任意一棵树对应的二叉树的右子树必空，若把森林中第二棵树根视为第一棵树根的右兄弟，即将第二棵树对应的二叉树当作第一棵二叉树根的右子树，将第三棵树对应的二叉树当作第二棵二叉树根的右子树，以此类推，就可以将森林转换为二叉树。 

3.二叉树转换为森林

    二叉树转换为森林的规则：若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树形式，所以将根的右链断开。二叉树根的右子树又可视为一个由除第一棵树外的森林转换后的二叉树，应用同样的方法，直到最后只剩一棵没有右子树的二叉树为止，最后将每棵二叉树依次转换成树，就得到了原森林，如图 5.24 所示。二叉树转换为树或森林是唯一的。\