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

6.3 6.3 遍历二叉树遍历二叉树和线索二叉树和线索二叉树6.3.1 6.3.1 遍历二叉树遍历二叉树遍历定义：遍历定义：遍历用途：遍历用途：遍历方法：遍历方法：指按某条搜索路线遍访每个结点且指按某条搜索路线遍访每个结点且不重复（又称周游）。不重复（又称周游）。它是树结构插入、删除、修改、查找它是树结构插入、删除、修改、查找和排序运算的前提，和排序运算的前提，是二叉树一切运是二叉树一切运算的基础和核心。算的基础和核心。对每个结点的查看通常都是对每个结点的查看通常都是“先左后先左后右右”。（无论是先序、中序还是后序）。（无论是先序、中序还是后序）例例1 1：先序先序遍历的结果是：遍历的结果是：中序中序遍历的结果是：遍历的结果是：后序后序遍历的结果是：遍历的结果是：A B CD ED B E A CD B E A CD E B C AD E B C A口诀：口诀：DLR先序遍历，即先根再左、右先序遍历，即先根再左、右LDR中序遍历，即先左再根后右中序遍历，即先左再根后右LRD后序遍历，即先左、右再根后序遍历，即先左、右再根A A B B D D E E C C层次遍历层次遍历：ABCDE练习练习1 1、任何一棵二叉树的叶子结点在先序、中序、后序遍历、任何一棵二叉树的叶子结点在先序、中序、后序遍历、任何一棵二叉树的叶子结点在先序、中序、后序遍历、任何一棵二叉树的叶子结点在先序、中序、后序遍历序列中的相对次序不发生改变。（序列中的相对次序不发生改变。（序列中的相对次序不发生改变。（序列中的相对次序不发生改变。（）。）。）。）。2 2、已知某二叉树的先序序列为、已知某二叉树的先序序列为、已知某二叉树的先序序列为、已知某二叉树的先序序列为ABDCEABDCE，它可能的中序序，它可能的中序序，它可能的中序序，它可能的中序序列为（列为（列为（列为（）A.BDAEC B.BCADE A.BDAEC B.BCADE C.CBADE D.BEACD C.CBADE D.BEACD3 3、已知某二叉树的后序遍历序列是、已知某二叉树的后序遍历序列是、已知某二叉树的后序遍历序列是、已知某二叉树的后序遍历序列是dabecdabec，中序遍历序列，中序遍历序列，中序遍历序列，中序遍历序列是是是是debac,debac,它的前序遍历序列是（它的前序遍历序列是（它的前序遍历序列是（它的前序遍历序列是（）A.acbed B.decab A.acbed B.decab C.deabc D.cedba C.deabc D.cedba4 4、一棵二叉树结点的（、一棵二叉树结点的（、一棵二叉树结点的（、一棵二叉树结点的（）可唯一确定一棵二叉树。）可唯一确定一棵二叉树。）可唯一确定一棵二叉树。）可唯一确定一棵二叉树。A.A.先序序列和中序序列先序序列和中序序列先序序列和中序序列先序序列和中序序列 C.C.后序序列后序序列后序序列后序序列 C.C.先序序列和后序序列先序序列和后序序列先序序列和后序序列先序序列和后序序列 D.D.中序序列中序序列中序序列中序序列5 5、图示在黑板上。写出其先序序列、中序序列和后序、图示在黑板上。写出其先序序列、中序序列和后序、图示在黑板上。写出其先序序列、中序序列和后序、图示在黑板上。写出其先序序列、中序序列和后序序列。序列。序列。序列。6 6、某、某、某、某n0n0个结点的二叉树的先序序列和后序序列正好相个结点的二叉树的先序序列和后序序列正好相个结点的二叉树的先序序列和后序序列正好相个结点的二叉树的先序序列和后序序列正好相反，则该二叉树一定不是（反，则该二叉树一定不是（反，则该二叉树一定不是（反，则该二叉树一定不是（）的二叉树。）的二叉树。）的二叉树。）的二叉树。A.A.任一结点无左孩子任一结点无左孩子任一结点无左孩子任一结点无左孩子 B.B.任一结点无又孩子任一结点无又孩子任一结点无又孩子任一结点无又孩子 C.C.深度为深度为深度为深度为n D.n D.存在度为存在度为存在度为存在度为2 2的结点的结点的结点的结点练习练习abadefgff n个结点个结点.例例2 2：画出所有：画出所有中序中序遍历序列和遍历序列和后序后序遍历序列一致的遍历序列一致的 二叉树的所有形态二叉树的所有形态.分析：中序遍历分析：中序遍历:LDR-LD:LDR-LD 后序遍历后序遍历:LRD-LD.:LRD-LD.练习练习7 7、（、（、（、（）的二叉树先序遍历和中序遍历正好相同）的二叉树先序遍历和中序遍历正好相同）的二叉树先序遍历和中序遍历正好相同）的二叉树先序遍历和中序遍历正好相同.（）的二叉树后序遍历和中序遍历正好相同）的二叉树后序遍历和中序遍历正好相同）的二叉树后序遍历和中序遍历正好相同）的二叉树后序遍历和中序遍历正好相同.（）的二叉树先序遍历和中序遍历正好相反）的二叉树先序遍历和中序遍历正好相反）的二叉树先序遍历和中序遍历正好相反）的二叉树先序遍历和中序遍历正好相反.（）的二叉树后序遍历和中序遍历正好相反的二叉树后序遍历和中序遍历正好相反的二叉树后序遍历和中序遍历正好相反的二叉树后序遍历和中序遍历正好相反.前序和后前序和后前序和后前序和后序遍历结果相同的二叉树（序遍历结果相同的二叉树（序遍历结果相同的二叉树（序遍历结果相同的二叉树（）.8 8、对二叉树的结点从、对二叉树的结点从、对二叉树的结点从、对二叉树的结点从1 1开始连续编号，要求每个结点开始连续编号，要求每个结点开始连续编号，要求每个结点开始连续编号，要求每个结点的编号大于其左孩子（如果有的话）的编号，而小的编号大于其左孩子（如果有的话）的编号，而小的编号大于其左孩子（如果有的话）的编号，而小的编号大于其左孩子（如果有的话）的编号，而小于其右孩子（如果有的话）的编号，则可以采用（于其右孩子（如果有的话）的编号，则可以采用（于其右孩子（如果有的话）的编号，则可以采用（于其右孩子（如果有的话）的编号，则可以采用（）次序的遍历实现二叉树的结点编号。）次序的遍历实现二叉树的结点编号。）次序的遍历实现二叉树的结点编号。）次序的遍历实现二叉树的结点编号。A.A.先序先序先序先序 B.B.中序中序中序中序 C.C.后序后序后序后序 D.D.层序遍历层序遍历层序遍历层序遍历由此可以看出：由此可以看出：由此可以看出：由此可以看出：（1 1 1 1）遍历操作实际上是将非线性结构线性化的过程，）遍历操作实际上是将非线性结构线性化的过程，）遍历操作实际上是将非线性结构线性化的过程，）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列；其结果为线性序列；其结果为线性序列；其结果为线性序列；（2 2 2 2）遍历操作是一个递归的过程，因此，这三种遍历）遍历操作是一个递归的过程，因此，这三种遍历）遍历操作是一个递归的过程，因此，这三种遍历）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。操作的算法可以用递归函数实现。操作的算法可以用递归函数实现。操作的算法可以用递归函数实现。先序遍历递归算法：先序遍历递归算法：先序遍历递归算法：先序遍历递归算法：DLR (BiTree T)if(T)/非空二叉树非空二叉树 printf(“%d”,T-data);/访问根结点访问根结点D 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 3次次。AFEDCBG第第1 1次次经过时访问，是经过时访问，是先序先序遍历遍历第第2 2次次经过时访问，是经过时访问，是中序中序遍历遍历第第3 3次次经过时访问，是经过时访问，是后序后序遍历遍历 任何一棵二叉树都可以将它的外部轮廓用一条线任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的递归遍历很有用。如图：对于理解二叉树的递归遍历很有用。如图：9、一棵二叉树的中序序列为、一棵二叉树的中序序列为FEABDC，后序，后序序列为序列为FBADCE,则层序序列为（则层序序列为（）。）。A.ABCDEF B.EFCDBA C.FECDAB D.EFCDAB10、已知一棵二叉树的先序遍历结果是、已知一棵二叉树的先序遍历结果是ABECDFGHIJ,中序遍历的结果是中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树，并写出试画出这棵二叉树，并写出其后序遍历的结果。其后序遍历的结果。练习练习11、中序：、中序：DBAEGCF,后序：后序：DBGEFCA,画出画出二叉树并写出其前序遍历序列。二叉树并写出其前序遍历序列。12、前序：、前序：ABCDEFGHIJ,中序：中序：CBAEFDIHJG,画出二叉树并写出画出二叉树并写出后序序列。后序序列。13、先序：、先序：ABDEHCFIMGJKL,中序：中序：DBHEAIMFCGKLJ,画出二叉树，画出二叉树，写出后序。写出后序。练习练习练习练习14、某二叉树先序遍历序列是、某二叉树先序遍历序列是eadcbjfghi,中序中序遍历序列为遍历序列为acbdjefhgi,画出二叉树，并写出画出二叉树，并写出它的后序遍历序列。它的后序遍历序列。15、设一棵二叉树的先序序列为、设一棵二叉树的先序序列为123456789，其，其中序序列为中序序列为231547869，试画出该二叉树，并，试画出该二叉树，并写出它的后序序列。写出它的后序序列。16、假设一棵二叉树的先序序列为、假设一棵二叉树的先序序列为abdficegh,中中序序列为序序列为bfidagehc,请画出该二叉树，并写出请画出该二叉树，并写出后序序列。后序序列。+*A*/EDCB先序遍历结果：先序遍历结果：+*/A B C D E前缀表示法前缀表示法（波兰式）（波兰式）中序遍历结果：中序遍历结果：A/B*C*D+E中缀表示法中缀表示法后序遍历结果：后序遍历结果：A B/C*D*E+后缀表示法后缀表示法（逆波兰式）（逆波兰式）例例例例3 3 3 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+1n+1个空链域。个空链域。规规 定：定：1 1）若结点有左子树，则）若结点有左子树，则lchildlchild指向其左指向其左孩子；否则，孩子；否则，lchildlchild指向其直接前驱指向其直接前驱(即即线索线索)；2 2）若结点有右子树，则）若结点有右子树，则rchildrchild指向其右指向其右孩子；否则，孩子；否则，rchildrchild指向其直接后继指向其直接后继(即线索即线索)。datalchildrchildfwdbwddatalchildrchild缺点：空间效缺点：空间效率太低！率太低！如何判断是孩如何判断是孩子指针还是线子指针还是线索指针？索指针？如何区如何区别？别？lchildlchildLTagLTagdatadataRTagRTag rchildrchild约定约定:当当Tag域为域为0时时,表示孩子情况表示孩子情况;当当Tag域为域为1时时,表示表示线索线索情况情况.前驱前驱(后继后继)左左(右右)孩子孩子为区别两种不同情况，特增加两个标志域：为区别两种不同情况，特增加两个标志域：为区别两种不同情况，特增加两个标志域：为区别两种不同情况，特增加两个标志域：问：问：增加了前驱和后继等线索有什么好处？增加了前驱和后继等线索有什么好处？能方便找出当前结点的前驱和后继，不用能方便找出当前结点的前驱和后继，不用堆栈（递归）也能遍历整棵树。堆栈（递归）也能遍历整棵树。各各1bit1bit 有关线索二叉树的几个术语：有关线索二叉树的几个术语：有关线索二叉树的几个术语：有关线索二叉树的几个术语：线索链表：线索链表：线线 索：索：线索二叉树：线索二叉树：线线 索索 化：化：用用含含Tag的结点样式所构成的二叉链表。的结点样式所构成的二叉链表。指向结点前驱和后继的指针。指向结点前驱和后继的指针。加上线索的二叉树。加上线索的二叉树。对二叉树以对二叉树以某种次序遍历某种次序遍历使其变为线索二使其变为线索二叉树的过程。叉树的过程。线索化过程就是在遍历过程中修改空指针的过程：线索化过程就是在遍历过程中修改空指针的过程：课本课本P127P127图图 将空的将空的lchildlchild改为结点的直接前驱；改为结点的直接前驱；将空的将空的rchildrchild改为结点的直接后继。改为结点的直接后继。非空指针呢？仍然指向孩子结点（称为非空指针呢？仍然指向孩子结点（称为“正常情况正常情况”）2020、已知一个二叉树的中序序列为、已知一个二叉树的中序序列为、已知一个二叉树的中序序列为、已知一个二叉树的中序序列为CBEDAHGIJF,CBEDAHGIJF,后序序列为后序序列为后序序列为后序序列为CEDBHJIGFA.CEDBHJIGFA.画出该二叉树，并画出该二叉树的先序线索二叉树。画出该二叉树，并画出该二叉树的先序线索二叉树。画出该二叉树，并画出该二叉树的先序线索二叉树。画出该二叉树，并画出该二叉树的先序线索二叉树。2121、将下图示的二叉树按中序线索化，结点、将下图示的二叉树按中序线索化，结点、将下图示的二叉树按中序线索化，结点、将下图示的二叉树按中序线索化，结点x x的右指的右指的右指的右指针指向（针指向（针指向（针指向（），），），），y y的左指针指向（的左指针指向（的左指针指向（的左指针指向（）。）。）。）。作业：作业：作业：作业：P217-218P217-218练习练习ABCDEXY