数据结构C语言树形结构.pptx

《数据结构C语言树形结构.pptx》由会员分享，可在线阅读，更多相关《数据结构C语言树形结构.pptx（115页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、7.1.1 7.1.1 树的定义树的定义 形式化定义：形式化定义：树树：TK,R。K是是包包含含n个个结结点点的的有有穷穷集集合合(n0),关系关系R满足以下条件满足以下条件:(1)有有且且仅仅有有一一个个结结点点k0 K,它它对对于于关关系系R来来说说没有前驱结点没有前驱结点,结点结点k0称作树的根。称作树的根。(2)除除结结点点k0外外,K中中的的每每个个结结点点对对于于关关系系R来来说说都有且仅有一个前驱结点。都有且仅有一个前驱结点。(3)K中中每每个个结结点点对对于于关关系系R来来说说可可以以有有多多个个后后继结点。继结点。第1页/共115页递归定义：递归定义：树树是是由由n(n0)个

2、个结结点点组组成成的的有有限限集集合合(记记为为T)。其其中中,如果如果n=0,它是一棵空树它是一棵空树,这是树的特例；这是树的特例；如如果果n0,这这n个个结结点点中中存存在在(有有仅仅存存在在)一一个个结结点点作作为为树树的的根根结结点点,简简称称为为根根(root),其其余余结结点点可可分分为为m(m0)个个互互不不相相交交的的有有限限集集T1,T2,Tm,其其中中每每一一棵棵子子集集本本身身又又是是一一棵棵符符合合本本定定义义的的树树,称称为为根根root的的子子树。树。第2页/共115页7.1.2 7.1.2 树的表示树的表示 (1)树树形形表表示示法法。这这是是树树的的最最基基本本

3、的的表表示示,使使用用一一棵棵倒倒置置的的树树表表示示树树结结构构,非非常常直直观观和和形形象象。下下图图就就是是采用这种表示法。采用这种表示法。第3页/共115页 (2)文文氏氏图图表表示示法法。使使用用集集合合以以及及集集合合的的包包含含关关系系描描述述树树结结构构。下下图图就就是是树树的的文文氏氏图图表示法。表示法。第4页/共115页 (3)凹凹入入表表示示法法。使使用用线线段段的的伸伸缩缩描描述述树树结结构。下图是树的凹入表示法。构。下图是树的凹入表示法。第5页/共115页 (4)括括号号表表示示法法。将将树树的的根根结结点点写写在在括括号号的的左左边边,除除根根结结点点之之外外的的其

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

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

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

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

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

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

10、在在一一棵棵树树中中,除除树树根根结结点点外外,每每个个结结点点有有且且仅仅有有一一个个前前驱驱结结点点。也也就就是是说说,每每个个结结点点与与指指向向它它的的一一个个分分支支一一一一对对应应,所所以以除除树树根根之之外外的的结结点点数数等等于于所所有有结结点点的的分分支支数数(度度数数),从从而而可可得得树树中中的结点数等于所有结点的度数加的结点数等于所有结点的度数加1。第12页/共115页 性性质质2 度度为为m的的树树中中第第i层层上上至至多多有有mi-1个个结结点点,这这里应有里应有i1。证明证明(采用数学归纳法采用数学归纳法)对对于于第第一一层层,因因为为树树中中的的第第一一层层上上

11、只只有有一一个个结结点点,即即整整个个树树的的根根结结点点,而而由由i=1代代入入mi-1,得得mi-1=m1-1=1,也也同同样得到只有一个结点样得到只有一个结点,显然结论成立。显然结论成立。假假设设对对于于第第(i-1)层层(i1)命命题题成成立立,即即度度为为m的的树树中中第第(i-1)层层上上至至多多有有mi-2个个结结点点,则则根根据据树树的的度度的的定定义义,度度为为m的的树树中中每每个个结结点点至至多多有有m个个孩孩子子结结点点,所所以以第第i层层上上的的结结点点数数至至多多为为第第(i-1)层层上上结结点点数数的的m倍倍,即即至至多多为为mi-2m=mi-1个个,这与命题相同这

12、与命题相同,故命题成立。故命题成立。第13页/共115页 性质性质3 高度为高度为h的的m次树至多有次树至多有 个结点。个结点。证证明明：由由树树的的性性质质2可可知知,第第i层层上上最最多多结结点点数数为为mi-1(i=1,2,h),显显然然当当高高度度为为h的的m次次树树(即即度度为为m的的树树)上上每每一一层层都都达达到到最最多多结结点点数数时时,整整个个m次次树树具具有有最最多多结结点数点数,因此有：因此有：整整个个树树的的最最多多结结点点数数=每每一一层层最最多多结结点点数数之之和和=m0+m1+m2+mh-1=。第14页/共115页 性性质质4 具具有有n个个结结点点的的m次次树树

13、的的最最小小高高度度为为 logm(n(m-1)+1)。证证明明：设设具具有有n个个结结点点的的m次次树树的的高高度度为为h,若若在在该该树树中中前前h-1层层都都是是满满的的,即即每每一一层层的的结结点点数数都都等等于于mi-1个个(1ih-1),第第h层层(即即最最后后一一层层)的的结结点点数数可可能能满满,也也可可能不满能不满,则该树具有最小的高度。其高度则该树具有最小的高度。其高度h可计算如下：可计算如下：第15页/共115页根据树的性质根据树的性质3可得：可得：n乘乘(m-1)后得：后得：mh-1n(m-1)+1mh以以m为底取对数后得：为底取对数后得：h-1logm(n(m-1)+

14、1)h即即logm(n(m-1)+1)hlogm(n(m-1)+1)+1因因h只能取整数只能取整数,所以所以 h=logm(n(m-1)+1)结论得证。结论得证。第16页/共115页 例例7.1 含含n个个结结点点的的三三次次树树的的最最小小高高度度是是多多少少？解解：设设含含n个个结结点点的的(为为完完全全三三次次树树时时高高度度最最小小)的三次树的最小高度为的三次树的最小高度为h,则有：则有：1+3+9+3h-2n1+3+9+3h-1 (3h-1-1)/2 n(3h-1)/2 3h-12n+13h 即：即：h=log3(2n+1)第17页/共115页7.1.5 7.1.5 树的基本运算树的

15、基本运算 树的运算主要分为三大类：树的运算主要分为三大类：第第一一类类,寻寻找找满满足足某某种种特特定定关关系系的的结结点点,如如寻寻找找当前结点的双亲结点等；当前结点的双亲结点等；第第二二类类,插插入入或或删删除除某某个个结结点点,如如在在树树的的当当前前结结点点上上插插入入一一个个新新结结点点或或删删除除当当前前结结点点的的第第i i个个孩孩子子结点等；结点等；第三类第三类,遍历树中每个结点遍历树中每个结点,这里着重介绍。这里着重介绍。第18页/共115页 树树的的遍遍历历运运算算是是指指按按某某种种方方式式访访问问树树中中的的每每一一个个结结点点且且每每一一个个结结点点只只被被访访问问一

16、一次次。树树的的遍遍历历运运算算的的算算法法主主要要有有先先根根遍遍历历和和后后根根遍遍历历两两种种。注注意意,下下面面的的先先根遍历和后根遍历算法都是递归的。根遍历和后根遍历算法都是递归的。1.先根遍历先根遍历 先根遍历过程为：先根遍历过程为：(1)访问根结点；访问根结点；(2)按照从左到右的次序先根遍历根结点的每一棵按照从左到右的次序先根遍历根结点的每一棵子树。子树。第19页/共115页2.后根遍历后根遍历 后根遍历过程为：后根遍历过程为：(1)按按照照从从左左到到右右的的次次序序后后根根遍遍历历根根结结点点的的每每一一棵棵子树；子树；(2)访问根结点。访问根结点。第20页/共115页7.

17、1.6 7.1.6 树的存储结构树的存储结构1.1.双亲存储结构双亲存储结构 这这种种存存储储结结构构是是一一种种顺顺序序存存储储结结构构,用用一一组组连连续续空空间间存存储储树树的的所所有有结结点点,同同时时在在每每个个结结点点中中附附设设一一个伪指针指示其双亲结点的位置。个伪指针指示其双亲结点的位置。树的双亲存储结构示意图树的双亲存储结构示意图第21页/共115页2.孩子链存储结构孩子链存储结构 孩孩子子链链存存储储结结构构可可按按树树的的度度(即即树树中中所所有有结结点点度度的的最最大大值值)设设计计结结点点的的孩孩子子结结点点指指针针域域个个数数。下下图图(a)的的树树对应的孩子链存储

18、结构如图对应的孩子链存储结构如图(b)所示。所示。树的树的孩子链孩子链存储结构示意图存储结构示意图第22页/共115页3.孩子兄弟链存储结构孩子兄弟链存储结构 孩孩子子兄兄弟弟链链存存储储结结构构是是为为每每个个结结点点设设计计三三个个域域：一一个个数数据据元元素素域域,一一个个该该结结点点的的第第一一个个孩孩子子结结点点指指针针域域,一一个个该该结结点点的的下下一一个个兄兄弟弟结结点点指指针针域域。下下图图(a)的树对应的孩子兄弟链存储结构如图的树对应的孩子兄弟链存储结构如图(b)所示。所示。树的树的孩子兄弟链孩子兄弟链存储结构示意图存储结构示意图第23页/共115页7.2 7.2 二叉树概

19、念和性质二叉树概念和性质 7.2.1 7.2.1 二叉树概念二叉树概念7.2.2 7.2.2 二叉树性质二叉树性质7.2.3 7.2.3 二叉树与树、森林之间的转换二叉树与树、森林之间的转换第24页/共115页7.2.1 7.2.1 二叉树概念二叉树概念 二二叉叉树树也也称称为为二二次次树树或或二二分分树树,它它是是有有限限的的结结点点集集合合,这这个个集集合合或或者者是是空空,或或者者由由一一个个根根结结点点和和两两棵棵互互不相交的称为左子树和右子树的二叉树组成。不相交的称为左子树和右子树的二叉树组成。二叉树的定义是一种递归定义。二叉树的定义是一种递归定义。第25页/共115页 二二叉叉树树

20、有有五五种种基基本本形形态态,如如下下图图所所示示,任任何何复复杂杂的二叉树都是这五种基本形态的复合。的二叉树都是这五种基本形态的复合。第26页/共115页 从从定定义义看看到到,二二叉叉树树是是一一种种特特殊殊的的树树,其其表表示示法法也也与与树树的的表表示示法法一一样样,有有树树形形表表示示法法、文文氏氏图图表示法、凹入表示法和括号表示法等。表示法、凹入表示法和括号表示法等。第27页/共115页 在在一一棵棵二二叉叉树树中中,如如果果所所有有分分支支结结点点都都有有左左孩孩子子结结点点和和右右孩孩子子结结点点,并并且且叶叶结结点点都都集集中中在在二二叉叉树树的的最最下下一一层层,这这样样的

21、的二二叉叉树树称称为为满满二二叉叉树树。下下图图所所示示就就是是一一棵棵满满二二叉叉树树。可可以以对对满满二二叉叉树树的的结结点点进进行行连连续续编编号号,约约定定编编号号从从树树根根为为1 1开开始始,按按照照层层数数从从小小到到大大、同同一一层层从从左左到到右右的的次次序序进进行行。图图中中每每个个结结点点外外边边的的数数字字为为对该结点的编号。对该结点的编号。第28页/共115页 若若二二叉叉树树中中最最多多只只有有最最下下面面两两层层的的结结点点的的度度数数可可以以小小于于2,2,并并且且最最下下面面一一层层的的叶叶结结点点 都都依依次次排排列列在在该该层层最最左左边边的的位位置置上上

22、,则则这这样样的的二二叉叉树树称称为为完完全全二二叉叉树树。如如下下图图所所示示为为一一棵棵完完全全二二叉叉树树。同同样样可可以以对对完完全全二二叉叉树树中中每每个个结结点点进进行行连连续续编编号号,编编号号的的方方法法同同满满二二叉叉树树相同。图中每个结点外边的数字为对该结点的编号。相同。图中每个结点外边的数字为对该结点的编号。第29页/共115页7.2.2 7.2.2 二叉树性质二叉树性质 性性质质1 非非空空二二叉叉树树上上叶叶结结点点数数等等于于双双分分支支结结点点数数加加1。证证明明：设设二二叉叉树树上上叶叶结结点点数数为为n0,单单分分支支结结点点数数为为n1,双双分分支支结结点点

23、数数为为n2,则则总总结结点点数数=n0+n1+n2。在在一一棵棵二二叉叉树树中中,所所有有结结点点的的分分支支数数(即即度度数数)应应等等于于单单分分支支结结点点数数加加上上双双分分支支结结点点数数的的2倍倍,即即总总的的分分支支数数=n1+2n2。由由于于二二叉叉树树中中除除根根结结点点以以外外,每每个个结结点点都都有有惟惟一一的的一一个个分分支支指指向向它它,因因此此二二叉叉树树中中有有：总总的的分分支支数数=总总结结点点数数-1。由上述三个等式可得：由上述三个等式可得：n1+2n2=n0+n1+n2-1即：即：n0=n2+1第30页/共115页 性性质质2 非非空空二二叉叉树树上上第第

24、i层层上上至至多多有有2i-1个个结结点点,这这里应有里应有i1。由树的性质由树的性质2可推出。可推出。性性质质3 高高度度为为h的的二二叉叉树树至至多多有有2h-1个个结结点点(h1)。由树的性质由树的性质3可推出。可推出。第31页/共115页 性性 质质 4 对对 完完 全全 二二 叉叉 树树 中中 编编 号号 为为 i的的 结结 点点(1in,n1,n为结点数为结点数)有：有：(1)若若i n/2,即即2in,则则编编号号为为i的的结结点点为为分分支支结点结点,否则为叶子结点。否则为叶子结点。(2)若若n为为奇奇数数,则则每每个个分分支支结结点点都都既既有有左左孩孩子子结结点点,也也有有

25、右右孩孩子子结结点点；若若n为为偶偶数数,则则编编号号最最大大的的分分支支结结点点(编编号号为为)只只有有左左孩孩子子结结点点,没没有有右右孩孩子子结结点点,其其余余分支结点都有左、右孩子结点。分支结点都有左、右孩子结点。第32页/共115页 (3)若若编编号号为为i的的结结点点有有左左孩孩子子结结点点,则则左左孩孩子子结结点点的的编编号号为为2i；若若编编号号为为i的的结结点点有有右右孩孩子子结结点点,则则右右孩孩子结点的编号为子结点的编号为(2i+1)。(4)除除树树根根结结点点外外,若若一一个个结结点点的的编编号号为为i,则则它它的的双双亲亲结结点点的的编编号号为为 i/2,也也就就是是

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

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

28、的的右右孩孩子子结结点点始始终终为为空空,原原因因是是一一般般的的树的根结点不存在兄弟结点和相邻的树。树的根结点不存在兄弟结点和相邻的树。第35页/共115页将森林转换为二叉树的过程将森林转换为二叉树的过程第36页/共115页2.2.二叉树还原为森林、树二叉树还原为森林、树 (1)对对于于一一棵棵二二叉叉树树中中任任一一结结点点k0,沿沿着着k1右右孩孩子子结结点点的的右右子子树树方方向向搜搜索索所所有有右右孩孩子子结结点点,即即搜搜索索结结点点序序列列k2,k3,km,其其中中ki+1为为ki的的右右孩孩子子结结点点(1im),km没有右孩子结点。没有右孩子结点。(2)删去删去k1,k2,k

29、m之间连线。之间连线。(3)若若k1有双亲结点有双亲结点k,则连接则连接k与与ki(2im)。(4)将图形规整化将图形规整化,使各结点按层次排列使各结点按层次排列。第37页/共115页将一棵二叉树还原为树的过程将一棵二叉树还原为树的过程第38页/共115页7.3 7.3 二叉树存储结构二叉树存储结构 7.3.1 7.3.1 二叉树的顺序存储结构二叉树的顺序存储结构 7.3.2 7.3.2 二叉树的链式存储结构二叉树的链式存储结构第39页/共115页7.3.1 7.3.1 二叉树的顺序存储结构二叉树的顺序存储结构 二叉树的顺序存储结构中结点的存放次序是：二叉树的顺序存储结构中结点的存放次序是：对

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

31、顺序存储结构顺序存储结构第41页/共115页7.3.2 7.3.2 二叉树的链式存储结构二叉树的链式存储结构 在二叉树的链接存储中在二叉树的链接存储中,结点的结构如下结点的结构如下:typedef struct node ElemType data;struct node*lchild,*rchild;BTNode;其其中中,data表表示示值值域域,用用于于存存储储对对应应的的数数据据元元素素,lchild和和rchild分分别别表表示示左左指指针针域域和和右右指指针针域域,用用于于分分别别存存储储左左孩孩子子结结点点和和右右孩孩子子结结点点(即即左左、右右子子树树的的根根结点结点)的存储位

32、置。的存储位置。第42页/共115页二叉树及其链式存储结构二叉树及其链式存储结构 第43页/共115页7.4 7.4 二叉树的遍历二叉树的遍历7.4.1 7.4.1 二叉树遍历的概念二叉树遍历的概念7.4.2 7.4.2 二叉树遍历递归算法二叉树遍历递归算法第44页/共115页7.4.1 7.4.1 二叉树遍历的概念二叉树遍历的概念 二二叉叉树树的的遍遍历历是是指指按按照照一一定定次次序序访访问问树树中中所所有有结结点点,并并且且每每个个结结点点仅仅被被访访问问一一次次的的过过程程。它它是是最最基基本的运算本的运算,是二叉树中所有其他运算的基础。是二叉树中所有其他运算的基础。第45页/共115

33、页 1.先序遍历先序遍历先序遍历二叉树的过程是：先序遍历二叉树的过程是：(1)访问根结点；访问根结点；(2)先序遍历左子树；先序遍历左子树；(3)先序遍历右子树。先序遍历右子树。2.中序遍历中序遍历中序遍历二叉树的过程是：中序遍历二叉树的过程是：(1)中序遍历左子树；中序遍历左子树；(2)访问根结点；访问根结点；(3)中序遍历右子树。中序遍历右子树。第46页/共115页 3.后序遍历后序遍历后序遍历二叉树的过程是：后序遍历二叉树的过程是：(1)后序遍历左子树；后序遍历左子树；(2)后序遍历右子树；后序遍历右子树；(3)访问根结点。访问根结点。第47页/共115页7.4.2 7.4.2 二叉树遍

34、历递归算法二叉树遍历递归算法 由由二二叉叉树树的的三三种种遍遍历历过过程程直直接接得得到到如如下下三三种种递递归归算算法如下：法如下：void PreOrder(BTNode*b)/*先序遍历的递归算法先序遍历的递归算法*/if(b!=NULL)printf(%c,b-data);/*访问根结点访问根结点*/PreOrder(b-lchild);PreOrder(b-rchild);第48页/共115页 void InOrder(BTNode*b)/*中序遍历的递归算法中序遍历的递归算法*/if(b!=NULL)InOrder(b-lchild);printf(%c,b-data);/*访问根

35、结点访问根结点*/InOrder(b-rchild);第49页/共115页 void PostOrder(BTNode*b)/*后序遍历递归算法后序遍历递归算法*/if(b!=NULL)PostOrder(b-lchild);PostOrder(b-rchild);printf(%c,b-data);/*访问根结点访问根结点*/第50页/共115页 例例7.2 假假设设二二叉叉树树采采用用二二叉叉链链存存储储结结构构存存储储,试试设设计一个算法计一个算法,输出一棵给定二叉树的所有叶子结点。输出一棵给定二叉树的所有叶子结点。解解：输输出出一一棵棵二二叉叉树树的的所所有有叶叶子子结结点点的的递递归

36、归模模型型f()如下：如下：f(b)：不做任何事件：不做任何事件 若若b=NULL f(b)：输输出出*b结结点点的的data域域 若若*b为为叶子结点叶子结点 f(b)：f(b-lchild);f(b-rchild)其他情况其他情况第51页/共115页 void DispLeaf(BTNode*b)if(b!=NULL)if(b-lchild=NULL&b-rchild=NULL)printf(%c,b-data);else DispLeaf(b-lchild);DispLeaf(b-rchild);第52页/共115页7.5 7.5 二叉树的基本运算及其实现二叉树的基本运算及其实现7.5.

37、1 7.5.1 二叉树的基本运算概述二叉树的基本运算概述7.5.2 7.5.2 二叉树的基本运算算法实现二叉树的基本运算算法实现第53页/共115页7.5.1 7.5.1 二叉树的基本运算概述二叉树的基本运算概述 归纳起来归纳起来,二叉树有以下基本运算：二叉树有以下基本运算：(1)创创建建二二叉叉树树CreateBTNode(*b,*str)：根根据据二二叉叉树树括括号号表表示示法法的的字字符符串串*str生生成成对对应应的的链链式式存存储储结结构。构。(2)查查找找结结点点FindNode(*b,x)：在在二二叉叉树树b中中寻寻找找data域值为域值为x的结点的结点,并返回指向该结点的指针。

38、并返回指向该结点的指针。(3)找找孩孩子子结结点点LchildNode(p)和和RchildNode(p)：分别求二叉树中结点：分别求二叉树中结点*p的左孩子结点和右孩子结点。的左孩子结点和右孩子结点。第54页/共115页 (4)求求高高度度BTNodeDepth(*b)：求求二二叉叉树树b的的高高度度。若若二二叉叉树树为为空空,则则其其高高度度为为0；否否则则,其其高高度度等等于于左左子子树与右子树中的最大高度加树与右子树中的最大高度加l。(5)输输出出二二叉叉树树DispBTNode(*b)：以以括括号号表表示示法法输出一棵二叉树。输出一棵二叉树。第55页/共115页7.5.2 7.5.2

39、 二叉树的基本运算算法实现二叉树的基本运算算法实现 (1)创建二叉树创建二叉树CreateBTNode(*b,*str)用用ch扫扫描描采采用用括括号号表表示示法法表表示示二二叉叉树树的的字字符符串串。分以下几种情况：分以下几种情况：若若ch=(：则则将将前前面面刚刚创创建建的的结结点点作作为为双双亲亲结结点点进进栈栈,并并置置k=1,表表示示其其后后创创建建的的结结点点将将作作为为这这个个结结点点的的左孩子结点；左孩子结点；若若ch=)：表表示示栈栈中中结结点点的的左左右右孩孩子子结结点点处处理理完完毕毕,退栈；退栈；若若ch=,：表示其后创建的结点为右孩子结点；：表示其后创建的结点为右孩子

40、结点；第56页/共115页 其其他他情情况况,表表示示要要创创建建一一个个结结点点,并并根根据据k值值建建立立它它与与栈栈中中结结点点之之间间的的联联系系,当当k=1时时,表表示示这这个个结结点点作作为为栈栈中中结结点点的的左左孩孩子子结结点点,当当k=2时时,表表示示这这个个结结点点作作为为栈栈中中结结点点的的右右孩孩子子结结点点。如如此此循循环环直直到到str处处理理完完毕毕。算算法法中中使使用用一一个个栈栈St保保存存双双亲亲结结点点,top为为其其栈栈指指针针,k指指定定其其后后处处理理的的结结点点是是双双亲亲结结点点(保保存存在在栈栈中中)的左孩子结点的左孩子结点(k=1)还是右孩子

41、结点还是右孩子结点(k=2)。第57页/共115页 void CreateBTNode(BTNode*&b,char*str)BTNode*StMaxSize,*p=NULL;int top=-1,k,j=0;char ch;b=NULL;/*建立的二叉树初始时为空建立的二叉树初始时为空*/ch=strj;while(ch!=0)/*str未扫描完时循环未扫描完时循环*/switch(ch)case(:top+;Sttop=p;k=1;break;/*为左孩子结点为左孩子结点*/case):top-;break;case,:k=2;break;/*为孩子结点右结点为孩子结点右结点*/第58页/

42、共115页 default:p=(BTNode*)malloc(sizeof(BTNode);p-data=ch;p-lchild=p-rchild=NULL;if(b=NULL)/*p为二叉树的根结点为二叉树的根结点*/b=p;else /*已建立二叉树根结点已建立二叉树根结点*/switch(k)case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break;j+;ch=strj;第59页/共115页 例例如如,对对于于括括号号表表示示串串A(B(D(,G),C(E,F),建建立立二叉树链式存储结构的过程如下表所示。二叉树链式存储结构的过程如

43、下表所示。ch算法执行的操作算法执行的操作St中元素中元素A建立建立A结点结点,b指向该结点指向该结点空空(A结点进栈结点进栈,k=1AB建建立立B结结点点,因因k=1,将将其其作作为为A结结点点的的左左孩子结点孩子结点A(B结点进栈结点进栈,k=1ABD建建立立D结结点点,因因k=1,将将其其作作为为B结结点点的的左左孩子结点孩子结点AB第60页/共115页ch算法执行的操作算法执行的操作St中元素中元素(D结点进栈结点进栈,k=1ABD,k=2ABDG建建立立E结结点点,因因k=2,将将其其作作为为D结结点的右孩子结点点的右孩子结点ABD)退栈一次退栈一次AB)退栈一次退栈一次A,k=2A

44、C建建立立C结结点点,因因k=2,将将其其作作为为A结结点的右孩子结点点的右孩子结点A(C结点进栈结点进栈,k=1ACE建建立立E结结点点,因因k=1,将将其其作作为为C结结点的左孩子结点点的左孩子结点AC,k=2AC第61页/共115页ch算法执行的操作算法执行的操作St中元素中元素F建建立立F结结点点,因因k=2,将将其其作作为为C结结点点的右孩子结点的右孩子结点AC)退栈一次退栈一次A)退栈一次退栈一次空空ch扫描完毕扫描完毕算法结束算法结束生成的二叉树生成的二叉树第62页/共115页 (2)查找结点查找结点FindNode(*b,x)采采用用先先序序遍遍历历递递归归算算法法查查找找值值

45、为为x的的结结点点。找找到到后后返回其指针返回其指针,否则返回否则返回NULL。算法如下：。算法如下：BTNode*FindNode(BTNode*b,ElemType x)BTNode*p;if(b=NULL)return NULL;else if(b-data=x)return b;else p=FindNode(b-lchild,x);if(p!=NULL)return p;else return FindNode(b-rchild,x);第63页/共115页 (3)找孩子结点找孩子结点LchildNode(p)和和RchildNode(p)直直接接返返回回*p结结点点的的左左孩孩子子结

46、结点点或或右右孩孩子子结结点点的的指指针。算法如下：针。算法如下：BTNode*LchildNode(BTNode*p)return p-lchild;BTNode*RchildNode(BTNode*p)return p-rchild;第64页/共115页(4)求高度求高度BTNodeDepth(*b)求二叉树的高度的递归模型求二叉树的高度的递归模型f()如下：如下：f(NULL)=0 f(b)=MAXf(b-lchild),f(b-rchild)+1 其他情况其他情况对应的算法如下：对应的算法如下：第65页/共115页int BTNodeDepth(BTNode*b)int lchildd

47、ep,rchilddep;if(b=NULL)return(0);/*空树的高度为空树的高度为0*/else lchilddep=BTNodeDepth(b-lchild);/*求左子树的高度为求左子树的高度为lchilddep*/rchilddep=BTNodeDepth(b-rchild);/*求右子树的高度为求右子树的高度为rchilddep*/return(lchilddeprchilddep)?(lchilddep+1):(rchilddep+1);第66页/共115页 (5)输出二叉树输出二叉树DispBTNode(*b)其其过过程程是是：对对于于非非空空二二叉叉树树b,先先输输出

48、出其其元元素素值值,当当存存在在左左孩孩子子结结点点或或右右孩孩子子结结点点时时,输输出出一一个个“(”符符号号,然然后后递递归归处处理理左左子子树树,输输出出一一个个“,”符符号号,递递归归处处理理右右子树子树,最后输出一个最后输出一个“)”符号。对应的递归算法如下：符号。对应的递归算法如下：第67页/共115页 void DispBTNode(BTNode*b)if(b!=NULL)printf(%c,b-data);if(b-lchild!=NULL|b-rchild!=NULL)printf();DispBTNode(b-lchild);/*递归处理左子树递归处理左子树*/if(b-r

49、child!=NULL)printf(,);DispBTNode(b-rchild);/*递归处理右子树递归处理右子树*/printf();第68页/共115页 例例7.3 假假设设二二叉叉树树采采用用二二叉叉链链存存储储结结构构,设设计计一一个个算算法法判判断断两两棵棵二二叉叉树树是是否否相相似似,所所谓谓二二叉叉树树t1和和t2是是相相似似的的指指的的是是t1和和t2都都是是空空的的二二叉叉树树；或或者者t1和和t2的的根根结结点点是是相相似似的的,以以及及t1的的左左子子树树和和t2的的左左子子树树是是相似的且相似的且t1的右子树与的右子树与t2的右子树是相似的。的右子树是相似的。解：判

50、断两棵二叉树是否相似的递归模型解：判断两棵二叉树是否相似的递归模型f()如如下：下：f(t1,t2)=true 若若t1=t2=NULLf(t1,t2)=false 若若t1、t2之一为之一为NULL,另一不为另一不为NULLf(t1,t2)=f(t1-lchild,t2-lchild)&其他情况其他情况 f(t1-rchild,t2-rchild)对应的算法如下：对应的算法如下：第69页/共115页int Like(BTNode*b1,BTNode*b2)/*t1和和t2两棵二叉树相似时返回两棵二叉树相似时返回1,否则返回否则返回0*/int like1,like2;if(b1=NULL&b