遍历二叉树与线索二叉树.ppt

6.3 遍历二叉树和线索二叉树,6.3.1 遍历二叉树,遍历定义： 遍历用途： 遍历方法：,指按某条搜索路线遍访每个结点且不重复（又称周游）。,它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。,对每个结点的查看通常都是“先左后右”。（无论是先序、中序还是后序）,例1：,先序遍历的结果是： 中序遍历的结果是： 后序遍历的结果是：,D B E A C D E B C A,口诀： DLR先序遍历，即先根再左、右 LDR中序遍历，即先左再根后右 LRD后序遍历，即先左、右再根,A,B,D,E,C,层次遍历：,ABCDE,练习,1、任何一棵二叉树的叶子结点在先序、中序、后序遍历序列中的相对次序不发生改变。（ ）。 2、已知某二叉树的先序序列为ABDCE，它可能的中序序列为（ ） A. BDAEC B. BCADE C. CBADE D. BEACD 3、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac,它的前序遍历序列是（ ） A. acbed B. decab C. deabc D. cedba,4、一棵二叉树结点的（ ）可唯一确定一棵二叉树。 A.先序序列和中序序列 C.后序序列 C.先序序列和后序序列 D.中序序列 5、图示在黑板上。写出其先序序列、中序序列和后序序列。 6、某n0个结点的二叉树的先序序列和后序序列正好相反，则该二叉树一定不是（ ）的二叉树。 A.任一结点无左孩子 B.任一结点无又孩子 C.深度为n D.存在度为2的结点,练习,a,b,a,d,e,f,g,f,f,n个结点,.,.,.,.,.,例2：画出所有中序遍历序列和后序遍历序列一致的 二叉树的所有形态.,分析：中序遍历: LDR-LD 后序遍历: LRD-LD . .,练习,7、（ ）的二叉树先序遍历和中序遍历正好相同. （ ）的二叉树后序遍历和中序遍历正好相同.（ ）的二叉树先序遍历和中序遍历正好相反.（ ）的二叉树后序遍历和中序遍历正好相反.前序和后序遍历结果相同的二叉树（ ）. 8、对二叉树的结点从1开始连续编号，要求每个结点的编号大于其左孩子（如果有的话）的编号，而小于其右孩子（如果有的话）的编号，则可以采用（ ）次序的遍历实现二叉树的结点编号。 A.先序 B.中序 C.后序 D.层序遍历,由此可以看出： （1）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列； （2）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。,先序遍历递归算法： DLR ( BiTree T ) if (T) /非空二叉树 printf(“%d”,T-data); /访问根结点D DLR(T-lchild); /递归遍历左子树 DLR(T-rchild); /递归遍历右子树 return(0); ,中序遍历递归算法： LDR(BiTree T) if(T) LDR(T-lchild); printf(“%d”,T-data); LDR(T-rchild); return(0); ,（1） 从前面的三种遍历算法可以知道：如果将printf语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。,对遍历的分析：,后序遍历递归算法 LRD (BiTree T) if(T) LRD(T-lchild); LRD(T-rchild); printf(“%d”,T-data); return(0);,从虚线的出发点到终点的路径 上，每个结点经过3次。,第1次经过时访问，是先序遍历 第2次经过时访问，是中序遍历 第3次经过时访问，是后序遍历,任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的递归遍历很有用。如图：,9、一棵二叉树的中序序列为FEABDC，后序序列为FBADCE,则层序序列为（ ）。 A. ABCDEF B. EFCDBA C. FECDAB D. EFCDAB 10、已知一棵二叉树的先序遍历结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树，并写出其后序遍历的结果。,练习,11、中序：DBAEGCF,后序：DBGEFCA,画出二叉树并写出其前序遍历序列。 12、前序：ABCDEFGHIJ, 中序：CBAEFDIHJG,画出二叉树并写出后序序列。 13、先序：ABDEHCFIMGJKL, 中序：DBHEAIMFCGKLJ,画出二叉树，写出后序。,练习,练习,14、某二叉树先序遍历序列是eadcbjfghi,中序遍历序列为acbdjefhgi,画出二叉树，并写出它的后序遍历序列。 15、设一棵二叉树的先序序列为123456789，其中序序列为231547869，试画出该二叉树，并写出它的后序序列。 16、假设一棵二叉树的先序序列为abdficegh,中序序列为bfidagehc,请画出该二叉树，并写出后序序列。,先序遍历结果： + * * / A B C D E 前缀表示法 （波兰式） 中序遍历结果： A / B * C * D + E 中缀表示法 后序遍历结果： A B / C * D * E + 后缀表示法 （逆波兰式）,例3：用二叉树表示算术表达式,层次遍历结果： +*E*D/CAB,练习,17、图示出表达式(A-B*C)*(D+E/F)的二叉树表示。 18、将算术表达式(a+b)+c*(d+e)+f)*(g+h)转化为二叉树。 19、设a=6，b=4，c=2，d=3，e=2，则后缀表达式abc-/de*+的值为（ ）,这就是线索二叉树（Threaded Binary Tree）,二叉树中容易找到结点的左右孩子信息，但该结点在某一序列中的直接前驱和直接后继只能在某种遍历过程中动态获得。 先依遍历规则把每个结点某一序列中对应的前驱和后继线索预存起来，这叫做“线索化”。 意义：从任一结点出发都能快速找到其某一序列中前驱和后继，且不必借助堆栈。,线索二叉树（Threaded Binary Tree）, 每个结点增加两个域：fwd和bwd；,如何预存这类信息？有两种解决方法：, 与原有的左右孩子指针域“复用”，充分利用那n+1个空链域。,规 定：,1）若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱(即线索)；,2）若结点有右子树，则rchild指向其右 孩子；否则，rchild指向其直接后继(即线索) 。,缺点：空间效率太低！,如何判断是孩子指针还是线索指针？,如何区别？,约定:,当Tag域为0时,表示孩子情况;,当Tag域为1时,表示线索情况.,前驱(后继),左(右)孩子,为区别两种不同情况，特增加两个标志域：,问：增加了前驱和后继等线索有什么好处？,能方便找出当前结点的前驱和后继，不用堆栈（递归）也能遍历整棵树。,有关线索二叉树的几个术语：,线索链表： 线 索： 线索二叉树： 线 索 化：,用含Tag的结点样式所构成的二叉链表。 指向结点前驱和后继的指针。 加上线索的二叉树。 对二叉树以某种次序遍历使其变为线索二叉树的过程。,线索化过程就是在遍历过程中修改空指针的过程：课本P127图6.8 将空的lchild改为结点的直接前驱； 将空的rchild改为结点的直接后继。 非空指针呢？仍然指向孩子结点（称为“正常情况”）,20、已知一个二叉树的中序序列为CBEDAHGIJF,后序