遍历二叉树与线索二叉树

《遍历二叉树与线索二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.3遍历二叉树和线索二叉树6.3.1遍历二叉树遍历定义：遍历用途：遍历方法：指按某条搜索路线遍访每个结点且不重复（又称周游）。它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。对每个结点的查看通常都是“先左后右”。（无论是先序、中序还是后序）例1：先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：ABCDEDBEACDEBCA口诀：DLR—先序遍历，即先根再左、右LDR—中序遍历，即先左再根后右LRD—后序遍历，即先左、右再根ABDEC层次遍历：ABCDE练习1、任何一棵二叉树的叶子结点在先序、中序、后序遍历序列中的相对

2、次序不发生改变。（）。2、已知某二叉树的先序序列为ABDCE，它可能的中序序列为（）A.BDAECB.BCADEC.CBADED.BEACD3、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac,它的前序遍历序列是（）A.acbedB.decabC.deabcD.cedba4、一棵二叉树结点的（）可唯一确定一棵二叉树。A.先序序列和中序序列C.后序序列C.先序序列和后序序列D.中序序列5、图示在黑板上。写出其先序序列、中序序列和后序序列。6、某n>0个结点的二叉树的先序序列和后序序列正好相反，则该二叉树一定不是（）的二叉树。A.任一结点无左孩

3、子B.任一结点无又孩子C.深度为nD.存在度为2的结点练习abadefgffn个结点….....例2：画出所有中序遍历序列和后序遍历序列一致的二叉树的所有形态.分析：中序遍历:LDR---LD后序遍历:LRD---LD..练习7、（）的二叉树先序遍历和中序遍历正好相同.（）的二叉树后序遍历和中序遍历正好相同.（）的二叉树先序遍历和中序遍历正好相反.（）的二叉树后序遍历和中序遍历正好相反.前序和后序遍历结果相同的二叉树（）.8、对二叉树的结点从1开始连续编号，要求每个结点的编号大于其左孩子（如果有的话）的编号，而小于其右孩子（如果有的话）的编号，则可以采用（

4、）次序的遍历实现二叉树的结点编号。A.先序B.中序C.后序D.层序遍历由此可以看出：（1）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列；（2）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。先序遍历递归算法：DLR(BiTreeT){if(T)//非空二叉树{printf(“%d”,T->data);//访问根结点DDLR(T->lchild);//递归遍历左子树DLR(T->rchild);//递归遍历右子树}return(0);}中序遍历递归算法：LDR(BiTreeT){if(T){LDR(T->lchild);

5、printf(“%d”,T->data);LDR(T->rchild);}return(0);}（1）从前面的三种遍历算法可以知道：如果将printf语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。对遍历的分析：后序遍历递归算法LRD(BiTreeT){if(T){LRD(T->lchild);LRD(T->rchild);printf(“%d”,T->data);}return(0);}从虚线的出发点到终点的路径上，每个结点经过3次。AFEDCBG第1次经过时访问，是先序遍历第2次经过时访

6、问，是中序遍历第3次经过时访问，是后序遍历任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的递归遍历很有用。如图：9、一棵二叉树的中序序列为FEABDC，后序序列为FBADCE,则层序序列为（）。A.ABCDEFB.EFCDBAC.FECDABD.EFCDAB10、已知一棵二叉树的先序遍历结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树，并写出其后序遍历的结果。练习11、中序：DBAEGCF,后序：DBGEFCA,画出二叉树并写出其前序遍历序列。12、前序：ABCDEFG

7、HIJ,中序：CBAEFDIHJG,画出二叉树并写出后序序列。13、先序：ABDEHCFIMGJKL,中序：DBHEAIMFCGKLJ,画出二叉树，写出后序。练习练习14、某二叉树先序遍历序列是eadcbjfghi,中序遍历序列为acbdjefhgi,画出二叉树，并写出它的后序遍历序列。15、设一棵二叉树的先序序列为123456789，其中序序列为231547869，试画出该二叉树，并写出它的后序序列。16、假设一棵二叉树的先序序列为abdficegh,中序序列为bfidagehc,请画出该二叉树，并写出后序序列。+*A*/EDCB先序遍历结果：+**/A

8、BCDE—前缀表示法（波兰式）中序遍历结果：A/B*C*D+E—中