第7章树形结构.ppt

《第7章树形结构.ppt》由会员分享，可在线阅读，更多相关《第7章树形结构.ppt（144页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第7 7章章 树形结构树形结构7.1 7.1 树的基本概念树的基本概念 7.2 7.2 二叉树概念和性质二叉树概念和性质7.3 7.3 二叉树存储结构二叉树存储结构7.4 7.4 二叉树的遍历二叉树的遍历7.5 7.5 二叉树的基本运算及其实现二叉树的基本运算及其实现7.6 7.6 二叉树的构造二叉树的构造7.8 7.8 哈夫曼树哈夫曼树 本章本章小结小结7.7 7.7 线索二叉树线索二叉树7.9 7.9 并查集并查集 7.1 7.1 树的基本概念树的基本概念 7.1.1 7.1.1 树的定义树的定义 7.1.3 7.1.3 树的基本术语树的基本术语 7.1.2 7.1.2 树的表示树的表示

2、7.1.4 7.1.4 树的性质树的性质7.1.5 7.1.5 树的基本运算树的基本运算7.1.6 7.1.6 树的存储结构树的存储结构7.1.1 7.1.1 树的定义树的定义形式化定义：形式化定义：树树：TK,R。K是是包包含含n个个结结点点的的有有穷穷集集合合(n0),关系关系R满足以下条件满足以下条件:(1)有有且且仅仅有有一一个个结结点点k0K,它它对对于于关关系系R来来说说没有前驱结点没有前驱结点,结点结点k0称作树的根。称作树的根。(2)除除结结点点k0外外,K中中的的每每个个结结点点对对于于关关系系R来来说说都有且仅有一个前驱结点。都有且仅有一个前驱结点。(3)K中中每每个个结结

3、点点对对于于关关系系R来来说说可可以以有有多多个个后后继结点。继结点。递归定义：递归定义：树树是是由由n(n0)个个结结点点组组成成的的有有限限集集合合(记记为为T)。其其中中,如果如果n=0,它是一棵空树它是一棵空树,这是树的特例；这是树的特例；如如果果n0,这这n个个结结点点中中存存在在(有有仅仅存存在在)一一个个结结点点作作为为树树的的根根结结点点,简简称称为为根根(root),其其余余结结点点可可分分为为m(m0)个个互互不不相相交交的的有有限限集集T1,T2,Tm,其其中中每每一一棵棵子子集集本本身身又又是是一一棵棵符符合合本本定定义义的的树树,称称为为根根root的的子子树。树。7

4、.1.2 7.1.2 树的表示树的表示 (1)树树形形表表示示法法。这这是是树树的的最最基基本本的的表表示示,使使用用一一棵棵倒倒置置的的树树表表示示树树结结构构,非非常常直直观观和和形形象象。下下图图就就是是采用这种表示法。采用这种表示法。(2)文文氏氏图图表表示示法法。使使用用集集合合以以及及集集合合的的包包含含关关系系描描述述树树结结构构。下下图图就就是是树树的的文文氏氏图表示法。图表示法。(3)凹凹入入表表示示法法。使使用用线线段段的的伸伸缩缩描描述述树树结结构。下图是树的凹入表示法。构。下图是树的凹入表示法。(4)括括号号表表示示法法。将将树树的的根根结结点点写写在在括括号号的的左左

5、边边,除除根根结结点点之之外外的的其其余余结结点点写写在在括括号号中中并并用用逗号间隔来描述树结构。下图是树的括号表示法。逗号间隔来描述树结构。下图是树的括号表示法。7.1.3 7.1.3 树的基本术语树的基本术语1.结结点点的的度度与与树树的的度度：树树中中某某个个结结点点的的子子树树的的个个数数称称为为该该结结点点的的度度。树树中中各各结结点点的的度度的的最最大大值值称称为为树的度树的度,通常将度为通常将度为m的树称为的树称为m次树次树。2.分分支支结结点点与与叶叶结结点点：度度不不为为零零的的结结点点称称为为非非终终端端结结点点,又又叫叫分分支支结结点点。度度为为零零的的结结点点称称为为

6、终终端端结结点点或或叶叶结结点点。在在分分支支结结点点中中,每每个个结结点点的的分分支支数数就就是是该该结结点点的的度度。如如对对于于度度为为1的的结结点点,其其分分支支数数为为1,被被称称为为单单分分支支结结点点；对对于于度度为为2的的结结点点,其其分分支支数数为为2,被被称称为为双分支结点双分支结点,其余类推。其余类推。3.路路径径与与路路径径长长度度：对对于于任任意意两两个个结结点点ki和和kj,若若树树中中存存在在一一个个结结点点序序列列ki,ki1,ki2,kin,kj,使使得得序序列列中中除除ki外外的的任任一一结结点点都都是是其其在在序序列列中中的的前前一一个个结结点点的的后后继

7、继,则则称称该该结结点点序序列列为为由由ki到到kj的的一一条条路路径径,用用路路径径所所通通过过的的结结点点序序列列(ki,ki1,ki2,kj)表表示示这这条条路路径径。路路径径的的长长度度等等于于路路径径所所通通过过的的结结点点数数目目减减1(即即路路径径上上分分支支数数目目)。可可见见,路路径径就就是是从从ki出出发发“自自上上而而下下”到到达达kj所所通通过过的的树树中中结结点点序序列列。显显然然,从从树树的的根根结结点点到到树中其余结点均存在一条路径。树中其余结点均存在一条路径。4.孩孩子子结结点点、双双亲亲结结点点和和兄兄弟弟结结点点：在在一一棵棵树树中中,每每个个结结点点的的后

8、后继继,被被称称作作该该结结点点的的孩孩子子结结点点(或或子子女女结结点点)。相相应应地地,该该结结点点被被称称作作孩孩子子结结点点的的双双亲亲结结点点(或或父父母母结结点点)。具具有有同同一一双双亲亲的的孩孩子子结结点点互互为为兄兄弟弟结结点点。进进一一步步推推广广这这些些关关系系,可可以以把把每每个个结结点点的的所所有有子子树树中中的的结结点点称称为为该该结结点点的的子子孙孙结结点点,从从树树根根结结点点到到达达该该结结点的路径上经过的所有结点被称作该结点的点的路径上经过的所有结点被称作该结点的祖先结点祖先结点。5.结结点点的的层层次次和和树树的的高高度度：树树中中的的每每个个结结点点都都

9、处处在在一一定定的的层层次次上上。结结点点的的层层次次从从树树根根开开始始定定义义,根根结结点点为为第第1层层,它它的的孩孩子子结结点点为为第第2层层,以以此此类类推推,一一个个结结点点所所在在的的层层次次为为其其双双亲亲结结点点所所在在的的层层次次加加1。树树中中结点的最大层次称为结点的最大层次称为树的高度树的高度(或树的深度或树的深度)。6.有有序序树树和和无无序序树树：若若树树中中各各结结点点的的子子树树是是按按照照一一定定的的次次序序从从左左向向右右安安排排的的,且且相相对对次次序序是是不不能能随随意变换的意变换的,则称为则称为有序树有序树,否则称为否则称为无序树无序树。7.森森林林：

10、n(n0)个个互互不不相相交交的的树树的的集集合合称称为为森森林林。森森林林的的概概念念与与树树的的概概念念十十分分相相近近,因因为为只只要要把把树树的的根根结结点点删删去去就就成成了了森森林林。反反之之,只只要要给给n棵棵独独立立的的树树加加上上一一个个结结点点,并并把把这这n棵棵树树作作为为该结点的子树该结点的子树,则森林就变成了树。则森林就变成了树。7.1.4 7.1.4 树的性质树的性质性质性质1树中的结点数等于所有结点的度数加树中的结点数等于所有结点的度数加1。证证明明：根根据据树树的的定定义义,在在一一棵棵树树中中,除除树树根根结结点点外外,每每个个结结点点有有且且仅仅有有一一个个

11、前前驱驱结结点点。也也就就是是说说,每每个个结结点点与与指指向向它它的的一一个个分分支支一一一一对对应应,所所以以除除树树根根之之外外的的结结点点数数等等于于所所有有结结点点的的分分支支数数(度度数数),从从而而可可得得树树中中的结点数等于所有结点的度数加的结点数等于所有结点的度数加1。性性质质2度度为为m的的树树中中第第i层层上上至至多多有有mi-1个个结结点点,这这里应有里应有i1。证明证明(采用数学归纳法采用数学归纳法)对对于于第第一一层层,因因为为树树中中的的第第一一层层上上只只有有一一个个结结点点,即即整整个个树树的的根根结结点点,而而由由i=1代代入入mi-1,得得mi-1=m1-

12、1=1,也也同同样得到只有一个结点样得到只有一个结点,显然结论成立。显然结论成立。假假设设对对于于第第(i-1)层层(i1)命命题题成成立立,即即度度为为m的的树树中中第第(i-1)层层上上至至多多有有mi-2个个结结点点,则则根根据据树树的的度度的的定定义义,度度为为m的的树树中中每每个个结结点点至至多多有有m个个孩孩子子结结点点,所所以以第第i层层上上的的结结点点数数至至多多为为第第(i-1)层层上上结结点点数数的的m倍倍,即即至至多多为为mi-2m=mi-1个个,这与命题相同这与命题相同,故命题成立。故命题成立。性质性质3高度为高度为h的的m次树至多有次树至多有个结点。个结点。证证明明：

13、由由树树的的性性质质2可可知知,第第i层层上上最最多多结结点点数数为为mi-1(i=1,2,h),显显然然当当高高度度为为h的的m次次树树(即即度度为为m的的树树)上上每每一一层层都都达达到到最最多多结结点点数数时时,整整个个m次次树树具具有有最最多结点数多结点数,因此有：因此有：整整个个树树的的最最多多结结点点数数=每每一一层层最最多多结结点点数数之之和和=m0+m1+m2+mh-1=。性性质质4 具具有有n个个结结点点的的m次次树树的的最最小小高高度度为为 logm(n(m-1)+1)。证证明明：设设具具有有n个个结结点点的的m次次树树的的高高度度为为h,若若在在该该树树中中前前h-1层层

14、都都是是满满的的,即即每每一一层层的的结结点点数数都都等等于于mi-1个个(1ih-1),第第h层层(即即最最后后一一层层)的的结结点点数数可可能能满满,也也可可能能不不满满,则则该该树树具具有有最最小小的的高高度度。其其高高度度h可可计计算算如下：如下：根据树的性质根据树的性质3可得：可得：n乘乘(m-1)后得：后得：mh-1n(m-1)+1mh以以m为底取对数后得：为底取对数后得：h-1logm(n(m-1)+1)h即即logm(n(m-1)+1)hlogm(n(m-1)+1)+1因因h只能取整数只能取整数,所以所以h=logm(n(m-1)+1)结论得证。结论得证。例例7.1含含n个个结

15、结点点的的三三次次树树的的最最小小高高度度是是多多少少？最大高度是多少？最大高度是多少？解解：设设含含n个个结结点点的的(为为完完全全三三次次树树时时高高度度最最小小)的三次树的最小高度为的三次树的最小高度为h,则有：则有：1+3+9+3h-2n1+3+9+3h-1(3h-1-1)/2n(3h-1)/23h-12n+13h即：即：h=log3(2n+1)最大高度为最大高度为n-2。7.1.5 7.1.5 树的基本运算树的基本运算 树的运算主要分为三大类：树的运算主要分为三大类：第第一一类类,寻寻找找满满足足某某种种特特定定关关系系的的结结点点,如如寻寻找找当前结点的双亲结点等；当前结点的双亲结

16、点等；第第二二类类,插插入入或或删删除除某某个个结结点点,如如在在树树的的当当前前结结点点上上插插入入一一个个新新结结点点或或删删除除当当前前结结点点的的第第i i个个孩孩子子结点等；结点等；第三类第三类,遍历树中每个结点遍历树中每个结点,这里着重介绍。这里着重介绍。树树的的遍遍历历运运算算是是指指按按某某种种方方式式访访问问树树中中的的每每一一个个结结点点且且每每一一个个结结点点只只被被访访问问一一次次。树树的的遍遍历历运运算算的的算算法法主主要要有有先先根根遍遍历历和和后后根根遍遍历历两两种种。注注意意,下下面面的的先先根遍历和后根遍历算法都是递归的。根遍历和后根遍历算法都是递归的。1.先

17、根遍历先根遍历先根遍历过程为：先根遍历过程为：(1)访问根结点；访问根结点；(2)按照从左到右的次序先根遍历根结点的每一按照从左到右的次序先根遍历根结点的每一棵子树。棵子树。2.后根遍历后根遍历后根遍历过程为：后根遍历过程为：(1)按按照照从从左左到到右右的的次次序序后后根根遍遍历历根根结结点点的的每每一一棵子树；棵子树；(2)访问根结点。访问根结点。7.1.6 7.1.6 树的存储结构树的存储结构1.1.双亲存储结构双亲存储结构 这这种种存存储储结结构构是是一一种种顺顺序序存存储储结结构构,用用一一组组连连续续空空间间存存储储树树的的所所有有结结点点,同同时时在在每每个个结结点点中中附附设设

18、一一个伪指针指示其双亲结点的位置。个伪指针指示其双亲结点的位置。树的双亲存储结构示意图树的双亲存储结构示意图2.孩子链存储结构孩子链存储结构孩孩子子链链存存储储结结构构可可按按树树的的度度(即即树树中中所所有有结结点点度度的的最最大大值值)设设计计结结点点的的孩孩子子结结点点指指针针域域个个数数。下下图图(a)的的树对应的孩子链存储结构如图树对应的孩子链存储结构如图(b)所示。所示。树的树的孩子链孩子链存储结构示意图存储结构示意图3.孩子兄弟链存储结构孩子兄弟链存储结构孩孩子子兄兄弟弟链链存存储储结结构构是是为为每每个个结结点点设设计计三三个个域域：一一个个数数据据元元素素域域,一一个个该该结

19、结点点的的第第一一个个孩孩子子结结点点指指针针域域,一一个个该该结结点点的的下下一一个个兄兄弟弟结结点点指指针针域域。下下图图(a)的树对应的孩子兄弟链存储结构如图的树对应的孩子兄弟链存储结构如图(b)所示。所示。树的树的孩子兄弟链孩子兄弟链存储结构示意图存储结构示意图7.2 7.2 二叉树概念和性质二叉树概念和性质 7.2.1 7.2.1 二叉树概念二叉树概念7.2.2 7.2.2 二叉树性质二叉树性质7.2.3 7.2.3 二叉树与树、森林之间的转换二叉树与树、森林之间的转换7.2.1 7.2.1 二叉树概念二叉树概念二二叉叉树树也也称称为为二二次次树树或或二二分分树树,它它是是有有限限的

20、的结结点点集集合合,这这个个集集合合或或者者是是空空,或或者者由由一一个个根根结结点点和和两两棵棵互不相交的称为左子树和右子树的二叉树组成。互不相交的称为左子树和右子树的二叉树组成。二叉树的定义是一种递归定义。二叉树的定义是一种递归定义。二二叉叉树树有有五五种种基基本本形形态态,如如下下图图所所示示,任任何何复复杂杂的二叉树都是这五种基本形态的复合。的二叉树都是这五种基本形态的复合。从从定定义义看看到到,二二叉叉树树是是一一种种特特殊殊的的树树,其其表表示示法法也也与与树树的的表表示示法法一一样样,有有树树形形表表示示法法、文文氏氏图图表示法、凹入表示法和括号表示法等。表示法、凹入表示法和括号

21、表示法等。在在一一棵棵二二叉叉树树中中,如如果果所所有有分分支支结结点点都都有有左左孩孩子子结结点点和和右右孩孩子子结结点点,并并且且叶叶结结点点都都集集中中在在二二叉叉树树的的最最下下一一层层,这这样样的的二二叉叉树树称称为为满满二二叉叉树树。下下图图所所示示就就是是一一棵棵满满二二叉叉树树。可可以以对对满满二二叉叉树树的的结结点点进进行行连连续续编编号号,约约定定编编号号从从树树根根为为1 1开开始始,按按照照层层数数从从小小到到大大、同同一一层层从从左左到到右右的的次次序序进进行行。图图中中每每个个结结点点外外边边的的数数字字为为对对该结点的编号。该结点的编号。若若二二叉叉树树中中最最多

22、多只只有有最最下下面面两两层层的的结结点点的的度度数数可可以以小小于于2 2,并并且且最最下下面面一一层层的的叶叶结结点点 都都依依次次排排列列在在该该层层最最左左边边的的位位置置上上,则则这这样样的的二二叉叉树树称称为为完完全全二二叉叉树树。如如下下图图所所示示为为一一棵棵完完全全二二叉叉树树。同同样样可可以以对对完完全全二二叉叉树树中中每每个个结结点点进进行行连连续续编编号号,编编号号的的方方法法同同满满二二叉叉树树相同。图中每个结点外边的数字为对该结点的编号。相同。图中每个结点外边的数字为对该结点的编号。7.2.2 7.2.2 二叉树性质二叉树性质性性质质1非非空空二二叉叉树树上上叶叶结

23、结点点数数等等于于双双分分支支结结点点数数加加1。证证明明：设设二二叉叉树树上上叶叶结结点点数数为为n0,单单分分支支结结点点数数为为n1,双双分分支支结结点点数数为为n2,则则总总结结点点数数=n0+n1+n2。在在一一棵棵二二叉叉树树中中,所所有有结结点点的的分分支支数数(即即度度数数)应应等等于于单单分分支支结点数加上双分支结点数的结点数加上双分支结点数的2倍倍,即总的分支数即总的分支数=n1+2n2。由由于于二二叉叉树树中中除除根根结结点点以以外外,每每个个结结点点都都有有惟惟一一的的一一个个分分支支指指向向它它,因因此此二二叉叉树树中中有有：总总的的分分支支数数=总总结结点数点数-1

24、。由上述三个等式可得：由上述三个等式可得：n1+2n2=n0+n1+n2-1即：即：n0=n2+1性性质质2非非空空二二叉叉树树上上第第i层层上上至至多多有有2i-1个个结结点点,这这里应有里应有i1。由树的性质由树的性质2可推出。可推出。性质性质3高度为高度为h的二叉树至多有的二叉树至多有2h-1个结点个结点(h1)。由树的性质由树的性质3可推出。可推出。性性 质质 4 对对 完完 全全 二二 叉叉 树树 中中 编编 号号 为为 i的的 结结 点点(1in,n1,n为结点数为结点数)有：有：(1)若若i n/2,即即2in,则则编编号号为为i的的结结点点为为分分支支结点结点,否则为叶子结点。

25、否则为叶子结点。(2)若若n为为奇奇数数,则则每每个个分分支支结结点点都都既既有有左左孩孩子子结结点点,也也有有右右孩孩子子结结点点；若若n为为偶偶数数,则则编编号号最最大大的的分分支支结结点点(编编号号为为)只只有有左左孩孩子子结结点点,没没有有右右孩孩子子结结点点,其余分支结点都有左、右孩子结点。其余分支结点都有左、右孩子结点。(3)若若编编号号为为i的的结结点点有有左左孩孩子子结结点点,则则左左孩孩子子结结点点的的编编号号为为2i；若若编编号号为为i的的结结点点有有右右孩孩子子结结点点,则则右右孩子结点的编号为孩子结点的编号为(2i+1)。(4)除除树树根根结结点点外外,若若一一个个结结

26、点点的的编编号号为为i,则则它它的的双双亲亲结结点点的的编编号号为为 i/2,也也就就是是说说,当当i为为偶偶数数时时,其其双双亲亲结结点点的的编编号号为为i/2,它它是是双双亲亲结结点点的的左左孩孩子子结结点点,当当i为为奇奇数数时时,其其双双亲亲结结点点的的编编号号为为(i-1)/2,它它是是双双亲亲结结点的右孩子结点。点的右孩子结点。性性质质5具具有有n个个(n0)结结点点的的完完全全二二叉叉树树的的高高度度为为 log2n+1 或或 log2n+1。由完全二叉树的定义和树的性质由完全二叉树的定义和树的性质3可推出。可推出。7.2.3 7.2.3 二叉树与树、森林之间的转换二叉树与树、森

27、林之间的转换1森林、树转换为二叉树森林、树转换为二叉树步骤如下：步骤如下：(1)在在所所有有相相邻邻兄兄弟弟结结点点(森森林林中中每每棵棵树树的的根根结结点点可看成是兄弟结点可看成是兄弟结点)之间加一水平连线。之间加一水平连线。(2)对对每每个个非非叶叶结结点点k,除除了了其其最最左左边边的的孩孩子子结结点点外外,删去删去k与其他孩子结点的连线。与其他孩子结点的连线。(3)所所有有水水平平线线段段以以左左边边结结点点为为轴轴心心顺顺时时针针旋旋转转45度。度。通通过过以以上上步步骤骤,原原来来的的森森林林就就转转换换为为一一棵棵二二叉叉树树。一一般般的的树树是是森森林林中中的的特特殊殊情情况况

28、,由由一一般般的的树树转转换换的的二二叉叉树树的的根根结结点点的的右右孩孩子子结结点点始始终终为为空空,原原因因是是一一般般的的树的根结点不存在兄弟结点和相邻的树。树的根结点不存在兄弟结点和相邻的树。将森林转换为二叉树的过程将森林转换为二叉树的过程2.2.二叉树还原为森林、树二叉树还原为森林、树 步骤如下：步骤如下：(1)对对于于一一棵棵二二叉叉树树中中任任一一结结点点k0,沿沿着着k0的的左左孩孩子子结结点点k1的的右右子子树树方方向向搜搜索索所所有有右右孩孩子子结结点点,即即搜搜索索结结点点序序列列k2,k3,km,其其中中ki+1为为ki的的右右孩孩子子结点结点(1im),km没有右孩子

29、结点。没有右孩子结点。(2)删去删去k1,k2,km之间连线。之间连线。(3)若若k1有双亲结点有双亲结点k,则连接则连接k与与ki(2im)。(4)将图形规整化将图形规整化,使各结点按层次排列使各结点按层次排列。将一棵二叉树还原为树的过程将一棵二叉树还原为树的过程7.3 7.3 二叉树存储结构二叉树存储结构 7.3.1 7.3.1 二叉树的顺序存储结构二叉树的顺序存储结构7.3.2 7.3.2 二叉树的链式存储结构二叉树的链式存储结构7.3.1 7.3.1 二叉树的顺序存储结构二叉树的顺序存储结构 二叉树的顺序存储结构中结点的存放次序是：二叉树的顺序存储结构中结点的存放次序是：对该树中每个结

30、点进行编号对该树中每个结点进行编号,其编号从小到大的顺其编号从小到大的顺序就是结点存放在连续存储单元的先后次序。若序就是结点存放在连续存储单元的先后次序。若把二叉树存储到一维数组中把二叉树存储到一维数组中,则该编号就是下标值则该编号就是下标值加加1(注意注意,C/C+语言中数组的起始下标为语言中数组的起始下标为0)。树。树中各结点的编号与等高度的完全二叉树中对应位中各结点的编号与等高度的完全二叉树中对应位置上结点的编号相同。置上结点的编号相同。利用二叉树的性质利用二叉树的性质4。A B C D E F G H I J K123456789101112131415顺序存储结构顺序存储结构7.3.

31、2 7.3.2 二叉树的链式存储结构二叉树的链式存储结构在二叉树的链接存储中在二叉树的链接存储中,结点的结构如下结点的结构如下:typedefstructnode ElemTypedata;structnode*lchild,*rchild;BTNode;其其中中,data表表示示值值域域,用用于于存存储储对对应应的的数数据据元元素素,lchild和和rchild分分别别表表示示左左指指针针域域和和右右指指针针域域,用用于于分分别别存存储储左左孩孩子子结结点点和和右右孩孩子子结结点点(即即左左、右右子子树树的的根结点根结点)的存储位置。的存储位置。二叉树及其链式存储结构二叉树及其链式存储结构

32、7.4 7.4 二叉树的遍历二叉树的遍历7.4.1 7.4.1 二叉树遍历的概念二叉树遍历的概念7.4.2 7.4.2 二叉树遍历递归算法二叉树遍历递归算法7.4.3 7.4.3 二叉树遍历非递归算法二叉树遍历非递归算法 7.4.1 7.4.1 二叉树遍历的概念二叉树遍历的概念二二叉叉树树的的遍遍历历是是指指按按照照一一定定次次序序访访问问树树中中所所有有结结点点,并并且且每每个个结结点点仅仅被被访访问问一一次次的的过过程程。它它是是最最基基本的运算本的运算,是二叉树中所有其他运算的基础。是二叉树中所有其他运算的基础。1.先序遍历先序遍历先序遍历二叉树的过程是：先序遍历二叉树的过程是：(1)访

33、问根结点；访问根结点；(2)先序遍历左子树；先序遍历左子树；(3)先序遍历右子树。先序遍历右子树。2.中序遍历中序遍历中序遍历二叉树的过程是：中序遍历二叉树的过程是：(1)中序遍历左子树；中序遍历左子树；(2)访问根结点；访问根结点；(3)中序遍历右子树。中序遍历右子树。3.后序遍历后序遍历后序遍历二叉树的过程是：后序遍历二叉树的过程是：(1)后序遍历左子树；后序遍历左子树；(2)后序遍历右子树；后序遍历右子树；(3)访问根结点。访问根结点。7.4.2 7.4.2 二叉树遍历递归算法二叉树遍历递归算法由由二二叉叉树树的的三三种种遍遍历历过过程程直直接接得得到到如如下下三三种种递递归归算算法如下

34、：法如下：voidPreOrder(BTNode*b)/*先序遍历的递归算法先序遍历的递归算法*/if(b!=NULL)printf(%c,b-data);/*访问根结点访问根结点*/PreOrder(b-lchild);PreOrder(b-rchild);voidInOrder(BTNode*b)/*中序遍历的递归算法中序遍历的递归算法*/if(b!=NULL)InOrder(b-lchild);printf(%c,b-data);/*访问根结点访问根结点*/InOrder(b-rchild);voidPostOrder(BTNode*b)/*后序遍历递归算法后序遍历递归算法*/if(b!

35、=NULL)PostOrder(b-lchild);PostOrder(b-rchild);printf(%c,b-data);/*访问根结点访问根结点*/层次遍历层次遍历其过程是：其过程是：若二叉树非空（假设其高度为若二叉树非空（假设其高度为h），则：），则：（1）访问根结点（第）访问根结点（第1层）；层）；（2）从左到右访问第）从左到右访问第2层的所有结点；层的所有结点；（3）从左到右访问第）从左到右访问第3层的所有结点、层的所有结点、第、第h层的所有结点。层的所有结点。层次遍历序列：层次遍历序列：A、B、C、D、E、F、GvoidLevelOrder(BTNode*b)BTNode*p;

36、BTNode*quMaxSize;/*定义环形队列定义环形队列,存放结点指针存放结点指针*/intfront,rear;/*定义队头和队尾指针定义队头和队尾指针*/front=rear=-1;/*置队列为空队列置队列为空队列*/rear+;qurear=b;/*根结点指针进入队列根结点指针进入队列*/while(front!=rear)/*队列不为空队列不为空*/front=(front+1)%MaxSize;p=qufront;/*队头出队列队头出队列*/printf(%c,p-data);/*访问结点访问结点*/if(p-lchild!=NULL)/*有左孩子时将其进队有左孩子时将其进队*

37、/rear=(rear+1)%MaxSize;qurear=p-lchild;if(p-rchild!=NULL)/*有右孩子时将其进队有右孩子时将其进队*/rear=(rear+1)%MaxSize;qurear=p-rchild;例例7.2假假设设二二叉叉树树采采用用二二叉叉链链存存储储结结构构存存储储,试试设设计一个算法计一个算法,输出一棵给定二叉树的所有叶子结点。输出一棵给定二叉树的所有叶子结点。解解：输输出出一一棵棵二二叉叉树树的的所所有有叶叶子子结结点点的的递递归归模模型型f()如下：如下：f(b)：不做任何事件不做任何事件若若b=NULLf(b)：输出输出*b结点的结点的data

38、域域若若*b为叶子结点为叶子结点f(b)：f(b-lchild);f(b-rchild)其他情况其他情况voidDispLeaf(BTNode*b)if(b!=NULL)if(b-lchild=NULL&b-rchild=NULL)printf(%c,b-data);elseDispLeaf(b-lchild);DispLeaf(b-rchild);7.4.3 7.4.3 二叉树遍历非递归算法二叉树遍历非递归算法 1.1.先序遍历先序遍历非递归算法非递归算法（1）第一种方法）第一种方法由先序遍历的定义可知，其递归模型由先序遍历的定义可知，其递归模型f()如下：如下：f(p)：不做任何事件不做任

39、何事件若若p=NULLf(p)：输出输出*p结点的结点的data域值域值;其他情况其他情况f(p-lchild);f(p-rchild);递归等价关系递归等价关系（非相等关系）（非相等关系）voidPreOrder1(BTNode*b)BTNode*p;structBTNode*pt;inttag;/1:未访问，未访问，0:可访问可访问StMaxSize;inttop=-1;top+;Sttop.pt=b;Sttop.tag=1;while(top-1)/栈不空时循环栈不空时循环if(Sttop.tag=1)/不能直接访问的情况不能直接访问的情况p=Sttop.pt;top-;if(p!=NU

40、LL)/(2)式式top+;/右孩子结点进栈右孩子结点进栈Sttop.pt=p-rchild;Sttop.tag=1;top+;/左孩子结点进栈左孩子结点进栈Sttop.pt=p-lchild;Sttop.tag=1;top+;/根结点进栈根结点进栈Sttop.pt=p;Sttop.tag=0;/endofif(Sttop.tag=1)if(Sttop.tag=0)/直接访问的情况直接访问的情况printf(%c,Sttop.pt-data);top-;/while（2）第二种方法（常规方法）第二种方法（常规方法）voidPreOrder2(BTNode*b)BTNode*StMaxSize,

41、*p;inttop=-1;top+;Sttop=b;/根结点入栈根结点入栈while(top-1)/栈不为空时循环栈不为空时循环p=Sttop;top-;/退栈并访问该结点退栈并访问该结点printf(%c,p-data);if(p-rchild!=NULL)/右孩子结点入栈右孩子结点入栈top+;Sttop=p-rchild;if(p-lchild!=NULL)/左孩子结点入栈左孩子结点入栈top+;Sttop=p-lchild;2.中序遍历非递归算法中序遍历非递归算法（2）第二种方法（常规方法）第二种方法（常规方法）由由中中序序遍遍历历过过程程可可知知，采采用用一一个个栈栈保保存存需需要要

42、返返回回的的结结点点指指针针，先先扫扫描描（并并非非访访问问）根根结结点点的的所所有有左左结结点点并并将将它它们一一进栈。们一一进栈。然然后后出出栈栈一一个个结结点点，显显然然该该结结点点没没有有左左孩孩子子结结点点或或者者左左孩孩子子结结点点已已访访问问过过（进进一一步步说说明明该该结结点点的的左左子子树树均均已已访访问问），则则访访问问它它。然然后后扫扫描描该该结结点点的的右右孩孩子子结结点点，将将其其进进栈栈，再再扫扫描描该该右右孩孩子子结结点点的的所所有有左左结结点点并并一一一一进进栈栈，如如此此这样，直到栈空为止。这样，直到栈空为止。voidInOrder2(BTNode*b)BTN

43、ode*StMaxSize,*p;inttop=-1;p=b;while(top-1|p!=NULL)while(p!=NULL)/扫描扫描*p的所有左结点并进栈的所有左结点并进栈top+;Sttop=p;p=p-lchild;if(top-1)p=Sttop;top-;/出栈出栈*p结点结点printf(%c,p-data);/访问之访问之p=p-rchild;/扫描扫描*p的右孩子结点的右孩子结点/endofwhile(top-1|p!=NULL)找找*b的最左下的最左下结点结点3.后序遍历非递归算法后序遍历非递归算法（2）第二种方法（常规方法）第二种方法（常规方法）由由后后遍遍历历过过程

44、程可可知知，采采用用一一个个栈栈保保存存需需要要返返回回的的结结点点指指针针，先先扫扫描描根根结结点点的的所所有有左左结结点点并并一一一一进进栈栈，出出栈栈一一个个结结点点*b即即当当前前结结点点，然然后后扫扫描描该该结结点点的的右右孩孩子子结结点点并并入入栈栈，再再扫扫描描该该右右孩孩子子结结点点的的所所有有左左结结点点并并入入栈栈。当当一一个个结结点点的的左左右右孩孩子子结结点点均均访访问后再访问该结点，如此这样，直到栈空为止。问后再访问该结点，如此这样，直到栈空为止。难点：难点：如何判断一个结点如何判断一个结点*b的右孩子结点已访问过的右孩子结点已访问过，为此，为此用用p保存刚刚访问过的

45、结点（初值为保存刚刚访问过的结点（初值为NULL），若），若b-rchild=p成立（成立（在后序遍历中，在后序遍历中，*b的右孩子结点一定刚好在的右孩子结点一定刚好在*b之前访问之前访问），说明，说明*b的左右子树均已访问，现在应访问的左右子树均已访问，现在应访问*b。voidPostOrder2(BTNode*b)BTNode*StMaxSize;BTNode*p;intflag,top=-1;/栈指针置初值栈指针置初值dowhile(b!=NULL)/将将*b的所有左结点进栈的所有左结点进栈top+;Sttop=b;b=b-lchild;p=NULL;/p指指向向栈栈顶顶结结点点的的前前

46、一一个个已已访访问问的结点的结点flag=1;/设置设置b的访问标记为已访问过的访问标记为已访问过找找最左下结点最左下结点while(top!=-1&flag=1)b=Sttop;/取出当前的栈顶元素取出当前的栈顶元素if(b-rchild=p)printf(%c,b-data);/访问访问*b结点结点top-;p=b;/p指向则被访问的结点指向则被访问的结点elseb=b-rchild;/b指向右孩子结点指向右孩子结点flag=0;/设置未被访问的标记设置未被访问的标记/endofwhile(top!=-1&flag=1)while(top!=-1);b b的右孩子不存在或已访问过的右孩子不

47、存在或已访问过从上述过程可知，栈中保存的是当前从上述过程可知，栈中保存的是当前结点结点*b的所有祖先结点（均未访问过）。的所有祖先结点（均未访问过）。例如，求一个结点的所有祖先结点。例如，求一个结点的所有祖先结点。7.5 7.5 二叉树的基本运算及其实现二叉树的基本运算及其实现7.5.1 7.5.1 二叉树的基本运算概述二叉树的基本运算概述7.5.2 7.5.2 二叉树的基本运算算法实现二叉树的基本运算算法实现7.5.1 7.5.1 二叉树的基本运算概述二叉树的基本运算概述归纳起来归纳起来,二叉树有以下基本运算：二叉树有以下基本运算：(1)创创建建二二叉叉树树CreateBTNode(*b,*

48、str)：根根据据二二叉叉树树括括号号表表示示法法的的字字符符串串*str生生成成对对应应的的链链式式存存储储结结构。构。(2)查查找找结结点点FindNode(*b,x)：在在二二叉叉树树b中中寻寻找找data域值为域值为x的结点的结点,并返回指向该结点的指针。并返回指向该结点的指针。(3)找找孩孩子子结结点点LchildNode(p)和和RchildNode(p)：分别求二叉树中结点分别求二叉树中结点*p的左孩子结点和右孩子结点。的左孩子结点和右孩子结点。(4)求求高高度度BTNodeDepth(*b)：求求二二叉叉树树b的的高高度度。若若二二叉叉树树为为空空,则则其其高高度度为为0；否否

49、则则,其其高高度度等等于于左左子子树与右子树中的最大高度加树与右子树中的最大高度加l。(5)输输出出二二叉叉树树DispBTNode(*b)：以以括括号号表表示示法法输出一棵二叉树。输出一棵二叉树。7.5.2 7.5.2 二叉树的基本运算算法实现二叉树的基本运算算法实现(1)创建二叉树创建二叉树CreateBTNode(*b,*str)用用ch扫扫描描采采用用括括号号表表示示法法表表示示二二叉叉树树的的字字符符串串。分分以下几种情况：以下几种情况：若若ch=(：则则将将前前面面刚刚创创建建的的结结点点作作为为双双亲亲结结点点进进栈栈,并并置置k=1,表表示示其其后后创创建建的的结结点点将将作作

50、为为这这个个结结点点的的左孩子结点；左孩子结点；若若ch=)：表表示示栈栈中中结结点点的的左左右右孩孩子子结结点点处处理理完完毕毕,退栈；退栈；若若ch=,：表示其后创建的结点为右孩子结点；表示其后创建的结点为右孩子结点；其其他他情情况况,表表示示要要创创建建一一个个结结点点,并并根根据据k值值建建立立它它与与栈栈中中结结点点之之间间的的联联系系,当当k=1时时,表表示示这这个个结结点点作作为为栈栈中中结结点点的的左左孩孩子子结结点点,当当k=2时时,表表示示这这个个结结点点作作为为栈栈中中结结点点的的右右孩孩子子结结点点。如如此此循循环环直直到到str处处理理完完毕毕。算算法法中中使使用用一