数据结构数据结构 6 6树和二叉树树和二叉树1树的类型定义树的类型定义二叉树的类型定义二叉树的类型定义二叉树的存储结构二叉树的存储结构遍历遍历二叉树二叉树和和线索二叉树线索二叉树树和森林树和森林赫夫曼树赫夫曼树主要内容主要内容2社会的组织结构社会的组织结构家族的族谱家族的族谱计算机中的目录组织计算机中的目录组织描述层次结构，是一种一对多的逻辑关系描述层次结构，是一种一对多的逻辑关系树型结构实例树型结构实例31.树的类型定义树的类型定义树的定义树的定义(Tree)树树是由是由n(n0)个结点组成的有限集合个结点组成的有限集合如果如果n=0，称为空树，称为空树如果如果n0，则，则l有一个特定的称之为有一个特定的称之为根根(root)的结点，它只有直接后继，的结点，它只有直接后继，但但没有直接前驱没有直接前驱l除根以外的其它结点划分为除根以外的其它结点划分为m(m=0)个个互不相交互不相交的有限的有限集合集合T0,T1,Tm-1，每个集合又是一棵树，并且称之为根，每个集合又是一棵树，并且称之为根的的子树子树递归定义递归定义4ABCDEFGHIJKLM根根子树子树树树(逻辑上逻辑上)的特点的特点每棵子树的根结点有且仅有一个直接前驱，但可以有每棵子树的根结点有且仅有一个直接前驱，但可以有0个个或多个直接后继或多个直接后继5ABCDEFGHIJKLM树的基本概念树的基本概念F结点结点分支结点分支结点叶子结点叶子结点根结点根结点内部结点内部结点结点结点度不为度不为0的结点的结点度为度为0的结点的结点6树的基本概念树的基本概念F结点的度和树的度结点的度和树的度结点的度即结点拥有的子树个数。结点的度即结点拥有的子树个数。树的度是树内各结点的度的最大值。树的度是树内各结点的度的最大值。ABCDEFGHIJKLM32132001000007树的基本概念树的基本概念F结点的层次和树的深度结点的层次和树的深度(高度高度)结结点点的的层层次次从从根根开开始始定定义义。根根位位于于第第1层层，根根的的孩孩子子位位于于第第2层，余则类推。层，余则类推。树的深度即树中结点的最大层次。树的深度即树中结点的最大层次。第第1层层第第2层层第第3层层第第4层层树树的的高高度度为为4ABCDEFGHIJKLM8树的基本概念树的基本概念F孩子、双亲、兄弟孩子、双亲、兄弟结点的子树的根称为结点的结点的子树的根称为结点的孩子孩子。该结点称为其孩子的该结点称为其孩子的双亲双亲。同一双亲的孩子间互称同一双亲的孩子间互称兄弟兄弟。ABCDEFGHIJKLM孩子孩子双亲双亲9树的基本概念树的基本概念F祖先、子孙祖先、子孙结点的结点的祖先祖先是从根到该结点所经分支上的所有结点；是从根到该结点所经分支上的所有结点；以某结点为根的子树中的任一结点都称该结点的以某结点为根的子树中的任一结点都称该结点的子孙子孙。ABCDEFGHIJKLMABCDEFGHIJKLM10树的基本概念树的基本概念森林：森林：m(m=0)棵互不相交的树的集合棵互不相交的树的集合BEFKLDHMIJCGACGBDEFKLHMIJ11树的有序性树的有序性：若树中结点的子树的相对位置不能随意：若树中结点的子树的相对位置不能随意改变，则称该树为改变，则称该树为有序树有序树，否则称该树为，否则称该树为无序树无序树。树的基本概念树的基本概念=有序树有序树无序树无序树ABDCACBD12有有序序树树中中最最左左边边的的子子树树的的根根称称其其第第一一个个孩孩子子，最最右右边边的的子树的根称其最后一个孩子。子树的根称其最后一个孩子。老大老大老二老二老三老三F有序树的第一个孩子和最后一个孩子有序树的第一个孩子和最后一个孩子树的基本概念树的基本概念ABDC13树的常用表示法树的常用表示法AEFBIJGHCDFGIJABCEDH凹入表示凹入表示嵌套集合嵌套集合广义表广义表A(B(E,F),C,D(G(J),H,I)A B E F C D G J H I14为何要重点研究每结点最多只有两个为何要重点研究每结点最多只有两个“叉叉”的树？的树？树太一般，子树的个数无限制，表示困难树太一般，子树的个数无限制，表示困难二叉树的结构最简单，规律性最强二叉树的结构最简单，规律性最强可以证明，可以证明，所有树都能转为唯一对应的二叉树所有树都能转为唯一对应的二叉树，不失，不失一般性。一般性。2.二叉树二叉树15二叉树的基本定义二叉树的基本定义二叉树的定义二叉树的定义是是n0个结点的有穷集合个结点的有穷集合该集合或者为空、或者由一个根结点和两个分别称为左子该集合或者为空、或者由一个根结点和两个分别称为左子树和右子树的互不相交的二叉树组成。树和右子树的互不相交的二叉树组成。当集合为空时，称该二叉树为空二叉树。当集合为空时，称该二叉树为空二叉树。逻辑结构：一对二逻辑结构：一对二(1:2)基本特征基本特征:l树的一种树的一种l每个结点最多有每个结点最多有2棵子树棵子树(即度即度=1)证明：证明：当当i=1时，显然成立时，显然成立假设当假设当i=k时，也成立，即第时，也成立，即第k层最多层最多2k-1个结点个结点当当i=k+1时，由于二叉树的每个结点最多有时，由于二叉树的每个结点最多有2个孩子，所个孩子，所以第以第k+1层最多有层最多有2*2k-1=2(k+1)-1个结点个结点故对于任意故对于任意i(i=1)，二叉树的第，二叉树的第i层最多有层最多有2i-1个结点个结点提问：第提问：第i层上至少有层上至少有个结点？个结点？121二叉树的性质二叉树的性质性质性质2：深度为深度为k的二叉树最多有的二叉树最多有2k-1个结点个结点(k=1)证明：证明：由性质由性质1可知：第可知：第i层最多有层最多有2i-1个结点个结点所以总的结点数最多为所以总的结点数最多为k=4123422二叉树的性质二叉树的性质性质性质3：对任何一棵二叉树对任何一棵二叉树T，若叶子结点数，若叶子结点数(即度为即度为0的结点数的结点数)为为n0，度为，度为2的结点数为的结点数为n2，则，则n0=n2+1证明：证明：总结点数总结点数n=n0+n1+n2设分支数为设分支数为B，则，则n=B+1又又B=n1+2n2结点无外乎度为结点无外乎度为0、1、2三种情况三种情况”五个手指四个叉五个手指四个叉”除了树根，其余每个结除了树根，其余每个结点点”上方上方”都有一个分支都有一个分支度为度为2的结点的结点“下方下方”有有2个分支个分支度为度为1的结点的结点“下方下方”有有1个分支个分支度为度为0的结点的结点“下方下方”有有0个分支个分支解方程组：解方程组：得：得：n0=n2+123树的叶子数与其它结点数的关系树的叶子数与其它结点数的关系设设度为度为m的树中度为的树中度为0,1,2,m的结点数分别为的结点数分别为n0,n1,n2,nm，结点总数为，结点总数为n，分支数为，分支数为B，则下面二式，则下面二式成立成立n=n0+n1+n2+nm(1)n=B+1=n1+2n2+mnm+1(2)由由(1)和和(2)得叶子结点数得叶子结点数n0=1+n2+2n3+(m-1)nm24满二叉树满二叉树(FullBinaryTree)深度为深度为k，结点数为，结点数为2k-1即结点数达到最大值即结点数达到最大值特殊形态的二叉树特殊形态的二叉树完全二叉树完全二叉树(CompleteBinaryTree)树中每个结点的编号（从上到下，从左到右）都与一个同树中每个结点的编号（从上到下，从左到右）都与一个同深度的满二叉树的结点一一对应深度的满二叉树的结点一一对应叶子结点只可能在层次最大的两层上出现叶子结点只可能在层次最大的两层上出现完全二叉树和和满二叉树相比，就是最完全二叉树和和满二叉树相比，就是最底层最右边连续缺少一些结点底层最右边连续缺少一些结点25特殊形态的二叉树特殊形态的二叉树2h-1结论：结论：深度为深度为h且具有且具有2h-1个结点的二叉树为满二叉树。个结点的二叉树为满二叉树。思考：深度为思考：深度为h的完全二叉树至少有多少个结点？的完全二叉树至少有多少个结点？26二叉树的性质二叉树的性质性质性质4：具有具有n个结点的非空完全二叉树的深度为个结点的非空完全二叉树的深度为证明：证明：设深度为设深度为k，则：，则：2k-1-1 n =2k-1由此推出：由此推出：2k-1 = n 2k两边求对数：两边求对数：k-1 = log2n 1，则其双亲是结点，则其双亲是结点 i/2 (2)若若2in，则结点，则结点i无左孩子无左孩子(即即i为叶结点为叶结点)，否则其左孩，否则其左孩子为子为2i(3)若若2i+1n，则结点，则结点i无右孩子，否则其右孩子为无右孩子，否则其右孩子为2i+1由由(2)(3)可以推导出可以推导出(1)理解：理解：结点结点i如果有左孩子的话，其编号应该为如果有左孩子的话，其编号应该为2i如果如果2in，则左孩子不存在，则左孩子不存在28二叉树的性质二叉树的性质性质性质6：具有具有n个结点的非空二叉树共有个结点的非空二叉树共有n-1个分支。个分支。证明：证明：除了根结点以外，每个结点有且仅有一个双亲结点，除了根结点以外，每个结点有且仅有一个双亲结点，即每个结点与其双亲结点之间仅有一个分支存在，因即每个结点与其双亲结点之间仅有一个分支存在，因此，具有此，具有n个结点的非空二叉树的分支总数为个结点的非空二叉树的分支总数为n-1。291.n(n0)个结点的树的高度最低是多少？最高是多少？个结点的树的高度最低是多少？最高是多少？2.n(n0)个结点的二叉树的高度最低是多少？最高是多少？个结点的二叉树的高度最低是多少？最高是多少？推论推论n个结点的树：个结点的树：高最多为高最多为n，最低为最低为2。n个结点的二叉树：个结点的二叉树：高最多为高最多为n(单支树单支树)，最低为，最低为 log2n +1(完全二叉树完全二叉树)。自测题自测题30自测题自测题 3.有关二叉树下列说法正确的是有关二叉树下列说法正确的是()A.二叉树的度为二叉树的度为2B.一棵二叉树的度可以小于一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为二叉树中任何一个结点的度都为24.已知一棵完全二叉树的第已知一棵完全二叉树的第6层层(设根是第设根是第1层层)有有8个叶结点，个叶结点，则该完全二叉树的结点个数最多是则该完全二叉树的结点个数最多是()A.39B.52C.111D.11931完全二叉树性质的推论完全二叉树性质的推论n个结点的完全二叉树中：个结点的完全二叉树中：度为度为1的结点数为的结点数为(n+1)%2度为度为0的结点数为的结点数为 (n+1)/2 度为度为2的结点数为的结点数为 (n+1)/2 -1编号最大的分支结点是编号最大的分支结点是 n/2 编号最小的叶子结点是编号最小的叶子结点是 n/2 +1具有具有n0个叶子结点的完全二叉树中共有个叶子结点的完全二叉树中共有2n0个个结点或结点或2n0-1个个结点。结点。32一棵完全二叉树有一棵完全二叉树有1000个结点，则它必个结点，则它必有有个叶子结点；个叶子结点；有有个度为个度为2的结点；的结点；有有个结点只有非空左子树；个结点只有非空左子树；有有个结点只有非空右子树。个结点只有非空右子树。 (1000+1)/2 =500叶子总数叶子总数-1=49910因为最后一个结点坐标是偶数，所以必为左子树。有因为最后一个结点坐标是偶数，所以必为左子树。有1个结点只有非个结点只有非空左子树，有空左子树，有0个结点只有非空右子树。个结点只有非空右子树。自测题自测题33自测题自测题5.一棵一棵124个叶结点的完全二叉树，最多有个叶结点的完全二叉树，最多有()个结点。个结点。A.247B.248C.249D.250E.2516.已知一棵完全二叉树中共有已知一棵完全二叉树中共有626个结点，叶子结点的个数应个结点，叶子结点的个数应为为()。A.311B.312C.313D.314E.其他其他34自测题自测题7.一个具有一个具有1025个结点的二叉树的高个结点的二叉树的高h为为()。A.11B.10C.11至至1025之间之间D.10至至1024之间之间8.已知一棵度为已知一棵度为3的树有的树有2个度为个度为1的结点，的结点，3个度为个度为2的结点，的结点，4个度为个度为3的结点，则该树有的结点，则该树有_个叶子结点。个叶子结点。1235二叉树二叉树本节小结本节小结二叉树的概念和类型定义二叉树的概念和类型定义注意和树的类型定义的对比注意和树的类型定义的对比二叉树的性质二叉树的性质要求自己能推导、应用、推广要求自己能推导、应用、推广363.二叉树的存储结构二叉树的存储结构二叉树的顺序存储结构二叉树的顺序存储结构用一维数组来表示用一维数组来表示#defineMAX_TREE_SIZE100typedefdatatypeSqBiTreeMAX_TREE_SIZE;SqBiTreeBt;按照满二叉树的顺序存放按照满二叉树的顺序存放37完全二叉树的顺序存储结构完全二叉树的顺序存储结构根据完全二叉树的根据完全二叉树的性质性质5，对于深度为，对于深度为h的完全二叉树，将树的完全二叉树，将树中所有结点的数据信息按编号顺序一次存储到数组中所有结点的数据信息按编号顺序一次存储到数组BT12h-1中，中，由于编号与数组下标一一对应，该数组就是该完全二叉树的顺序由于编号与数组下标一一对应，该数组就是该完全二叉树的顺序存储结构。存储结构。1234567891012345678910下标：下标： BT3的双亲为的双亲为 3/2 =1，即在，即在BT1中；中；其左孩子在其左孩子在BT2i=BT6中；中；其右孩子在其右孩子在BT2i+1=BT7中。中。38一般二叉树的顺序存储结构一般二叉树的顺序存储结构123456789101234567891012345678910BT5的双亲为的双亲为 5/2 =2，即在，即在BT2中，与实际矛盾！中，与实际矛盾！其左孩子在其左孩子在BT2i=BT10中，实际应在中，实际应在BT9中。中。v对对于于一一般般二二叉叉树树，需需要要在在二二叉叉树树中中“增增添添”一一些些实实际际上上并并不不存存在在的的“虚虚结结点点”(可可以以认认为为这这些些结结点点的的数数据据信信息息为为空空)，使使其其在在形形式式上上成成为为一一棵棵“完全二叉树完全二叉树”；v然然后后按按照照完完全全二二叉叉树树的的顺顺序序存存储储结结构构的的构构造造方方法法将将所所有有结结点点的的信信息息依次存放到数组依次存放到数组BT1.2h-1中。中。391234067890012001512345678910 11 12 13 14 15BT6的双亲为的双亲为 6/2 =3，即在，即在BT3中！中！其左孩子在其左孩子在BT2i=BT12中；中；其右孩子在其右孩子在BT2i+1=BT13中，而中，而BT130，表示无右孩子。，表示无右孩子。40一般二叉树的顺序存储结构一般二叉树的顺序存储结构极端情形：单支树极端情形：单支树深度为深度为k的二叉树，最少只有的二叉树，最少只有k个结点个结点却需要却需要2k-1个存储单元个存储单元137深度增加一层深度增加一层10增加增加1倍之多倍之多103000700000001541二叉树的链式存储结构二叉树的链式存储结构二叉链表二叉链表data为数据域；为数据域；lchild与与rchild分别为指向左、右子树的指针域。分别为指向左、右子树的指针域。3.二叉树的存储结构二叉树的存储结构lchilddatarchilddatalchildrchild42二叉链表示例二叉链表示例说明：说明：一个二叉链表由根指针一个二叉链表由根指针T唯一确定。唯一确定。若若二二叉叉树树为为空空，则则T=NULL；若若结结点点的的某某个个孩孩子子不不存存在在，则则相相应的指针为空。应的指针为空。具具有有n个个结结点点的的二二叉叉链链表表中中，共共有有2n个个指指针针域域。其其中中只只有有n-1个个用来指示结点的左、右孩子，其余的用来指示结点的左、右孩子，其余的n+1个指针域为空。个指针域为空。43二叉树的链式存储结构二叉树的链式存储结构三叉链表三叉链表比二叉链表的链结点多增加了一个指向双亲结点的指针域比二叉链表的链结点多增加了一个指向双亲结点的指针域parent。3.二叉树的存储结构二叉树的存储结构lchilddataparentrchildparentdataleftchildrightchild44三叉链表示例三叉链表示例45二叉链表结点结构的定义二叉链表结点结构的定义typedefintdatatype;typedefstructnodedatatypedata;structnode*lchild,*rchild;bitree;二叉树的链表表示二叉树的链表表示lchilddatarchild46二叉树的存储结构二叉树的存储结构本节小结本节小结各种存储结构各种存储结构注意各自的优缺点注意各自的优缺点比如顺序存储空间浪费大比如顺序存储空间浪费大二叉链表不能直接找到父结点二叉链表不能直接找到父结点47练习练习1已知非空二叉树采用广义表形式作为输入，请写一算已知非空二叉树采用广义表形式作为输入，请写一算法，建立该二叉树的二叉链表存储结构。法，建立该二叉树的二叉链表存储结构。48关于广义表形式表示二叉树的说明关于广义表形式表示二叉树的说明1.约定约定表中的一个字母代表一个结点的数据信息。表中的一个字母代表一个结点的数据信息。2.每个根结点作为由子树构成的表的名字放在表的前面。每个根结点作为由子树构成的表的名字放在表的前面。3.每个结点的左子树和右子树之间用逗号分开，若只有右子树而无每个结点的左子树和右子树之间用逗号分开，若只有右子树而无左子树，则逗号不能省略。左子树，则逗号不能省略。4.在整个广义表的末尾加一个特殊符号（如在整个广义表的末尾加一个特殊符号（如）作为结束标志。）作为结束标志。ABCDFGE49F二叉树的广义表表示方法二叉树的广义表表示方法二叉树二叉树defi=“”空树空树50大写字大写字母母二叉树二叉树defi=“A”只有树根只有树根AF二叉树的广义表表示方法二叉树的广义表表示方法51大写字大写字母母(二叉二叉树树,)二叉树二叉树#二叉二叉树树defi=“A(B,C(D,E)”ACDEBF二叉树的广义表表示方法二叉树的广义表表示方法521.若取到的元素为字母，则如下若取到的元素为字母，则如下建立一个新结点建立一个新结点，l若该结点为根结点，则将该结点的地址送若该结点为根结点，则将该结点的地址送T。l若该结点不是二叉树的根结点，则将该结点作为左孩子（若标志为若该结点不是二叉树的根结点，则将该结点作为左孩子（若标志为1）或者右孩子（若标志为或者右孩子（若标志为2）链接到其双亲结点上链接到其双亲结点上（双亲结点的地址在（双亲结点的地址在栈栈顶）顶）。2.若取到的元素为左括号（，则表明一个子表开始，若取到的元素为左括号（，则表明一个子表开始，将标志置为将标志置为1，同时将前面那个结点的地址进栈同时将前面那个结点的地址进栈。3.若取到的元素为右括号），则表明一个子表结束，若取到的元素为右括号），则表明一个子表结束，作退栈操作作退栈操作。4.若取到的元素为逗号，则表明以左孩子为根的子树处理完毕，接着若取到的元素为逗号，则表明以左孩子为根的子树处理完毕，接着应该处理以右孩子为根的子树，应该处理以右孩子为根的子树，将标志置为将标志置为2。如此处理广义表中每一个元素，直到取到结束符号如此处理广义表中每一个元素，直到取到结束符号为止。为止。53练习练习2已知具有已知具有n个结点的非空完全二叉树采用顺序存储结个结点的非空完全二叉树采用顺序存储结构，结点的数据信息依次存放于数组构，结点的数据信息依次存放于数组BT1.n中。请写中。请写出由此产生该二叉树二叉链表结构的算法。出由此产生该二叉树二叉链表结构的算法。54建立根结点建立根结点以以BT的第的第2个元素开始取个元素开始取一个元素一个元素建立一个新结点建立一个新结点保存新结点的地址保存新结点的地址找到新结点的双亲结点的地址找到新结点的双亲结点的地址确定新结点是双亲结点的左（或右）孩子确定新结点是双亲结点的左（或右）孩子将新结点插入二叉链表中将新结点插入二叉链表中保存在一个数组中保存在一个数组中利用二叉树利用二叉树的性质的性质555设置一个一维数组设置一个一维数组PTR存放结点所在链结点的地址存放结点所在链结点的地址建立根结点，并将根结点的地址保存在数组建立根结点，并将根结点的地址保存在数组PTR中中从数组从数组BT的第的第2个元素开始依次取结点的信息个元素开始依次取结点的信息BTi，每取得一，每取得一个结点做如下操作：个结点做如下操作：1.建立一个新结点，并将结点地址保存在建立一个新结点，并将结点地址保存在PTRi中；中；2.建立新结点的双亲结点的位置建立新结点的双亲结点的位置(地址地址)；3.确定新结点是其双亲结点的左孩子或右孩子；确定新结点是其双亲结点的左孩子或右孩子；4.将新结点作为双亲结点的左孩子或右孩子插入二叉链表中。将新结点作为双亲结点的左孩子或右孩子插入二叉链表中。位位置置j=i/2地地址址PTRj若若i%2=0，则新结点是其双亲结点的左孩子；，则新结点是其双亲结点的左孩子；当当i%2!=0，则新结点是其双亲结点的右孩子；，则新结点是其双亲结点的右孩子；56ijj=i/2当当i%2=0时，时，i是是j的左孩子的左孩子当当i%2!=0时，时，i是是j的右孩子的右孩子57#defineMaxNode100/*MaxNode=n*/bitree*BUILDBTREE(datatypeBT,intn)bitree*T,*PTRMaxNode;inti,j;PTR1=(bitree*)malloc(sizeof(bitree);PTR1-data=BT1;PTR1-lchild=NULL;PTR1-rchild=NULL;T=PTR1;/*建立根结点建立根结点*/58for(i=2;idata=BTi;PTRi-lchild=NULL;PTRi-rchild=NULL;j=i/2;/*计算双亲结点的位置计算双亲结点的位置j*/if(i%2=0)PTRj-lchild=PTRi;/*BTi是双亲的左孩子是双亲的左孩子*/elsePTRj-rchild=PTRi;/*BTi是双亲的右孩子是双亲的右孩子*/returnT;59已知非空二叉树采用顺序存储结构，结点的数据信已知非空二叉树采用顺序存储结构，结点的数据信息依次存放于数组息依次存放于数组BT1.n中。请写出由此产生该二叉中。请写出由此产生该二叉树二叉链表结构的算法。树二叉链表结构的算法。练习练习360一、二叉树的遍历一、二叉树的遍历按照一定的顺序按照一定的顺序(原则原则)对二叉树中每一个结点都访问一次对二叉树中每一个结点都访问一次(仅仅访问一次访问一次)，得到一个由该二叉树的所有结点组成的序列，这一，得到一个由该二叉树的所有结点组成的序列，这一过程称为过程称为二叉树的遍历二叉树的遍历。访问的含义包括查询、打印、计算、修改等对结点的操作。访问的含义包括查询、打印、计算、修改等对结点的操作。4.二叉树的遍历二叉树的遍历61常用的遍历方法：常用的遍历方法：1.前前(先先)序遍历序遍历DLR2.中中序遍历序遍历LDR3.后后序遍历序遍历LRD4.按按层次遍历层次遍历遍历规则遍历规则注：指访问的结点注：指访问的结点D是先于子树出现还是后于子树出现。是先于子树出现还是后于子树出现。以根结点为参照系以根结点为参照系根根左左子子树树右右子子树树62原则原则若被遍历的二叉树为空，则空操作若被遍历的二叉树为空，则空操作否则否则1.访问根结点访问根结点2.以前序遍历原则以前序遍历原则遍历根结点的左子树遍历根结点的左子树3.以前序遍历原则以前序遍历原则遍历根结点的右子树遍历根结点的右子树二、前序遍历二、前序遍历(PreorderTraversal)递归递归63BACFDEGHA遍历序列：遍历序列：BCFDEGH(1)访问根结点；访问根结点；(2)前序遍历左子树；前序遍历左子树；(3)前序遍历右子树。前序遍历右子树。二、前序遍历二、前序遍历(PreorderTraversal)64三、中序遍历三、中序遍历(InorderTraversal)原则原则若被遍历的二叉树为空，则空操作若被遍历的二叉树为空，则空操作否则否则1.以中序遍历原则以中序遍历原则遍历根结点的左子树遍历根结点的左子树2.访问根结点访问根结点3.以中序遍历原则以中序遍历原则遍历根结点的右子树遍历根结点的右子树递归递归65遍历序列：遍历序列：(1)中序遍历左子树；中序遍历左子树；(2)访问根结点；访问根结点；(3)中序遍历右子树。中序遍历右子树。BACFDEGHABCFDEGH三、中序遍历三、中序遍历(InorderTraversal)66四、后序遍历四、后序遍历(PostorderTraversal)原则原则若被遍历的二叉树为空，则空操作若被遍历的二叉树为空，则空操作否则否则1.以后序遍历原则以后序遍历原则遍历根结点的左子树遍历根结点的左子树2.以后序遍历原则以后序遍历原则遍历根结点的右子树遍历根结点的右子树3.访问根结点访问根结点递归递归67遍历序列：遍历序列：(1)后序遍历左子树；后序遍历左子树；(2)后序遍历右子树；后序遍历右子树；(3)访问根结点。访问根结点。BACFDEGHABCFDEGH四、后序遍历四、后序遍历(PostorderTraversal)68二叉树的其它操作：广度优先遍历二叉树的其它操作：广度优先遍历BACFDEGHA遍历序列：遍历序列：BCFDEGH广度优先遍历广度优先遍历(也叫层次遍历也叫层次遍历)(1)按按结结点点所所在在层层次次，由由低低层层向向高层依次遍历；高层依次遍历；(2)同层按自左向右次序遍历。同层按自左向右次序遍历。69二叉树的其它操作：广度优先遍历二叉树的其它操作：广度优先遍历二叉树的层序遍历算法：二叉树的层序遍历算法：(1)初始化设置一个队列；初始化设置一个队列；(2)把根结点指针入队列；把根结点指针入队列；(3)当队列非空时，循环执行步骤当队列非空时，循环执行步骤(a)到步骤到步骤(c):(a)出队列取得一个结点指针，访问该结点；出队列取得一个结点指针，访问该结点；(b)若该结点的左子树非空，则将该结点的左子树指针入队列；若该结点的左子树非空，则将该结点的左子树指针入队列；(c)若该结点的右子树非空，则将该结点的右子树指针入队列；若该结点的右子树非空，则将该结点的右子树指针入队列；(4)结束。结束。70(1)从根开始：若二叉树非空，则根入队；从根开始：若二叉树非空，则根入队；(2)队头出队，并访问；队头出队，并访问；BACDEGFHT排队处排队处遍历序列遍历序列思路：思路：ApBC(3)若若当当前前结结点点有有左左子子树树，则则其其左左子树的根入队；子树的根入队；(4)若若当当前前结结点点有有右右子子树树，则则其其右右子树的根入队；子树的根入队；(5)重复重复(2)(4)，DEpFpGHppp直至队空。直至队空。71算法：算法：StatusLevelOrderTraverse(biTree*T)InitQueue(Q);AddQueue(Q,T);/树根入队树根入队while(!QueueEmpty(Q)/只要队列非空只要队列非空DeleteQueue(Q,p);/出队一个结点出队一个结点if(!Visit(p-data)returnERROR;/访问之访问之if(p-lchild)AddQueue(Q,p-lchild);/左孩子入队左孩子入队if(p-rchild)AddQueue(Q,p-rchild);/右孩子入队右孩子入队returnOK;72二叉树的遍历二叉树的遍历:算法算法回忆一下递归算法的适用情况回忆一下递归算法的适用情况(1)问题本身直接用递归定义的问题本身直接用递归定义的(2)问题的规律有递归的特点问题的规律有递归的特点二叉树及其遍历是用递归定义的二叉树及其遍历是用递归定义的用递归算法肯定可以解决用递归算法肯定可以解决如果不用递归呢？如果不用递归呢？73二叉树的前序遍历递归算法二叉树的前序遍历递归算法若二叉树为空，则算法结束；否则：若二叉树为空，则算法结束；否则：(1)访问根结点；访问根结点；(2)前序遍历根结点的左子树；前序遍历根结点的左子树；(3)前序遍历根结点的右子树。前序遍历根结点的右子树。voidPreOrderTraverse(bitree*T)if(T) 二叉树非空二叉树非空printf(t%cn,T-data); 访问根结点访问根结点PreOrderTraverse(T-lchild); 前序遍历左子树前序遍历左子树PreOrderTraverse(T-rchild); 前序遍历右子树前序遍历右子树74二叉树的中序遍历递归算法二叉树的中序遍历递归算法若二叉树为空，则算法结束；否则：若二叉树为空，则算法结束；否则：(1)中序遍历根结点的左子树；中序遍历根结点的左子树；(2)访问根结点；访问根结点；(3)中序遍历根结点的右子树。中序遍历根结点的右子树。voidInOrderTraverse(bitree*T)if(T)InOrderTraverse(T-lchild);printf(t%cn,T-data);InOrderTraverse(T-rchild);75二叉树的后序遍历递归算法二叉树的后序遍历递归算法若二叉树为空，则算法结束；否则：若二叉树为空，则算法结束；否则：(1)后序遍历根结点的左子树；后序遍历根结点的左子树；(2)后序遍历根结点的右子树；后序遍历根结点的右子树；(3)访问根结点。访问根结点。voidPostOrderTraverse(bitree*T)if(T)PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);printf(t%cn,T-data);761.递归算法的优点递归算法的优点(1)问题的数学模型或算法设计方法本身就是递归的，采用递归算法问题的数学模型或算法设计方法本身就是递归的，采用递归算法来描述它们非常自然；来描述它们非常自然；(2)描述直观，结构清晰、简洁；正确性证明比非递归算法容易。描述直观，结构清晰、简洁；正确性证明比非递归算法容易。2.递归算法的不足递归算法的不足(1)算法的执行时间与空间开销往往比非递归算法要大，当问题规模算法的执行时间与空间开销往往比非递归算法要大，当问题规模较大时尤为明显；较大时尤为明显；(2)对算法进行优化比较困难；对算法进行优化比较困难；(3)分析跟踪算法的执行过程比较麻烦；分析跟踪算法的执行过程比较麻烦；(4)描述算法的语言不具有递归功能时，算法无法描述。描述算法的语言不具有递归功能时，算法无法描述。谨慎使用递归，因为它的简谨慎使用递归，因为它的简洁可能会掩盖它的低效率。洁可能会掩盖它的低效率。五、递归问题的非递归算法的设计五、递归问题的非递归算法的设计77五、递归问题的非递归算法的设计五、递归问题的非递归算法的设计回顾遍历的过程回顾遍历的过程(以中序为例以中序为例)1先走到最左先走到最左2往回访问父结点往回访问父结点3往右访问右子树往右访问右子树3.1走到最左走到最左3.2回访父结点回访父结点3.3访问右子树访问右子树.ABCDEFG78二叉树的遍历：非递归算法二叉树的遍历：非递归算法ABCDEFG当向左当向左/右走到底时怎么办？右走到底时怎么办？需要返回到祖先需要返回到祖先哪个祖先？哪个祖先？路过的却未访问的最近的祖先路过的却未访问的最近的祖先这就需要一种机制能记录访问的这就需要一种机制能记录访问的“历历史信息史信息”:路过却未访问的结点路过却未访问的结点，以便，以便能够回溯回去能够回溯回去这就需要一个这就需要一个栈栈存放来这些祖先存放来这些祖先79E H二叉树的遍历：非递归算法二叉树的遍历：非递归算法(1)非空树从根开始；非空树从根开始；(2)若当前结点存在，若当前结点存在，则暂存，则暂存，p下到左子树；下到左子树；否则回退否则回退访问当前结点访问当前结点p下到右子树下到右子树中序遍历非递归思路：中序遍历非递归思路：BACDEGFHTpA栈栈SBDpp遍历序列：遍历序列：DppBGpGpppEppHppACppCFppFp(3)重复重复(2)直到直到p空且栈空空且栈空80Stack0.M-1-保存遍历过程中结点的地址；保存遍历过程中结点的地址；top-栈顶指针，初始为栈顶指针，初始为-1；p-遍历过程中使用的指针变量，初始时指向根结点。遍历过程中使用的指针变量，初始时指向根结点。用自然语言表达的算法用自然语言表达的算法1.若若p指向的结点非空，则将指向的结点非空，则将p指的结点的地址进栈，然后，将指的结点的地址进栈，然后，将p指指向左子树的根；向左子树的根；2.若若p指向的结点为空，则从栈中退出栈顶元素送指向的结点为空，则从栈中退出栈顶元素送p，访问该结点，访问该结点，然后，将然后，将p指向右子树的根；指向右子树的根；重复上述过程，直到重复上述过程，直到p为空，并且栈也为空。为空，并且栈也为空。81二叉树的中序遍历：非递归算法二叉树的中序遍历：非递归算法intInOrderT(bitree*T)bitree*p=T;SqStack*S;InitStack(S);/建栈建栈while(p|!StackEmpty(s)/还有未访问的还有未访问的if(p)/一直向左走到底，路过的所有的根入栈一直向左走到底，路过的所有的根入栈Push(S,p);p=p-lchild;/遍历左子树遍历左子树else/p为为NULL，说明走到了底，说明走到了底Pop(S,p);Visit(p-data);/弹出一个还没访问的结点，访问之弹出一个还没访问的结点，访问之p=p-rchild;/遍历右子树遍历右子树returnOK;p指向树根指向树根p走到了底，再依次弹出刚才走到了底，再依次弹出刚才路过却没有访问的结点，访问路过却没有访问的结点，访问之，然后之，然后p向右走向右走82时间复杂度时间复杂度n个结点，每一个都要访问一次个结点，每一个都要访问一次显然时间复杂度为显然时间复杂度为O(n)(这里这里n为结点数为结点数)空间复杂度空间复杂度不论是递归还是非递归算法都要用到栈不论是递归还是非递归算法都要用到栈栈的最大深度栈的最大深度=树的深度树的深度所有空间复杂度为所有空间复杂度为O(n)(这里这里n为树的深度为树的深度)二叉树的遍历：算法效率二叉树的遍历：算法效率83二叉树的初始化二叉树的初始化算法的基本思想算法的基本思想:创建二叉树的头结点。创建二叉树的头结点。程序实现程序实现：voidInitiate(bitree*root)*root=(bitree*)malloc(sizeof(bitree);(*root)-lchild=NULL;(*root)-rchild=NULL;root是指向根指针的指针是指向根指针的指针84按前序构造二叉链表按前序构造二叉链表例例1：按下列次序输入字符：按下列次序输入字符(表示空格表示空格):ABCDEGFABCDEFG二叉链表为二叉链表为:例例2：HGFMrootHGMF85按前序构造二叉链表的算法按前序构造二叉链表的算法voidCreateBT(bitree*P)charch;ch=getchar();/*从键盘上输入一个字符从键盘上输入一个字符*/if(ch=)*P=NULL;else*P=(bitree*)malloc(sizeof(bitree);(*P)-data=ch;CreateBT(&(*P)-lchild);CreateBT(&(*P)-rchild);P是指向根指针的指针，是指向根指针的指针，*P的的值发生变化后可以返回值发生变化后可以返回86前序遍历序列：前序遍历序列：A,B,D,K,J,G,C,F,I,E,H中序遍历序列：中序遍历序列：D,B,G,J,K,A,F,I,E,C,H后序遍历序列：后序遍历序列：D,G,J,K,B,E,I,F,H,C,A按层次遍历序列：按层次遍历序列：A,B,C,D,K,F,H,J,I,G,E8788前序序列：前序序列：中序序列：中序序列：后序序列：后序序列：ABIFCGDEHFIBCGADEHFIGCBHEDA89利用利用前序序列前序序列和和中序序列中序序列恢复二叉树恢复二叉树利用利用中序序列中序序列和和后序序列后序序列恢复二叉树恢复二叉树利用利用前序序列前序序列和和后序序列后序序列恢复二叉树恢复二叉树前序序列：前序序列：A,B,D,C后序序列：后序序列：D,B,C,A90六、由遍历序列恢复二叉树六、由遍历序列恢复二叉树前序序列：前序序列：A,B,D,E,J,C,F,I,G中序序列：中序序列：D,B,J,E,A,F,I,C,G91已知前序序列和中序序列，恢复二叉树已知前序序列和中序序列，恢复二叉树在前序序列中寻找根；在前序序列中寻找根；到中序序列中分左右。到中序序列中分左右。规规律律已知中序序列和后序序列，恢复二叉树已知中序序列和后序序列，恢复二叉树在后序序列中寻找根；在后序序列中寻找根；到中序序列中分左右。到中序序列中分左右。92例例:已知结点的前序序列和中序序列分别为：已知结点的前序序列和中序序列分别为：前序序列：前序序列：ABDEGHCF中序序列：中序序列：DBGEHACF求此二叉树求此二叉树六、由遍历序列恢复二叉树六、由遍历序列恢复二叉树93F由已知的前序序列和中序序列构造二叉树的方法由已知的前序序列和中序序列构造二叉树的方法ABD前序前序EGHCFDBG中序中序EHACFA012345左子树左子树右子树右子树左子树左子树右子树右子树六、由遍历序列恢复二叉树六、由遍历序列恢复二叉树94ABD前序前序EGHCFDBG中序中序EHACFAB01左左右右左左右右DF由已知的前序序列和中序序列构造二叉树的方法由已知的前序序列和中序序列构造二叉树的方法六、由遍历序列恢复二叉树六、由遍历序列恢复二叉树95ABD前序前序EGHCFDBG中序中序EHACFBADE01左左左左右右右右GHF由已知的前序序列和中序序列构造二叉树的方法由已知的前序序列和中序序列构造二叉树的方法六、由遍历序列恢复二叉树六、由遍历序列恢复二叉树96ABD前序前序EGHCFDBG中序中序EHACFBACFDEGH0右右右右F由已知的前序序列和中序序列构造二叉树的方法由已知的前序序列和中序序列构造二叉树的方法六、由遍历序列恢复二叉树六、由遍历序列恢复二叉树97(1)由前序序列得根；由前序序列得根；(2)在中序序列中查找根，并确定左子树中结点个数；在中序序列中查找根，并确定左子树中结点个数；(3)分别确定左、右子树的前序序列和中序序列；分别确定左、右子树的前序序列和中序序列；(4)分别构造左、右子树分别构造左、右子树六、由遍历序列恢复二叉树六、由遍历序列恢复二叉树F由已知的前序序列和中序序列构造二叉树的方法由已知的前序序列和中序序列构造二叉树的方法98已知二叉树的已知二叉树的1.前序序列前序序列ABDFCEHG中序序列中序序列DBFAHECG请构造该二叉树。请构造该二叉树。2.后序序列后序序列DMFBHELGCA中序序列中序序列DBMFAHECGL请构造该二叉树。请构造该二叉树。自测题自测题99一棵二叉树的前序、中序和后序序列如下，其中有部分未标一棵二叉树的前序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。出，试构造出该二叉树。前序序列为：前序序列为：_CDE_GHI_K中序序列为：中序序列为：CB_FA_JKIG后序序列为：后序序列为：_EFDB_JIH_A自测题自测题100试找出满足下列条件的二叉树试找出满足下列条件的二叉树1)前序序列与后序序列相同前序序列与后序序列相同2)中序序列与后序序列相同中序序列与后序序列相同3)前序序列与中序序列相同前序序列与中序序列相同4)前序、中序、后序序列均相同前序、中序、后序序列均相同5)中序序列与层次遍历序列相同中序序列与层次遍历序列相同自测题自测题101一棵二叉树的前序遍历序列为一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序，它的中序遍历序列可能是列可能是()。A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEGB自测题自测题102一棵非空的二叉树的前序序列和后序序列正好相反，则该二一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足叉树一定满足()。A.其中任意一个结点均无左孩子其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子其中任意一个结点均无右孩子C.其中只有一个叶子结点其中只有一个叶子结点D.其中度为其中度为2的结点最多为一个的结点最多为一个E.空或只有一个结点空或只有一个结点F.高度等于其结点数高度等于其结点数自测题自测题103注意：注意：一个二叉树的遍历序列一个二叉树的遍历序列不能决定一棵不能决定一棵二叉树，但二叉树，但前序前序（或后序）和中序遍历序列的组合（或后序）和中序遍历序列的组合可以可以唯一确定唯一确定一棵二一棵二叉树。而前序和后序遍历则不能。叉树。而前序和后序遍历则不能。口诀：口诀：DLR前序遍历，即前序遍历，即先根先根再左再右再左再右LDR中序遍历，即中序遍历，即先左先左再根再根再右再右LRD后序遍历，即后序遍历，即先左再右先左再右再根再根104例例6.1 给二叉树中某个指定结点插入一个左结点给二叉树中某个指定结点插入一个左结点算法思想算法思想:若当前结点若当前结点(假设为假设为curr)非空，在非空，在curr的左子树插入元的左子树插入元素值为素值为x的新结点，原的新结点，原curr所指结点的左子树成为新插入结所指结点的左子树成为新插入结点的左子树。若插入成功返回新插入结点的指针，否则返回点的左子树。若插入成功返回新插入结点的指针，否则返回空指针。空指针。二叉树操作举例二叉树操作举例105bitree*InsertLeftNode(bitree*curr,datatypex)bitree*s,*t;if(curr=NULL)returnNULL; t=curr-lchild;s=(bitree*)malloc(sizeof(bitree);s-data=x;s-lchild=t;s-rchild=NULL;curr-lchild=s;returncurr-lchild;106算法思想算法思想:若若curr非空，删除非空，删除curr所指结点的左子树。若删除成功，所指结点的左子树。若删除成功，返回删除结点的双亲结点指针，否则返回空指针。返回删除结点的双亲结点指针，否则返回空指针。例例6.2 删除二叉树中指定结点的左子树删除二叉树中指定结点的左子树bitree*DeleteLeftTree(bitree*curr)if(curr=NULL|curr-lchild=NULL)returnNULL;free(curr-lchild);curr-lchild=NULL;returncurr;107例例6.3 求二叉树深度求二叉树深度算法思想算法思想: 从二叉树深度的定义可知，二叉树的深度应为其左、右从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加子树深度的最大值加1。由此，需先分别求得左、右子树的。由此，需先分别求得左、右子树的深度，并将所得的左、右子树深度的最大值加深度，并将所得的左、右子树深度的最大值加1。108intBTreeDepth(bitree*BT)intleftdep,rightdep;if(BT=NULL)return(0);/空二叉树空二叉树elseleftdep=BTreeDepth(BT-lchild);rightdep=BTreeDepth(BT-rchild);if(leftdeprightdep)return(leftdep+1);elsereturn(rightdep+1);109例例6.4 统计叶子结点数（统计叶子结点数（1）算法思想算法思想: 中序中序(或前序或后序或前序或后序)遍历二叉树，在遍历过程中查找叶遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个子结点，并计数。由此，需在遍历算法中增添一个“计数计数”的的参数，并将遍历算法中参数，并将遍历算法中“访问结点访问结点”的操作改为：若是叶子，的操作改为：若是叶子，则计数器增则计数器增1。110intnum=0;/全局变量全局变量voidLeafCount(bitree*BT)if(BT)LeafCount(BT-lchild);/中序遍历左子树中序遍历左子树if(!BT-lchild&!BT-rchild)num+;/叶子结点计数叶子结点计数LeafCount(BT-rchild);/中序遍历右子树中序遍历右子树111例例6.4 统计叶子结点数（统计叶子结点数（2）intleafcount(bitree*BT)if(!BT)return(0);/空树没有叶子空树没有叶子else/只有根结点只有根结点if(!BT-lchild&!BT-rchild)return(1);elsereturn/左子树叶子数加上右子树叶子数左子树叶子数加上右子树叶子数(leafcount(BT-lchild)+leafcount(BT-rchild);112例例6.5 交换所有结点的左右子树交换所有结点的左右子树voidSubtree_Revolute(bitree*T)bitree*p;if(T)p=T-lchild;T-lchild=T-rchild;T-rchild=p;Subtree_Revolute(T-lchild);Subtree_Revolute(T-rchild);113例例6.6 求二叉树的结点个数求二叉树的结点个数intnodecount(bitree*BT)if(BT=NULL)return(0);/空二叉树空二叉树elsereturn(nodecount(BT-lchild)+nodecount(BT-rchild)+1);114例例6.7 求二叉树的非叶子结点个数求二叉树的非叶子结点个数intnotleafcount(bitree*BT)if(!BT)return(0);/空二叉树空二叉树else/只有根结点只有根结点if(!BT-lchild&!BT-rchild)return(0);elsereturn(notleafcount(BT-lchild)+notleafcount(BT-rchild)+1);115例例6.8 设一棵二叉树中各结点的值互不相同，其前设一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存于两个一维数组序序列和中序序列分别存于两个一维数组pre1.n和和mid1.n中，试遍写算法建立该二叉中，试遍写算法建立该二叉树的二叉链表。树的二叉链表。 116ABDEGHCF0213 4 5 6 7preDBGEHACF0213 4 5 6 7mid1.由前序序列得根由前序序列得根2.若若序序列列中中多多于于1个个元元素素，则则在在中中序序序序列列中中查查找找根根（定定位位根根在字符串中第一次出现的位置）在字符串中第一次出现的位置），并确定左子树中结点个数；，并确定左子树中结点个数；makeT(pre,mid)1174.分别构造左、右子树分别构造左、右子树r.lchild=makeT(lpre,lmid);r.rchild=makeT(rpre,rmid);3.分别确定左、右子树的前序序列和中序序列分别确定左、右子树的前序序列和中序序列lpre=pre(1,i-1);rpre=pre(i,n);lmid=mid(0,i-1);rmid=mid(i,m);118已知具有已知具有n个结点的完全二叉树采个结点的完全二叉树采用顺序存储结构，结点的数据信息用顺序存储结构，结点的数据信息依次存放于一维数组依次存放于一维数组BT1.n中，中，写出中序遍历二叉树的非递归算法。写出中序遍历二叉树的非递归算法。119BT1.6ABCDEF123456中序序列：中序序列：DBEAFC120Stack0.M-1-保存遍历过程中结点的保存遍历过程中结点的位置位置；top-栈顶指针，初始为栈顶指针，初始为-1；i-遍历过程中使用的遍历过程中使用的位置位置变量，初始时指向根结点。变量，初始时指向根结点。i=1,BT11.若若i指向的结点非空，则将指向的结点非空，则将i进栈，然后，将进栈，然后，将i指向左子树的根；指向左子树的根；2.若若i指向的结点为空，则从堆栈中退出栈顶元素送指向的结点为空，则从堆栈中退出栈顶元素送i，访问该结点，访问该结点，然后，将然后，将i指向右子树的根；指向右子树的根；重复上述过程，直到重复上述过程，直到i为空，并且堆栈也为空。为空，并且堆栈也为空。i=2*i;i=2*i+1;121#defineMaxN100voidINORDER(datatypeBT,intn)intStackMaxN,i=1,top=-1;if(n=0)dowhile(i=n)Stack+top=i;/*BTi的位置进栈的位置进栈*/i=i*2;/*找到找到i的左孩子的位置的左孩子的位置*/i=Stacktop-;/*退栈退栈*/VISIT(BTi);/*访问结点访问结点BTi*/i=i*2+1;/*找到找到i的右孩子的位置的右孩子的位置*/while(i=0);122二叉树的其它操作二叉树的其它操作建议思考以下问题：建议思考以下问题：求二叉树中只有一个孩子的结点个数求二叉树中只有一个孩子的结点个数求二叉树中有两个孩子的结点个数求二叉树中有两个孩子的结点个数复制一棵二叉树复制一棵二叉树交换一棵二叉树的所有左右子树交换一棵二叉树的所有左右子树123二叉树的操作二叉树的操作本节小结本节小结深度优先遍历（包括前、中、后序）深度优先遍历（包括前、中、后序）手工能写出前、中、后序遍历的结果手工能写出前、中、后序遍历的结果要求能够写出递归和非递归的算法要求能够写出递归和非递归的算法广度优先遍历广度优先遍历了解其算法：为什么要用队列了解其算法：为什么要用队列其它操作其它操作能把握大致方向：借助深度优先遍历、递归、广度优能把握大致方向：借助深度优先遍历、递归、广度优先遍历等先遍历等1245.线索二叉树线索二叉树一、线索二叉树的提出一、线索二叉树的提出二叉树的任何一种遍历，其实质均为对非线性结构的二叉树的任何一种遍历，其实质均为对非线性结构的线性化。若将遍历序列中所体现的结点间的线性关系，保线性化。若将遍历序列中所体现的结点间的线性关系，保存在二叉树的存储结构中，则称存在二叉树的存储结构中，则称线索二叉树线索二叉树。1255.线索二叉树线索二叉树241356897【例】设二叉树如图，则其中序遍历序列为：【例】设二叉树如图，则其中序遍历序列为：【问题】【问题】如何保存结点在遍历序列中的线性关系。如何保存结点在遍历序列中的线性关系。126F方案一方案一在在二二叉叉链链表表中中每每个个结结点点上上增增加加两两个个指指针针域域，分分别别用用以以指指向该结点在遍历序列中的直接前驱和直接后继。向该结点在遍历序列中的直接前驱和直接后继。5.线索二叉树线索二叉树二二 叉叉 树树 的的 中中 序序 遍遍 历历 序序 列列 为为 ：21345869T721345869T7127F方案二方案二5.线索二叉树线索二叉树利利用用二二叉叉链链表表中中的的空空链链域域保保存存结结点点间间的的线线性性关关系系：若若结结点点的的lchild域域为为空空，则则保保存存指指向向其其直直接接前前驱驱的的指指针针；若若结结点点的的rchild域为空，则用于保存指向其直接后继的指针。域为空，则用于保存指向其直接后继的指针。为为此此，每每个个结结点点还还需需另另设设两两个个标标志志域域，用用以以指指明明该该结结点点的的lchild域域(rchild域域)中中所所保保存存的的指指针针是是指指向向其其左左(右右)孩孩子子的的，还是指向其直接前驱还是指向其直接前驱(直接后继直接后继)的。的。128二二 叉叉 树树 的的 中中 序序 遍遍 历历 序序 列列 为为 ：5.线索二叉树线索二叉树21345869T721345869T7000000001111111111129二、什么是线索二叉树二、什么是线索二叉树利用二叉链表中空的指针域指出结点在某种遍历序列中的利用二叉链表中空的指针域指出结点在某种遍历序列中的直接前驱和直接后继。指向前驱和后继的指针称为直接前驱和直接后继。指向前驱和后继的指针称为线索线索，加，加了线索的二叉树称为了线索的二叉树称为线索二叉树线索二叉树。三、线索二叉树的构造三、线索二叉树的构造利用链结点的利用链结点的空的左指针域空的左指针域存放该结点的直接前驱的地址，存放该结点的直接前驱的地址，空的右指针域空的右指针域存放该结点的直接后继的地址；而非空的指针存放该结点的直接后继的地址；而非空的指针域仍然存放结点的左孩子或右孩子的地址。域仍然存放结点的左孩子或右孩子的地址。130对下图按照中序遍历进行线索化对下图按照中序遍历进行线索化中序遍历的结果为：中序遍历的结果为：a+b*c-d-e/f称作称作中序线索二叉树中序线索二叉树NULLNULL131对下图按照前序遍历进行线索化对下图按照前序遍历进行线索化前序遍历的结果为：前序遍历的结果为：-+a*b-cd/ef称作称作前序线索二叉树前序线索二叉树NULL132对下图按照后序遍历进行线索化对下图按照后序遍历进行线索化后序遍历的结果为：后序遍历的结果为：abcd-*+ef/-称作称作后序线索二叉树后序线索二叉树NULL133线索二叉树：结点的结构线索二叉树：结点的结构现在现在lchild有有2个功能个功能(1)指向左孩子指向左孩子(2)指向前驱结点指向前驱结点如何区别呢？如何区别呢？增加一个标记增加一个标记ltag说明其当前的功能说明其当前的功能当当ltag=0时：指向左孩子，是时：指向左孩子，是指针指针当当ltag=1时：指向前驱结点，是时：指向前驱结点，是线索线索rchild类似处理类似处理lchildltagdatartagrchild134线索二叉树：结点类型定义线索二叉树：结点类型定义lchildltagdatartagrchildtypedefintdatatype;typedefstructnodedatatypedata;structnode*lchild,*rchild;intltag,rtag;bithptr;135例：例：带了带了两个标志两个标志的某的某前序前序遍历结果如下表所示，请画出对遍历结果如下表所示，请画出对应的二叉树。应的二叉树。dataAGEIDJHCFBLtag0011110101Rtag0001010111AAGEIDJHCFBTag=1表示表示线索线索:Ltag=1表示前驱表示前驱Rtag=1表示后继表示后继1361 a 10 * 01 e 11 f 11 b 10 - 01 c 11 d 10+00 / 00 - 0?中序线索二叉树中序线索二叉树:a+b*c-d-e/f1371 a 10 * 01 e 11 f 11 b 10 - 01 c 11 d 10+00 / 00 - 0头结点头结点01138线索二叉树：中序线索二叉树的遍历线索二叉树：中序线索二叉树的遍历线索化二叉树的目的就在于方便遍历线索化二叉树的目的就在于方便遍历增加头结点增加头结点lchild是指针：指向树根是指针：指向树根rchild是线索：指向中序遍历序列的尾结点是线索：指向中序遍历序列的尾结点同时同时中序遍历序列中的首结点的中序遍历序列中的首结点的lchild和尾结点的和尾结点的rchild都是一个都是一个线索：都指向线索：都指向头结点头结点这样就能方便的进行中序和逆向中序遍历了这样就能方便的进行中序和逆向中序遍历了139例：在中序线索二叉树中查找结点例：在中序线索二叉树中查找结点p的后继结点的后继结点二叉树中序遍历序列二叉树中序遍历序列:a+b*c-d-当当rtag=1时，后继就是时，后继就是p-rchild；-当当rtag=0时，说明时，说明p有右子树，必须沿着有右子树，必须沿着p的右子树的根的左的右子树的根的左子树方向查找，直到某结点的子树方向查找，直到某结点的lchild域为线索域为线索(即，即，p右子树中右子树中最左下角的结点最左下角的结点)，此结点就是，此结点就是p结点的后继结点的后继。p四、线索二叉链表的应用四、线索二叉链表的应用+-*abdc140中序线索二叉树查找结点中序线索二叉树查找结点p的后继结点算法的后继结点算法bithptr*InOrderNext(bithptr*p)bithptr*q;if(p-rtag=1)return(p-rchild);elseq=p-rchild;while(q-ltag=0)q=q-lchild;return(q);+-*abdc141回顾二叉树的中序遍历：非递归算法回顾二叉树的中序遍历：非递归算法intInOrderT(bitree*T)bitree*p=T;SqStack*S;InitStack(S); 建栈建栈while(p|!StackEmpty(s)if(p)Push(S,p); 二叉树非空，根结点进栈二叉树非空，根结点进栈p=p-lchild; 遍历左子树遍历左子树elsePop(S,p);Visit(p-data);p=p-rchild; 遍历右子树遍历右子树returnOK;142中序线索二叉树的遍历中序线索二叉树的遍历(顺后继进行顺后继进行)基本思想基本思想第一个访问的结点应该是最左下角的结点第一个访问的结点应该是最左下角的结点(假设为假设为p)然后然后p的后继是谁？的后继是谁？若若p-rchild是指针是指针(0)，说明，说明p有右子树，下一个结点有右子树，下一个结点应该是应该是p右子树中最左下角的结点右子树中最左下角的结点若若p-rchild是线索是线索(1)，直接访问，直接访问p-rchild如此循环往复如此循环往复.143中序线索二叉树的遍历算法中序线索二叉树的遍历算法intInOrderTraverse_Thr(bithptr*T)p=T-lchild;/p指向树根指向树根while(p!=T)/p等于等于T则说明已经遍历完毕则说明已经遍历完毕while(p-ltag=0)/p-lchild为指针为指针p=p-lchild;/则向左下走到底则向左下走到底Visit(p-data);/访问访问pwhile(p-rtag=1&p-rchild!=T)/p-rchild为线索为线索p=p-rchild;Visit(p-data);/访问访问pp=p-rchild;/向右继续遍历向右继续遍历returnOK;144中序线索二叉树的遍历中序线索二叉树的遍历思考：思考：如果反方向进行遍历呢如果反方向进行遍历呢(顺前驱进行顺前驱进行)？第一个访问的结点应该是最右下角的结点第一个访问的结点应该是最右下角的结点(假设为假设为p)然后然后p的前驱是谁？的前驱是谁？若若p-lchild是指针，说明是指针，说明p有有左左子树，前驱应该是子树，前驱应该是p左左子子树中最树中最右右下角的结点下角的结点若若p-lchild是线索，直接访问是线索，直接访问p-lchild如此循环往复如此循环往复.145以后序线索二叉树为例以后序线索二叉树为例第一个访问的应该是最左下角的结点第一个访问的应该是最左下角的结点(假设为假设为p)，p的的后继是谁？后继是谁？p线索二叉树：前线索二叉树：前/后序线索二叉树的遍历后序线索二叉树的遍历146解答解答若若p-rchild是线索是线索则后继就是则后继就是p-rchild否则否则若若p是树根，则无后继是树根，则无后继若若p是右孩子或者是唯一的左孩子，是右孩子或者是唯一的左孩子，则后继是其父结点则后继是其父结点若若p是左孩子，且有右兄弟，则后是左孩子，且有右兄弟，则后继是继是p的父结点的右子树中第一个的父结点的右子树中第一个访问的结点访问的结点pppp线索二叉树：前线索二叉树：前/后序线索二叉树的遍历后序线索二叉树的遍历147线索二叉树：前线索二叉树：前/后序线索二叉树的遍历后序线索二叉树的遍历困难困难对于后序线索二叉树，想要找结点对于后序线索二叉树，想要找结点p的后继结点，可能需的后继结点，可能需要知道要知道p的父结点是谁的父结点是谁可是这是很难办到的可是这是很难办到的两种方法两种方法从树根开始查找从树根开始查找改用三叉链表来表示二叉树改用三叉链表来表示二叉树此困难对于后序线索二叉树找前驱结点、前序线索二叉树此困难对于后序线索二叉树找前驱结点、前序线索二叉树找后继找后继/前驱结点同样存在前驱结点同样存在p148五、线索二叉树：二叉树的线索化五、线索二叉树：二叉树的线索化普通的二叉树怎么变成线索二叉树？普通的二叉树怎么变成线索二叉树？称作线索化称作线索化基本思想基本思想线索其实就是按照遍历的顺序把闲置的指针链接到前驱线索其实就是按照遍历的顺序把闲置的指针链接到前驱/后继结点：后继结点：遍历过程中维护两个指针：遍历过程中维护两个指针：pre和和p，分别指向遍历序列中，分别指向遍历序列中一前一后的两个结点一前一后的两个结点若若pre-rchild闲置，闲置，pre-rchild=p若若p-lchild闲置，闲置，p-lchild=pre149StatusInOrderThreading(Bitree*Thrt,Bitree*T)Thrt=(Bitree*)malloc(sizeof(bithptr);/头结点头结点if(!Thrt)exit(OVERFLOW);Thrt-ltag=0;/头结点的头结点的lchild是指针是指针Thrt-rtag=1;/头结点的头结点的rchild是线索是线索if(!T)/若若T为空树，头结点的左右指针回指为空树，头结点的左右指针回指Thrt-lchild=Thrt;Thrt-rchild=Thrt;elseThrt-lchild=T;/头结点的头结点的lchild指向树根指向树根pre=Thrt;/pre是全局变量是全局变量InThreading(T);/调用中序线索化函数处理二叉树调用中序线索化函数处理二叉树Tpre-rchild=Thrt;/InThreading调用完以后调用完以后pre-rtag=1;/就差最后一个结点没有链接好就差最后一个结点没有链接好Thrt-rchild=pre;/此时，此时，pre指向最后一个结点指向最后一个结点returnOK;创建中序线索二叉创建中序线索二叉树的头结点树的头结点头结点与树根之间的连接头结点与树根之间的连接修改中序遍历的最后一个结点修改中序遍历的最后一个结点与头结点之间的连接与头结点之间的连接150voidInThreading(Bitree*p)if(p)/p为空则返回为空则返回InThreading(p-lchild);/左子树线索化左子树线索化if(!p-lchild)/若若p-lchild闲置闲置p-lchild=pre;p-ltag=1;if(!pre-rchild)/若若pre-rchild闲置闲置pre-rchild=p;pre-rtag=1;pre=p;/维持维持pre和和p一前一后的关系一前一后的关系InThreading(p-rchild);/右子树线索化右子树线索化151voidInThreading(Bitree*p)if(p) InThreading(p-lchild);if(!p-lchild)p-lchild=pre;p-ltag=1; if(!pre-rchild)pre-rchild=p;pre-rtag=1; pre=p;InThreading(p-rchild);ABC头结点头结点prep以以p-lchild为参数为参数递归调用递归调用此时的此时的p就是就是A-lchild(B)以以p-lchild为参数为参数递归调用递归调用此时的此时的p就是就是B-lchild此时此时p-lchild(B-lchild)闲闲置，应作为线索，指向置，应作为线索，指向pre此时此时pre-rchild闲置闲置应作为线索，指向应作为线索，指向p注意：这次操作是无效的注意：这次操作是无效的pre跟进跟进以以p-rchild为参数为参数递归调用递归调用调用完毕调用完毕p-lchild不闲置不闲置pre-rchild闲置闲置应作为索引，指向应作为索引，指向ppre跟进跟进以以p-rchild为参数为参数递归调用递归调用p以以p-lchild为参数为参数递归调用递归调用此时此时p-lchild闲置闲置应作为线索，指向应作为线索，指向prepre-rchild不闲置不闲置pre跟进跟进pre以以p-rchild为参数为参数递归调用递归调用152StatusInOrderThreading(Bitree*Thrt,Bitree*T).InThreading(T);pre-rchild=Thrt;pre-rtag=1;Thrt-rchild=pre;returnOK;ABC头结点头结点prepre此时指向遍历序列的最后此时指向遍历序列的最后一个结点，一个结点，pre-rchild应作应作为线索，指向头结点为线索，指向头结点头结点的头结点的rchild应指向遍历应指向遍历序列的最后结点序列的最后结点程序结束程序结束调用完毕调用完毕153例：例：画出二叉链表存储结构上的画出二叉链表存储结构上的中序中序线索二叉树。线索二叉树。中序遍历序列中序遍历序列:H,D,I,B,E,A,F,C,G0A00B00C00D01E11F11G11H11I1root01154前序线索树上找前驱和后继前序线索树上找前驱和后继找前驱：找前驱：困难，需要知道其双亲。困难，需要知道其双亲。找后继找后继： 若结点有左子女，则左子女是后继；否则，若结点有左子女，则左子女是后继；否则，rchild指指向后继。向后继。155中序的前驱和后继都往上指向祖先中序的前驱和后继都往上指向祖先找前驱：找前驱：若左标记为若左标记为1，则，则lchild指向其前驱；否则，其前驱是其左子指向其前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。树上按中序遍历的最后一个结点。找后继找后继：若右标记为若右标记为1，则，则rchild指向其后继；否则，其后继是其右子指向其后继；否则，其后继是其右子树上按中序遍历的第一个结点。树上按中序遍历的第一个结点。中序线索树上找前驱和后继中序线索树上找前驱和后继156后序线索树上找前驱和后继后序线索树上找前驱和后继找前驱：找前驱：若结点有右子女，则右子女是其前驱；否则，若结点有右子女，则右子女是其前驱；否则，lchild指向其前驱。指向其前驱。找后继找后继：困难，需要知道其双亲。困难，需要知道其双亲。157线索树上结点的插入与删除线索树上结点的插入与删除除修改结点指针外，除修改结点指针外，还需要修改线索。还需要修改线索。1586.树和森林：回顾树和森林：回顾树：树：如果如果n0，则，则有一个特定的称之为根有一个特定的称之为根(root)的结点，它只有直接后继，的结点，它只有直接后继，但没有直接前驱但没有直接前驱除根以外的其它结点划分为除根以外的其它结点划分为m(m=0)个互不相交的有限个互不相交的有限集合集合T0,T1,Tm-1，每个集合又是一棵树，并且称之为根，每个集合又是一棵树，并且称之为根的子树的子树森林森林m(m=0)棵互不相交的树的集合棵互不相交的树的集合159树的存储结构树的存储结构l顺序存储结构顺序存储结构l链式存储结构链式存储结构(居多居多)主要取决于要对树主要取决于要对树进行何种操作进行何种操作无论采用何种存储结构，需要存储的信息有：无论采用何种存储结构，需要存储的信息有：l结点本身的数据信息；结点本身的数据信息；l结点之间存在的关系结点之间存在的关系(分支分支)。160树的存储结构：孩子表示法树的存储结构：孩子表示法孩子表示法孩子表示法每个结点可以有多个孩子每个结点可以有多个孩子方法一：定长结点的多重链表结构方法一：定长结点的多重链表结构问题：问题：因因n为树的度，是所有结点的最大的度，因此树中有相当部为树的度，是所有结点的最大的度，因此树中有相当部分的指针域为空，浪费空间。分的指针域为空，浪费空间。有有n个结点的树的度为个结点的树的度为k，空指针域有，空指针域有n(k-1)+1个。个。datachild1child2child3.childnn为树的度为树的度161树的存储结构：孩子表示法树的存储结构：孩子表示法孩子表示法孩子表示法每个结点可以有多个孩子每个结点可以有多个孩子方法二：方法二：不定长不定长结点的多重链表结构结点的多重链表结构问题：问题：量体裁衣，节省存储空间量体裁衣，节省存储空间不同的数据元素，结点构造不同；不同的数据元素，结点构造不同；操作不方便。操作不方便。datadegreechild1child2.childn结点的度结点的度162树的存储结构：孩子表示法树的存储结构：孩子表示法孩子表示法孩子表示法每个结点可以有多个孩子每个结点可以有多个孩子方法三：方法三：用一个静态数组用一个静态数组，存放所有的结点，存放所有的结点数组的每个数据元素，包括两部分：数组的每个数据元素，包括两部分：数据元素，指针数据元素，指针；指针指；指针指向一个链表，链表结点的数据域是一个整数，表示该结点的孩向一个链表，链表结点的数据域是一个整数，表示该结点的孩子在子在数组中的下标数组中的下标；特点：特点：顺序顺序+链式存储结构；链式存储结构；找孩子容易，找双亲难；找孩子容易，找双亲难；163树的存储结构：孩子表示法树的存储结构：孩子表示法bdaefcnum6a0MAX-1nodes2c3d4e5f1b【例】【例】34512 164还可以增加双亲信息还可以增加双亲信息(孩子孩子-双亲表示法双亲表示法)bdaefcnum6a0MAX-1nodes2c3d4e5f1b-10110134512 【例】【例】165双亲表示法双亲表示法树中一个结点的孩子的数量不定树中一个结点的孩子的数量不定但是双亲却只有一个但是双亲却只有一个所以保存每个结点的双亲所以保存每个结点的双亲0bdaefcnum6-10111a0MAX-1nodes2c3d4e5f1b【例】【例】优点优点查找双亲、树根操作很快查找双亲、树根操作很快缺点缺点查找孩子操作慢，需遍历整个结构查找孩子操作慢，需遍历整个结构树的存储结构：双亲表示法树的存储结构：双亲表示法166从向下的纵向和向右的横向描述树；从向下的纵向和向右的横向描述树；定义结点结构定义结点结构:数据元素和两个指针。一个指向该结点的数据元素和两个指针。一个指向该结点的第一个孩子第一个孩子，另一个指向该结点的，另一个指向该结点的下一个兄弟下一个兄弟；firstchilddatanextsibling第一个儿子第一个儿子下一个兄弟下一个兄弟又称二叉树表示法又称二叉树表示法树的存储结构：孩子兄弟表示法树的存储结构：孩子兄弟表示法167即左孩子、右兄弟表示法即左孩子、右兄弟表示法用二叉树来表示树用二叉树来表示树左指针指向其大儿子左指针指向其大儿子右指针指向其兄弟右指针指向其兄弟树的存储结构：孩子兄弟表示法树的存储结构：孩子兄弟表示法168树、森林和二叉树的转换树、森林和二叉树的转换转换步骤：转换步骤：step1:将树中同一结点的兄弟相连；将树中同一结点的兄弟相连；step2:保留结点的最左孩子连线，删除其它孩子连线；保留结点的最左孩子连线，删除其它孩子连线；step3:将同一孩子的连线绕左孩子旋转将同一孩子的连线绕左孩子旋转45度角。度角。加线加线抹线抹线旋转旋转讨论讨论1：树如何转为二叉树？：树如何转为二叉树？169abcdefgih树转二叉树举例：方法：方法：加线加线抹线抹线旋转旋转兄弟相连兄弟相连长兄为父长兄为父孩子靠左孩子靠左abcdefgih特点是？特点是？根结点没有右孩子！根结点没有右孩子！170森林到二叉树的转换森林到二叉树的转换若若树采用孩子兄弟表示法树采用孩子兄弟表示法，二叉树采用二叉链表表示，则：，二叉树采用二叉链表表示，则：任一棵树，都可以找到唯一的一棵二叉树和它对应，而且该任一棵树，都可以找到唯一的一棵二叉树和它对应，而且该二叉树没有右子树。二叉树没有右子树。若把森林中的第二棵树的根结点，看成是第一棵树的根结点若把森林中的第二棵树的根结点，看成是第一棵树的根结点的兄弟结点，则这两棵树可以转换为一棵二叉树（该二叉树的兄弟结点，则这两棵树可以转换为一棵二叉树（该二叉树的根结点的右子女没有右子树）。的根结点的右子女没有右子树）。依次类推，可以认为森林和二叉树是一一对应的，从而得到依次类推，可以认为森林和二叉树是一一对应的，从而得到二叉树和森林的转换规则。二叉树和森林的转换规则。171树、森林和二叉树的转换树、森林和二叉树的转换讨论讨论2：森林如何转为二叉树？：森林如何转为二叉树？方法一：方法一：(1)把森林中的每一棵树转换为二叉树把森林中的每一棵树转换为二叉树(用孩子兄弟表示法用孩子兄弟表示法)(2)把所有的二叉树合并为一棵二叉树把所有的二叉树合并为一棵二叉树172(1)把森林中的每一棵树转换为二叉树把森林中的每一棵树转换为二叉树(用孩子兄弟表示法用孩子兄弟表示法)(2)把所有的二叉树合并为一棵二叉树把所有的二叉树合并为一棵二叉树森林和二叉树的转换森林和二叉树的转换ABCDEFGHIJ173方法二：方法二：森林直接变兄弟，再转为二叉树森林直接变兄弟，再转为二叉树森林和二叉树的转换森林和二叉树的转换ABCDEFGHIJ兄弟相连兄弟相连长兄为父长兄为父头树为根头树为根孩子靠左孩子靠左A A法一和法二得到的二叉法一和法二得到的二叉树是完全相同的、唯一树是完全相同的、唯一的。的。ABCDEFGHIJ174树、森林和二叉树的转换树、森林和二叉树的转换讨论讨论3：二叉树怎样还原为树：二叉树怎样还原为树要点：要点：逆操作，把逆操作，把所有右孩子变为兄弟所有右孩子变为兄弟！abcdefgihabcdefgih175树、森林和二叉树的转换树、森林和二叉树的转换(1)抹线抹线;(2)还原还原.讨论讨论4：二叉树如何还原为森林？：二叉树如何还原为森林？要点：要点：把最右边的子树变为森林，其余右子树变为兄弟把最右边的子树变为森林，其余右子树变为兄弟ABCDEFGHIJABCDEFGHIJ176二叉树到森林的转换二叉树到森林的转换DEFGHIJLABCKDKGHJABECFIL177树的遍历树的遍历深度优先遍历深度优先遍历(前根、后根前根、后根)广度优先遍历广度优先遍历(层次层次)后根遍历后根遍历按照从左到右依次后根遍历根结点的每棵子树；按照从左到右依次后根遍历根结点的每棵子树；访问根结点。访问根结点。树的遍历树的遍历前根遍历前根遍历访问根结点；访问根结点；按照从左到右依次前根遍历根结点的每棵子树。按照从左到右依次前根遍历根结点的每棵子树。1781、树的前根遍历、树的前根遍历(1)访问树的根结点；访问树的根结点；(2)从左至右，依次前根遍历根的每棵子树。从左至右，依次前根遍历根的每棵子树。【例】【例】beadfhigcj遍历序列：遍历序列：beadfhigcj1792、树的后根遍历、树的后根遍历(1)从左至右，依次后根遍历根的每棵子树；从左至右，依次后根遍历根的每棵子树；(2)访问树的根结点。访问树的根结点。【例】【例】beadfhigcj遍历序列：遍历序列：beadfhigcj180问题问题树的中根遍历呢？树的中根遍历呢？“中中”在哪里？在哪里？子树不分左右子树不分左右注意：注意：树的遍历中的树的遍历中的“前根前根”“后根后根”指的是树根和它的孩子相比，指的是树根和它的孩子相比，谁先谁后谁先谁后树的遍历树的遍历181讨论：讨论：树若采用树若采用“先转换，后遍历先转换，后遍历”方式，结果是否一样？方式，结果是否一样？前序遍历：前序遍历：后序遍历：后序遍历：中序遍历：中序遍历：EDKHGFCBARRADEBCFGHKDEABGHKFCR树的前根序列：树的前根序列：RADEBCFGHK树的后根序列：树的后根序列：DEABGHKFCR182结论：结论：树的树的前根前根遍历遍历=等价二叉树的等价二叉树的前序前序遍历遍历树的树的后根后根遍历遍历=等价二叉树的等价二叉树的中序中序遍历遍历树没有中序遍历，因为子树无左右之分。树没有中序遍历，因为子树无左右之分。183遍历序列：遍历序列：【例】【例】bdaheijfckgbdaheijfckg森林的前序遍历森林的前序遍历先访问森林中第一棵树的树根先访问森林中第一棵树的树根再前序遍历第一棵树中树根的子树森林再前序遍历第一棵树中树根的子树森林最后前序遍历剩余的树构成的森林最后前序遍历剩余的树构成的森林3.森林的前序遍历森林的前序遍历184森林的后序遍历森林的后序遍历先后序遍历第一棵树中树根的子树森林先后序遍历第一棵树中树根的子树森林再访问森林中第一棵树的树根再访问森林中第一棵树的树根最后后序遍历剩余的树构成的森林最后后序遍历剩余的树构成的森林3.森林的后序遍历森林的后序遍历遍历序列：遍历序列：【例】【例】bdaheijfckgbdaheijfckg185森林的前序遍历相当于对每棵树依次进行树的前根遍历森林的前序遍历相当于对每棵树依次进行树的前根遍历:(1)(2)(3)(1)(2)(3)森林的后序遍历相当于对每棵树依次进行树的后根遍历森林的后序遍历相当于对每棵树依次进行树的后根遍历:(2)(1)(3)森林的遍历森林的遍历186森林的森林的前序前序遍历遍历=等价二叉树的等价二叉树的前序前序遍历遍历森林的森林的后序后序遍历遍历=等价二叉树的等价二叉树的中序中序遍历遍历(1)(2)(3)(1)(2)(3)森林的遍历及其等价二叉树的遍历森林的遍历及其等价二叉树的遍历187如图所示二叉树，回答下列问题如图所示二叉树，回答下列问题:(1)写出其前序、中序、后序遍历序列写出其前序、中序、后序遍历序列(2)画出此二叉树的中序线索二叉树画出此二叉树的中序线索二叉树(3)画出此二叉树对应的森林。画出此二叉树对应的森林。ACFBDGEHI练习：练习：前序序列前序序列:ABDGCEFHI中序序列中序序列:DGBAECHIF后序序列后序序列:GDBEIHFCANULLNULLABDGCEFHI188已知一个森林的前序序列和后序序列如下，请构造出该森林。已知一个森林的前序序列和后序序列如下，请构造出该森林。前序序列：前序序列：ABCDEFGHIJKLMNO后序序列：后序序列：CDEBFHIJGAMLONK自测题自测题1897.赫夫曼树及其应用赫夫曼树及其应用一、一、Huffman树树(最优二叉树最优二叉树)二、二、Huffman编码编码(不等长编码不等长编码)带权路径长带权路径长度最短的树度最短的树是通信中最经是通信中最经典的压缩编码典的压缩编码1907.赫夫曼树及其应用赫夫曼树及其应用ACFBDGE路径路径从一个结点到另一个结点的分支构成从一个结点到另一个结点的分支构成路径长度路径长度路径上的分支的个数路径上的分支的个数例如：例如：AE的路径长度的路径长度=2树的路径长度树的路径长度从树根到每一个结点的路径长度之和从树根到每一个结点的路径长度之和树长度树长度=1*2+2*2+2*3=121917.赫夫曼树及其应用赫夫曼树及其应用以下我们只讨论二叉树以下我们只讨论二叉树问题：问题：树的路径长度最短的是哪一种？树的路径长度最短的是哪一种？完全二叉树完全二叉树192权权(weight)给结点赋予一定的数值给结点赋予一定的数值结点的带权路径长度结点的带权路径长度从树根到该结点的路径长度从树根到该结点的路径长度该结点的权该结点的权树的带权路径长度树的带权路径长度WeightedPathLength所有所有叶结点叶结点的带权路径长度之和的带权路径长度之和WPL=7.赫夫曼树及其应用赫夫曼树及其应用193例例:计算下列二叉树的计算下列二叉树的WPL值值Huffman树是树是WPL最小的树最小的树7.赫夫曼树及其应用赫夫曼树及其应用194赫夫曼树的性质赫夫曼树的性质赫夫曼树只有度为赫夫曼树只有度为0和和2的结点，无度为的结点，无度为1的结点；的结点；权值大的结点离根结点近；权值大的结点离根结点近；n个叶子的赫夫曼树的形态一般不唯一，但个叶子的赫夫曼树的形态一般不唯一，但WPL是相同的；是相同的；n个叶子的赫夫曼树共有个叶子的赫夫曼树共有2n-1个结点。个结点。195最优二叉树最优二叉树(又称赫夫曼树又称赫夫曼树)已知有已知有n个权值个权值w1,w2,.,wn构造一棵有构造一棵有n个叶结点的二叉树，每个叶结点的权值为个叶结点的二叉树，每个叶结点的权值为wi其中其中WPL最小的那一棵称作最优二叉树，即赫夫曼树最小的那一棵称作最优二叉树，即赫夫曼树最优又能怎样？最优又能怎样？7.赫夫曼树及其应用赫夫曼树及其应用196例：例：一个判断成绩等级的程序一个判断成绩等级的程序if(a60)b=“不及格不及格”elseif(a70)b=“及格及格”elseif(a80)b=“中等中等”elseif(a90)b=“良好良好”elseb=“优秀优秀”一个一个a最多最多要经过要经过4次比较才能得出次比较才能得出b我们当然希望比较的总次数最小我们当然希望比较的总次数最小7.赫夫曼树及其应用赫夫曼树及其应用197假设有如下统计数据假设有如下统计数据原判定树为：原判定树为：分数分数0-5960-6970-7980-8990-100概率概率0.050.150.400.300.10若一共有若一共有10000个输入数据个输入数据则总共的比较次数则总共的比较次数=500*1+1500*2+4000*3+3000*4+1000*4=31500198构造一棵赫夫曼树构造一棵赫夫曼树有有5个叶结点，权值分别为：个叶结点，权值分别为：0.05(不及格不及格),0.15(及格及格),0.4(中等中等),0.3(良好良好),0.1(优秀优秀)判断成绩等级的程序图示如下：判断成绩等级的程序图示如下：199根据这棵赫夫曼树导出新的判定树：根据这棵赫夫曼树导出新的判定树：总的比较次数总的比较次数=500*3+1500*3+4000*2+3000*2+1000*2=2200031500200构造赫夫曼树构造赫夫曼树(1)根据给定的根据给定的n个权值个权值w1,w2,wn构成构成n棵二叉树的集合棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树只含一个带权的根结点，其左右，其中每棵二叉树只含一个带权的根结点，其左右子树均空；子树均空；赫夫曼算法：赫夫曼算法：d7a1c5b3F201构造赫夫曼树构造赫夫曼树(2)在在F中选两棵根结点的权值最小的二叉树作为左右子树，构造中选两棵根结点的权值最小的二叉树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和；树上根结点的权值之和；赫夫曼算法：赫夫曼算法：d7a1c5b3Fab134202构造赫夫曼树构造赫夫曼树(3)在在F中删除这两棵二叉树，同时将新得到的二叉树加入中删除这两棵二叉树，同时将新得到的二叉树加入F；赫夫曼算法：赫夫曼算法：d7a1c5b3Fab134203构造赫夫曼树构造赫夫曼树(4)重复重复(2)和和(3)，直到，直到F只含一棵二叉树，此即最优二叉树。只含一棵二叉树，此即最优二叉树。赫夫曼算法：赫夫曼算法：d7c5Fab134ab134c59ab134c95d167F2047.赫夫曼树及其应用赫夫曼树及其应用理解理解为什么赫夫曼树的带权路径长度最小？为什么赫夫曼树的带权路径长度最小？它把权值小的结点放在底层它把权值小的结点放在底层权值大的结点放在上层权值大的结点放在上层练习：练习：给给定定权权值值7,6,3,32,5,26,12,9，构构造造相相应应的的哈哈夫夫曼曼树树，并并计计算算其其带带权权路路径径长长度度。为为使使结结果果答答案案尽尽可可能能唯唯一一，请请用用左左结结点点的的值值小于等于右结点的值来构造哈夫曼树。小于等于右结点的值来构造哈夫曼树。205赫夫曼树的类型定义赫夫曼树的类型定义typedefstructintweight;intparent,lchild,rchild;HufmTree;206赫夫曼树的应用赫夫曼树的应用赫夫曼编码赫夫曼编码问题：问题：设某系统在通信联络中只可能出现八种字符，它们的出现概设某系统在通信联络中只可能出现八种字符，它们的出现概率分别为率分别为0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11，要求设计这些字符的二进制编码，以使通信中总码长尽可，要求设计这些字符的二进制编码，以使通信中总码长尽可能短。能短。207赫夫曼树的应用赫夫曼树的应用赫夫曼编码赫夫曼编码分析：分析：设这八个字符分别为设这八个字符分别为A(0.05)、B(0.29)、C(0.07)、D(0.08)、E(0.14)、F(0.23)、G(0.03)、H(0.11)。若用等长编码，则每个字符码长若用等长编码，则每个字符码长3位：位：若传递若传递10000个字符，则总码长为个字符，则总码长为位。位。A=000B=001C=010D=011E=100F=101G=110H=11130000若接收若接收001101010，应如何解释？，应如何解释？208赫夫曼树的应用赫夫曼树的应用赫夫曼编码赫夫曼编码分析：分析：设这八个字符分别为设这八个字符分别为A(0.05)、B(0.29)、C(0.07)、D(0.08)、E(0.14)、F(0.23)、G(0.03)、H(0.11)。若用不等长编码，则应使常用字符码长较短。若用不等长编码，则应使常用字符码长较短。B=0F=1E=00H=01D=10C=11A=000G=001若接收若接收001101010，应如何解释？，应如何解释？若传递若传递10000个字符，则总码长为个字符，则总码长为位。位。15600209赫夫曼树的应用赫夫曼树的应用赫夫曼编码赫夫曼编码赫夫曼编码的由来赫夫曼编码的由来通讯使用电报码；通讯使用电报码；如何避免一个编码是另一个编码的前缀；如何避免一个编码是另一个编码的前缀；赫夫曼编码方案赫夫曼编码方案以字符出现频率为权值，构造赫夫曼二叉树；以字符出现频率为权值，构造赫夫曼二叉树；约定以左分支表示约定以左分支表示0，右分支表示，右分支表示1，把从根到叶子的路，把从根到叶子的路径上所有分支构成的径上所有分支构成的01串作为叶子的二进制编码，即为串作为叶子的二进制编码，即为赫夫曼编码。赫夫曼编码。210赫夫曼树的应用赫夫曼树的应用赫夫曼编码赫夫曼编码例：例：d0.08a0.05c0.07b0.29h0.11e0.14g0.03f0.230.150.290.080.190.580.421211例：例：dacbhegf10101010101010a(0.05):0001b(0.29):10c(0.07):1110d(0.08): 1111e(0.14):110f(0.23): 01g(0.03):0000h(0.11): 001赫夫曼树的应用赫夫曼树的应用赫夫曼编码赫夫曼编码212例：例：a(0.05): 0001b(0.29):10c(0.07): 1110d(0.08):1111e(0.14): 110f(0.23): 01g(0.03):0000h(0.11): 001此时传递此时传递10000个字符的总码长个字符的总码长500*427100 30000+2900*2 +700*4+800*4+1400*3 +2300*3+300*4 +1100*3赫夫曼树的应用赫夫曼树的应用赫夫曼编码赫夫曼编码213赫夫曼树的应用赫夫曼树的应用赫夫曼编码赫夫曼编码Huffman树树中，一定没有度为中，一定没有度为1的结点，因此有的结点，因此有n个结点的个结点的Huffman树，一定有树，一定有2n-1个结点。个结点。在在编码编码中，需要从中，需要从叶子叶子结点出发，走从结点出发，走从叶子叶子到到根根的路径；的路径；译译码码中，需要从中，需要从根根到到叶子叶子。214假假设设用用于于通通信信的的电电文文由由字字符符集集a,b,c,d,e,f,g,h中中的的字字母母构构成成 ， 这这 8个个 字字 母母 在在 电电 文文 中中 出出 现现 的的 概概 率率 分分 别别 为为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。(1)为这为这8个字母设计哈夫曼编码。个字母设计哈夫曼编码。(2)若若用用这这三三位位二二进进制制数数(07)对对这这8个个字字母母进进行行等等长长编编码码，则则哈哈夫夫曼曼编编码码的的平平均均码码长长是是等等长长编编码码的的百百分分之之几几?它它使使电电文文总总长长平均压缩多少平均压缩多少?自测题自测题215(1)根根 据据 左左 图图 可可 得得 编编 码码 表表 ：a:1001b:01c:10111d:1010e:11f:10110g:00h:1000(2)用用三三位位二二进进行行数数进进行行的的等等长长编编码码平平均均长长度度为为3，而而根根据据哈哈夫夫曼曼树树编编码码的的平平均均码码长长为为：4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.612.61/3=0.87=87%其平均码长是等长码的其平均码长是等长码的87%，所以平均压缩率为，所以平均压缩率为13%。216本章总结本章总结一、树的类型定义一、树的类型定义树是递归定义的树是递归定义的子树也是树子树也是树相关术语可以类比家族树来记忆相关术语可以类比家族树来记忆二、二叉树的类型定义二、二叉树的类型定义相关术语要注意跟树做对比相关术语要注意跟树做对比孩子最多两个孩子最多两个而且要分左右而且要分左右5个性质要牢记并且会推导个性质要牢记并且会推导三、二叉树的存储结构三、二叉树的存储结构顺序存放顺序存放简单，但是空间浪费大简单，但是空间浪费大二叉链表二叉链表常用常用三叉链表三叉链表找父亲很快找父亲很快217本章总结本章总结四、二叉树的操作四、二叉树的操作遍历操作遍历操作遍历的定义是递归的遍历的定义是递归的算法当然也可以递归算法当然也可以递归非递归的话要借助堆栈非递归的话要借助堆栈层序遍历要借助队列层序遍历要借助队列其它操作其它操作基本方法无外乎是深度、广度和递归基本方法无外乎是深度、广度和递归218本章总结本章总结五、线索二叉树五、线索二叉树叶子的指针的闲置叶子的指针的闲置只有一个孩子的结点也有一个指针闲置只有一个孩子的结点也有一个指针闲置因此利用它来帮助遍历因此利用它来帮助遍历遍历的算法是要会写遍历的算法是要会写一些不足也要知道一些不足也要知道前序前序/后序线索二叉树难以找后继后序线索二叉树难以找后继/前驱结点前驱结点因为二叉链表找父亲不方便因为二叉链表找父亲不方便219六、树和森林六、树和森林树的表示方法多样树的表示方法多样各种方法的各有优劣各种方法的各有优劣要求手工能画出来就可以了要求手工能画出来就可以了树、森林树、森林二叉树相互转化二叉树相互转化树和森林的遍历要注意树和森林的遍历要注意方法和二叉树有点儿不同方法和二叉树有点儿不同本章总结本章总结220七、赫夫曼树七、赫夫曼树赫夫曼树的相关概念赫夫曼树的相关概念手工构造要掌握手工构造要掌握应用：赫夫曼编码应用：赫夫曼编码本章总结本章总结221