6.3遍历二叉树和线索二叉树.pptVIP

6.3 遍历二叉树和线索二叉树;6.3.1 遍历二叉树;例1：;练习;4、一棵二叉树结点的（ ）可唯一确定一棵二叉树。 A.先序序列和中序序列 C.后序序列 C.先序序列和后序序列 D.中序序列 5、图示在黑板上。写出其先序序列、中序序列和后序序列。 6、某n0个结点的二叉树的先序序列和后序序列正好相反，则该二叉树一定不是（ ）的二叉树。 A.任一结点无左孩子 B.任一结点无又孩子 C.深度为n D.存在度为2的结点;a;练习;由此可以看出： （1）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列； （2）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。 ;中序遍历递归算法： LDR(BiTree T) { if(T) { LDR(T-lchild); printf(“%d”,T-data); LDR(T-rchild); } return(0); };从虚线的出发点到终点的路径 上，每个结点经过3次。;9、一棵二叉树的中序序列为FEABDC，后序序列为FBADCE,则层序序列为（ ）。 A. ABCDEF B. EFCDBA C. FECDAB D. EFCDAB 10、已知一棵二叉树的先序遍历结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树，并写出其后序遍历的结果。 ;11、中序：DBAEGCF,后序：DBGEFCA,画出二叉树并写出其前序遍历序列。 12、前序：ABCDEFGHIJ, 中序：CBAEFDIHJG,画出二叉树并写出后序序列。 13、先序：ABDEHCFIMGJKL, 中序：DBHEAIMFCGKLJ,画出二叉树，写出后序。;练习;+;练习;这就是线索二叉树（Threaded Binary Tree）;① 每个结点增加两个域：fwd和bwd；;lchild; 有关线索二叉树的几个术语：;20、已知一个二叉树的中序序列为CBEDAHGIJF,后序序列为CEDBHJIGFA. 画出该二叉树，并画出该二叉树的先序线索二叉树。 21、将下图示的二叉树按中序线索化，结点x的右指针指向（ ），y的左指针指向（ ）。 作业：P217-218