【数据结构】4. 树与二叉树(4)

注意：
以上三种遍历方式以及算法描述是简单易懂的，读者需要将它们作为模板来记忆，考研中的很多题目都是基于这 3 个模板而延伸出来的。

（4）递归算法和非递归算法的转换

可以借助栈，将二叉树的递归遍历算法转换为非递归算法，下面以中序遍历为例给出中序遍历的非递归算法。
先扫描（并非访问）根结点的所有左结点并将它们一一进栈。
然后出栈一个结点 *p ( 显然结点 *p 没有左孩子结点或者左孩子结点均已访问过），则访问它。
然后扫描该结点的右孩子结点，将其进栈，再扫描该右孩子结点的所有左结点并一一进栈，如此继续，直到栈空为止。
中序遍历的非递归算法如下：

void In0rder2(BiTree T) {
//二叉树中序遍历的非递归算法，算法需要借助一个栈
    InitStack(S); //初始化栈
    BiTree p = T; //p 是遍历指针
    while(p || !IsEmpty(S)) { //栈不空或 p 不空时循环
        if(p) { //根指针进栈，遍历左子树
            Push(S,p); //每遇到非空二叉树先向左走
            p = p->lchild;
        } else { //根指针退栈，访问根结点，遍历右子树
            Pop(S,p); visit(p); //退找，访问根结点
            p = p->rchild; //再向右子树走
        }
    }
}

显然非递归算法的执行效率要高于递归算法。
类似地可以得到先序遍历与后序遍历的非递归算法，其中后序遍历的非递归算法较复杂，留给读者思考。

（5）层次遍历

如图 4-7 所示为二叉树的层次遍历，即按照箭头所指方向，按照 1、2、3、4 的层次顺序，对二叉树中各个结点进行访问。
要进行层次遍历需要借助一个队列。
先将二叉树根结点入队，然后出队，访问该结点，如果它有左子树，则将左子树根结点入队；如果它有右子树，则将右子树根结点入队。
然后出队，对出队结点访问，如此反复，直到队列为空。
二叉树的层次遍历算法如下：

void LevelOrder(BiTree T) {
    InitQueue(Q); //初始化辅助队列
    BiTree p;
    EnQueue(Q,T); //将根结点入队
    while(!IsEmpty(Q)){ //队列不空循环
        DeQueue (Q,p); //队头元素出队
        visit(p); //访问当前 P 所指向结点
        if(p->lchild != NULL)
            EnQueue(Q,p->lchild); //左子树不空，则左子树入队列
        if(p->rchild != NULL)
            EnQueue(Q,p->rchild); //右子树不空，则右子树入队列
    }
}

对于上述二叉树层次遍历的算法，读者在复习过程当中应该将其作为一个模板，在熟练掌握其执行过程的基础上来记忆，并能够达到熟练默写的程度。
这样才能将层次遍历模板应用于各种题目之中。

注意：
遍历是二叉树各种操作的基础，可以在遍历的过程中对结点进行各种操作，例如，对于一棵已知树求结点的双亲、求结点的孩子结点、求二叉树的深度、求二又树的叶子结点个数、判断两棵二叉树是否相同等。
所有这些操作都建立在二叉树遍历的基础上，因此，必须掌握二叉树的各种遍历过程，并能灵活运用以解决各种问题。

（6）由遍历序列构造二叉树

由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树。
在先序遍历序列中，第一个结点一定是二叉树的根结点，
而在中序遍历中，根结点必然将中序序列分割成两个子序列，前个子序列就是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列。
根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。
在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。
如此递归地进行下去，便能唯一地确定这棵二叉树。

同理，由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树，因为后序序列的最后一个结点就如同先序序列的第一个结点，可以将中序序列分割成两个子序列，然后采用类似的方法递归地进行划分，就可以得到一棵二叉树。
由二叉树的层序序列和中序序列也可以唯一地确定一棵二叉树，实现方法留给读者思考。
需要注意的是，如果只知道二叉树的先序序列和后序序列，则无法唯一确定一棵二义树。

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

4.3.2 线索二叉树

（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指向其后继结点。
如图 4-9 所示，还需要增加两个标志域表明当前指针域所指对象是指向左（右）子结点还是直接前驱（后继）。

（编辑：ASP站长网）