数据结构树形PPT课件

《数据结构树形PPT课件》由会员分享，可在线阅读，更多相关《数据结构树形PPT课件（144页珍藏版）》请在装配图网上搜索。

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

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

3、子集本身又是一棵符合本定义的树,称为根称为根root的子的子树。树。第3页/共144页树的表示树的表示 ( (1) 树形表示法。这是树的最基本的表示树形表示法。这是树的最基本的表示,使用一使用一棵倒置的树表示树结构棵倒置的树表示树结构,非常直观和形象。下图就是非常直观和形象。下图就是采用这种表示法。采用这种表示法。 A C G J B E D F I H M K L 树形表示法树形表示法 第4页/共144页 (2) 文氏图表示法。使用集合以及集合文氏图表示法。使用集合以及集合的包含关系描述树结构。下图就是树的文氏的包含关系描述树结构。下图就是树的文氏图表示法。图表示法。 H L D K I M

4、 C G J E B F 文氏图表示法文氏图表示法 A 第5页/共144页 (3) 凹入表示法。使用线段的伸缩描述树结凹入表示法。使用线段的伸缩描述树结构。下图是树的凹入表示法。构。下图是树的凹入表示法。第6页/共144页 (4) 括号表示法。将树的根结点写在括号的左括号表示法。将树的根结点写在括号的左边边,除根结点之外的其余结点写在括号中并用逗除根结点之外的其余结点写在括号中并用逗号间隔来描述树结构。下图是树的括号表示法。号间隔来描述树结构。下图是树的括号表示法。 括号表示法括号表示法 A(B(E,F),C(G(J),D(H,I(K,L,M) 第7页/共144页树的基本术语树的基本术语 1.

5、 结点的度与树的度：树中某个结点的子树的个结点的度与树的度：树中某个结点的子树的个数称为该结点的度。树中各结点的度的最大值称为数称为该结点的度。树中各结点的度的最大值称为树的度树的度,通常将度为通常将度为m的树称为的树称为m次树次树。 2. 分支结点与叶结点：度不为零的结点称为分支结点与叶结点：度不为零的结点称为非非终端结点终端结点,又叫又叫分支结点分支结点。度为零的结点称为。度为零的结点称为终端结终端结点点或或叶结点叶结点。在分支结点中。在分支结点中,每个结点的分支数就是每个结点的分支数就是该结点的度。如对于度为该结点的度。如对于度为1的结点的结点,其分支数为其分支数为1,被称被称为为单分支

6、结点单分支结点；对于度为；对于度为2的结点的结点,其分支数为其分支数为2,被称被称为为双分支结点双分支结点,其余类推。其余类推。第8页/共144页 3. 路径与路径长度：对于任意两个结点路径与路径长度：对于任意两个结点ki和和kj,若若树中存在一个结点序列树中存在一个结点序列ki,ki1,ki2,kin,kj,使得序列中使得序列中除除ki外的任一结点都是其在序列中的前一个结点的后外的任一结点都是其在序列中的前一个结点的后继继,则称该结点序列为由则称该结点序列为由ki到到kj的一条路径的一条路径,用路径所用路径所通过的结点序列通过的结点序列(ki,ki1,ki2,kj)表示这条路径。路径表示这条

7、路径。路径的长度等于路径所通过的结点数目减的长度等于路径所通过的结点数目减1(即路径上分支即路径上分支数目数目)。可见。可见,路径路径就是从就是从ki出发出发“自上而下自上而下”到达到达kj所通过的树中结点序列。显然所通过的树中结点序列。显然,从树的根结点到树中从树的根结点到树中其余结点均存在一条路径。其余结点均存在一条路径。第9页/共144页 4. 孩子结点、双亲结点和兄弟结点：在一棵树中孩子结点、双亲结点和兄弟结点：在一棵树中,每个结点的后继每个结点的后继,被称作该结点的被称作该结点的孩子结点孩子结点(或子女结或子女结点点)。相应地。相应地,该结点被称作孩子结点的该结点被称作孩子结点的双亲

8、结点双亲结点(或父或父母结点母结点)。具有同一双亲的孩子结点互为兄弟结点。具有同一双亲的孩子结点互为兄弟结点。进一步推广这些关系进一步推广这些关系,可以把每个结点的所有子树中可以把每个结点的所有子树中的结点称为该结点的的结点称为该结点的子孙结点子孙结点,从树根结点到达该结从树根结点到达该结点的路径上经过的所有结点被称作该结点的点的路径上经过的所有结点被称作该结点的祖先结祖先结点点。第10页/共144页 5. 结点的层次和树的高度：树中的每个结点都结点的层次和树的高度：树中的每个结点都处在一定的层次上。结点的层次从树根开始定义处在一定的层次上。结点的层次从树根开始定义,根根结点为第结点为第1层层

9、,它的孩子结点为第它的孩子结点为第2层层,以此类推以此类推,一个一个结点所在的层次为其双亲结点所在的层次加结点所在的层次为其双亲结点所在的层次加1。树中。树中结点的最大层次称为结点的最大层次称为树的高度树的高度(或树的深度或树的深度)。 6. 有序树和无序树：若树中各结点的子树是按有序树和无序树：若树中各结点的子树是按照一定的次序从左向右安排的照一定的次序从左向右安排的,且相对次序是不能随且相对次序是不能随意变换的意变换的,则称为则称为有序树有序树,否则称为否则称为无序树无序树。第11页/共144页 7. 森林：森林：n(n0)个互不相交的树的集合称个互不相交的树的集合称为森林。森林的概念与树

10、的概念十分相近为森林。森林的概念与树的概念十分相近,因为因为只要把树的根结点删去就成了森林。反之只要把树的根结点删去就成了森林。反之,只要只要给给n棵独立的树加上一个结点棵独立的树加上一个结点,并把这并把这n棵树作为棵树作为该结点的子树该结点的子树,则森林就变成了树。则森林就变成了树。第12页/共144页树的性质树的性质性质性质1 树中的结点数等于所有结点的度数加树中的结点数等于所有结点的度数加1。 证明：根据树的定义证明：根据树的定义,在一棵树中在一棵树中,除树根结点外除树根结点外,每个结点有且仅有一个前驱结点。也就是说每个结点有且仅有一个前驱结点。也就是说,每个结每个结点与指向它的一个分支

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

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

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

14、树的高度为h,若在该若在该树中前树中前h-1层都是满的层都是满的,即每一层的结点数都等于即每一层的结点数都等于mi-1个个(1ih-1),第第h层层(即最后一层即最后一层)的结点数可能满的结点数可能满,也可也可能不满能不满,则该树具有最小的高度。其高度则该树具有最小的高度。其高度h可计算如下：可计算如下：第16页/共144页根据树的性质根据树的性质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只能取整数只能取整数,所以所以

15、 h= logm(n(m-1)+1) 结论得证。结论得证。111 mmh11 mmh第17页/共144页 例例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) 最大高度为最大高度为n-2。第18页/共144页树的基本运算树的基本运算 树的运算主要分为三

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

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

18、根结点。第21页/共144页树的存储结构树的存储结构1. 1. 双亲存储结构双亲存储结构 这种存储结构是一种顺序存储结构这种存储结构是一种顺序存储结构, ,用一组连用一组连续空间存储树的所有结点续空间存储树的所有结点, ,同时在每个结点中附同时在每个结点中附设一个伪指针指示其双亲结点的位置。设一个伪指针指示其双亲结点的位置。 A D B C G E F A -1 B 0 C 0 D 0 E 2 F 2 G 2 0 1 2 3 4 5 6 (a) (b) 树的双亲存储结构示意图树的双亲存储结构示意图第22页/共144页2. 孩子链存储结构孩子链存储结构 孩子链存储结构可按树的度孩子链存储结构可按

19、树的度(即树中所有结点度的即树中所有结点度的最大值最大值)设计结点的孩子结点指针域个数。下图设计结点的孩子结点指针域个数。下图(a)的树的树对应的孩子链存储结构如图对应的孩子链存储结构如图(b)所示。所示。 A B C F D E (a) G A B C D E F G (b) 树的树的孩子链孩子链存储结构示意图存储结构示意图第23页/共144页3. 孩子兄弟链存储结构孩子兄弟链存储结构 孩子兄弟链存储结构是为每个结点设计三个域：孩子兄弟链存储结构是为每个结点设计三个域：一个数据元素域一个数据元素域,一个该结点的第一个孩子结点指一个该结点的第一个孩子结点指针域针域,一个该结点的下一个兄弟结点指

20、针域。下图一个该结点的下一个兄弟结点指针域。下图(a)的树对应的孩子兄弟链存储结构如图的树对应的孩子兄弟链存储结构如图(b)所示。所示。 A B C F D E (a) G A B D C E G F (b) 树的树的孩子兄弟链孩子兄弟链存储结构示意图存储结构示意图第24页/共144页7.2 7.2 二叉树概念和性质二叉树概念和性质 二叉树概念二叉树概念二叉树性质二叉树性质二叉树与树、森林之间的转换二叉树与树、森林之间的转换第25页/共144页二叉树概念二叉树概念 二叉树也称为二次树或二分树二叉树也称为二次树或二分树,它是有限的结点集它是有限的结点集合合,这个集合或者是空这个集合或者是空,或者

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

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

23、的编号。该结点的编号。 A B C D E H I J K F G L M N O 1 2 3 4 5 6 7 8 9 10 15 11 12 13 14 满二叉树满二叉树 第29页/共144页 若二叉树中最多只有最下面两层的结点的度数可若二叉树中最多只有最下面两层的结点的度数可以小于以小于2,2,并且最下面一层的叶结点并且最下面一层的叶结点 都依次排列在该都依次排列在该层最左边的位置上层最左边的位置上, ,则这样的二叉树称为则这样的二叉树称为完全二叉树完全二叉树。如下图所示为一棵完全二叉树。同样可以对完全二叉如下图所示为一棵完全二叉树。同样可以对完全二叉树中每个结点进行连续编号树中每个结点进

24、行连续编号, ,编号的方法同满二叉树编号的方法同满二叉树相同。图中每个结点外边的数字为对该结点的编号。相同。图中每个结点外边的数字为对该结点的编号。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉树完全二叉树 第30页/共144页二叉树性质二叉树性质 性质性质1 非空二叉树上叶结点数等于双分支结点数加非空二叉树上叶结点数等于双分支结点数加1。 证明：设二叉树上叶结点数为证明：设二叉树上叶结点数为n0,单分支结点数为单分支结点数为n1,双分支结点数为双分支结点数为n2,则总结点数则总结点数=n0+n1+n2。在一棵。在一棵二叉树中二叉树中,所

25、有结点的分支数所有结点的分支数(即度数即度数)应等于单分支结应等于单分支结点数加上双分支结点数的点数加上双分支结点数的2倍倍,即总的分支数即总的分支数=n1+2n2。 由于二叉树中除根结点以外由于二叉树中除根结点以外,每个结点都有惟一的一每个结点都有惟一的一个分支指向它个分支指向它,因此二叉树中有：总的分支数因此二叉树中有：总的分支数=总结点总结点数数-1。 由上述三个等式可得：由上述三个等式可得：n1+2n2=n0+n1+n2-1即：即：n0=n2+1第31页/共144页 性质性质2 非空二叉树上第非空二叉树上第i层上至多有层上至多有2i-1个结点个结点,这这里应有里应有i1。 由树的性质由

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

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

28、时,其双其双亲结点的编号为亲结点的编号为i/2,它是双亲结点的左孩子结点它是双亲结点的左孩子结点,当当i为奇数时为奇数时,其双亲结点的编号为其双亲结点的编号为(i-1)/2,它是双亲结点它是双亲结点的右孩子结点。的右孩子结点。第34页/共144页 性质性质5 具有具有n个个(n0)结点的完全二叉树的高度结点的完全二叉树的高度为为 log2n+1 或或 log2n +1。 由完全二叉树的定义和树的性质由完全二叉树的定义和树的性质3可推出。可推出。第35页/共144页二叉树与树、森林之间的转换二叉树与树、森林之间的转换1森林、树转换为二叉树森林、树转换为二叉树 步骤如下：步骤如下： (1) 在所有

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

30、孩子结点始终为空叉树的根结点的右孩子结点始终为空,原因是一般的原因是一般的树的根结点不存在兄弟结点和相邻的树。树的根结点不存在兄弟结点和相邻的树。第37页/共144页 A B C D E F G H I A B E F G C D H I (a) (c) A B C D E F G H I (b) 将森林转换为二叉树的过程将森林转换为二叉树的过程第38页/共144页2. 2. 二叉树还原为森林、树二叉树还原为森林、树 步骤如下：步骤如下： (1) 对于一棵二叉树中任一结点对于一棵二叉树中任一结点k0,沿着沿着k0的左的左孩子结点孩子结点k1的右子树方向搜索所有右孩子结点的右子树方向搜索所有右孩

31、子结点,即即搜索结点序列搜索结点序列k2,k3,km,其中其中ki+1为为ki的右孩子结的右孩子结点点(1im),km没有右孩子结点。没有右孩子结点。 (2) 删去删去k1,k2,km之间连线。之间连线。 (3) 若若k1有双亲结点有双亲结点k,则连接则连接k与与ki(2im)。 (4) 将图形规整化将图形规整化,使各结点按层次排列使各结点按层次排列。第39页/共144页 A D H B F C G E A B D C F E H G (a) (c) A B D C F E H G (b) 将一棵二叉树还原为树的过程将一棵二叉树还原为树的过程第40页/共144页7.3 7.3 二叉树存储结构二

32、叉树存储结构 二叉树的顺序存储结构二叉树的顺序存储结构 二叉树的链式存储结构二叉树的链式存储结构第41页/共144页二叉树的顺序存储结构二叉树的顺序存储结构 二叉树的顺序存储结构中结点的存放次序是：二叉树的顺序存储结构中结点的存放次序是：对该树中每个结点进行编号对该树中每个结点进行编号,其编号从小到大的顺其编号从小到大的顺序就是结点存放在连续存储单元的先后次序。若序就是结点存放在连续存储单元的先后次序。若把二叉树存储到一维数组中把二叉树存储到一维数组中,则该编号就是下标值则该编号就是下标值加加1(注意注意,C/C+语言中数组的起始下标为语言中数组的起始下标为0)。树。树中各结点的编号与等高度的

33、完全二叉树中对应位中各结点的编号与等高度的完全二叉树中对应位置上结点的编号相同。置上结点的编号相同。 利用二叉树的性质利用二叉树的性质4。第42页/共144页 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉树完全二叉树 A B C D E F G H I J K123456789101112131415顺序存储结构顺序存储结构第43页/共144页二叉树的链式存储结构二叉树的链式存储结构 在二叉树的链接存储中在二叉树的链接存储中,结点的结构如下结点的结构如下: typedef struct node ElemType data; struct

34、 node *lchild,*rchild; BTNode; 其中其中,data表示值域表示值域,用于存储对应的数据元用于存储对应的数据元素素,lchild和和rchild分别表示左指针域和右指针域分别表示左指针域和右指针域,用于用于分别存储左孩子结点和右孩子结点分别存储左孩子结点和右孩子结点(即左、右子树的即左、右子树的根结点根结点)的存储位置。的存储位置。第44页/共144页 A B C E F D G A B C D E F G (a) (b) 二叉树及其链式存储结构二叉树及其链式存储结构 第45页/共144页7.4 7.4 二叉树的遍历二叉树的遍历二叉树遍历的概念二叉树遍历的概念二叉树

35、遍历递归算法二叉树遍历递归算法二叉树遍历非递归算法二叉树遍历非递归算法 第46页/共144页二叉树遍历的概念二叉树遍历的概念 二叉树的遍历是指按照一定次序访问树中所有二叉树的遍历是指按照一定次序访问树中所有结点结点,并且每个结点仅被访问一次的过程。它是最基并且每个结点仅被访问一次的过程。它是最基本的运算本的运算,是二叉树中所有其他运算的基础。是二叉树中所有其他运算的基础。第47页/共144页1. 先序遍历先序遍历先序遍历二叉树的过程是：先序遍历二叉树的过程是：(1) 访问根结点；访问根结点；(2) 先序遍历左子树；先序遍历左子树；(3) 先序遍历右子树。先序遍历右子树。2. 中序遍历中序遍历中

36、序遍历二叉树的过程是：中序遍历二叉树的过程是：(1) 中序遍历左子树；中序遍历左子树；(2) 访问根结点；访问根结点；(3) 中序遍历右子树。中序遍历右子树。第48页/共144页 3. 后序遍历后序遍历后序遍历二叉树的过程是：后序遍历二叉树的过程是：(1) 后序遍历左子树；后序遍历左子树；(2) 后序遍历右子树；后序遍历右子树；(3) 访问根结点。访问根结点。第49页/共144页二叉树遍历递归算法二叉树遍历递归算法 由二叉树的三种遍历过程直接得到如下三种递归算由二叉树的三种遍历过程直接得到如下三种递归算法如下：法如下： void PreOrder(BTNode *b) /*先序遍历的递归算法先

37、序遍历的递归算法*/ if (b!=NULL) printf(%c ,b-data); /*访问根结点访问根结点*/ PreOrder(b-lchild); PreOrder(b-rchild); 第50页/共144页 void InOrder(BTNode *b) /*中序遍历的递归算法中序遍历的递归算法*/ if (b!=NULL) InOrder(b-lchild); printf(%c ,b-data); /*访问根结点访问根结点*/ InOrder(b-rchild); 第51页/共144页 void PostOrder(BTNode *b) /*后序遍历递归算法后序遍历递归算法*/

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

39、层次遍历序列：A、B、C、D、E、F、G第53页/共144页void LevelOrder(BTNode *b) BTNode *p; BTNode *quMaxSize;/*定义环形队列定义环形队列,存放结点指针存放结点指针*/ int front,rear;/*定义队头和队尾指针定义队头和队尾指针*/ front=rear=-1;/*置队列为空队列置队列为空队列*/ rear+; qurear=b;/*根结点指针进入队列根结点指针进入队列*/ while (front!=rear)/*队列不为空队列不为空*/ front=(front+1)%MaxSize; p=qufront;/*队头出

40、队列队头出队列*/ printf(%c ,p-data);/*访问结点访问结点*/第54页/共144页if (p-lchild!=NULL)/*有左孩子时将其进队有左孩子时将其进队*/ rear=(rear+1)%MaxSize; qurear=p-lchild; if (p-rchild!=NULL)/*有右孩子时将其进队有右孩子时将其进队*/ rear=(rear+1)%MaxSize; qurear=p-rchild; 第55页/共144页 例例7.2 假设二叉树采用二叉链存储结构存储假设二叉树采用二叉链存储结构存储,试设试设计一个算法计一个算法,输出一棵给定二叉树的所有叶子结点。输出一

41、棵给定二叉树的所有叶子结点。 解：输出一棵二叉树的所有叶子结点的递归模型解：输出一棵二叉树的所有叶子结点的递归模型f()如下：如下： f(b)：不做任何事件：不做任何事件 若若b=NULL f(b)：输出：输出*b结点的结点的data域域 若若*b为叶子结点为叶子结点 f(b)：f(b-lchild);f(b-rchild) 其他情况其他情况第56页/共144页 void DispLeaf(BTNode *b) if (b!=NULL) if (b-lchild=NULL & b-rchild=NULL) printf(%c ,b-data); else DispLeaf(b-lchild);

42、 DispLeaf(b-rchild); 第57页/共144页二叉树遍历非递归算法二叉树遍历非递归算法 1. 1. 先序遍历非递归算法先序遍历非递归算法（1）第一种方法）第一种方法由先序遍历的定义可知，其递归模型由先序遍历的定义可知，其递归模型f()如下：如下： f(p)：不做任何事件：不做任何事件 若若p=NULL f(p)：输出：输出*p结点的结点的data域值域值;其他情况其他情况 f(p-lchild); f(p-rchild); 递归等价关系（非相等关系）第58页/共144页void PreOrder1(BTNode *b)BTNode *p;struct BTNode *pt; i

43、nt tag; /1:未访问，未访问，0:可访问可访问 StMaxSize;int top=-1;top+;Sttop.pt=b;Sttop.tag=1;第59页/共144页while (top-1)/栈不空时循环栈不空时循环 if (Sttop.tag=1)/不能直接访问的情况不能直接访问的情况 p=Sttop.pt;top-;if (p!=NULL)/(2)式式 top+;/右孩子结点进栈右孩子结点进栈 Sttop.pt=p-rchild;Sttop.tag=1; top+;/左孩子结点进栈左孩子结点进栈 Sttop.pt=p-lchild;Sttop.tag=1; top+;/根结点进栈

44、根结点进栈 Sttop.pt=p;Sttop.tag=0; /end of if (Sttop.tag=1)第60页/共144页 if (Sttop.tag=0)/直接访问的情况直接访问的情况 printf(%c ,Sttop.pt-data); top-; /while 第61页/共144页（2）第二种方法（常规方法）第二种方法（常规方法） void PreOrder2(BTNode *b) BTNode *StMaxSize,*p; int top=-1;top+; Sttop=b; /根结点入栈根结点入栈while (top-1) /栈不为空时循环栈不为空时循环 p=Sttop; top

45、-; /退栈并访问该结点退栈并访问该结点 printf(%c ,p-data); if (p-rchild!=NULL) /右孩子结点入栈右孩子结点入栈 top+; Sttop=p-rchild; if (p-lchild!=NULL)/左孩子结点入栈左孩子结点入栈 top+; Sttop=p-lchild; 第62页/共144页2. 中序遍历非递归算法中序遍历非递归算法（2）第二种方法（常规方法）第二种方法（常规方法） 由中序遍历过程可知，采用一个栈保存需要返回的结由中序遍历过程可知，采用一个栈保存需要返回的结点指针，先扫描（并非访问）根结点的所有左结点并将它点指针，先扫描（并非访问）根结点

46、的所有左结点并将它们一一进栈。们一一进栈。 然后出栈一个结点，显然该结点没有左孩子结点或者然后出栈一个结点，显然该结点没有左孩子结点或者左孩子结点已访问过（进一步说明该结点的左子树均已访左孩子结点已访问过（进一步说明该结点的左子树均已访问），则访问它。然后扫描该结点的右孩子结点，将其进问），则访问它。然后扫描该结点的右孩子结点，将其进栈，再扫描该右孩子结点的所有左结点并一一进栈，如此栈，再扫描该右孩子结点的所有左结点并一一进栈，如此这样，直到栈空为止。这样，直到栈空为止。第63页/共144页 void InOrder2(BTNode *b) BTNode *StMaxSize,*p; int

47、top=-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的右孩子结点的右孩子结点 /end of while(top-1 | p!=NULL) 找*b的最左下结点第64页/共144页3. 后序遍历非递归算法后序遍历非递归算法 （2）第二种方法（常规方法）第二种方法（常规方法） 由

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

49、，为此，为此用用p保存刚刚访问过的结点（初值为保存刚刚访问过的结点（初值为NULL），若），若b-rchild=p成立（成立（在后序遍历中，在后序遍历中，*b的右孩子结点一定刚好在的右孩子结点一定刚好在*b之前访之前访问问），说明），说明*b的左右子树均已访问，现在应访问的左右子树均已访问，现在应访问*b。 第65页/共144页void PostOrder2(BTNode *b)BTNode *StMaxSize;BTNode *p;int flag,top=-1;/栈指针置初值栈指针置初值do while (b!=NULL) /将将*b的所有左结点进栈的所有左结点进栈 top+; Sttop

50、=b; b=b-lchild; p=NULL; /p指向栈顶结点的前一个已访问的结点指向栈顶结点的前一个已访问的结点 flag=1; /设置设置b的访问标记为已访问过的访问标记为已访问过找最左下结点第66页/共144页 while (top!=-1 & flag=1) b=Sttop; /取出当前的栈顶元素取出当前的栈顶元素 if (b-rchild=p) printf(%c ,b-data);/访问访问*b结点结点top-;p=b;/p指向则被访问的结点指向则被访问的结点 else b=b-rchild; /b指向右孩子结点指向右孩子结点 flag=0;/设置未被访问的标记设置未被访问的标记

51、 /end of while (top!=-1 & flag=1) while (top!=-1); b b的右孩子不存在或已访问过第67页/共144页 从上述过程可知，栈中保存的是当前从上述过程可知，栈中保存的是当前结点结点*b的所有祖先结点（均未访问过）。的所有祖先结点（均未访问过）。 例如，求一个结点的所有祖先结点。例如，求一个结点的所有祖先结点。第68页/共144页7.5 7.5 二叉树的基本运算及其实现二叉树的基本运算及其实现二叉树的基本运算概述二叉树的基本运算概述二叉树的基本运算算法实现二叉树的基本运算算法实现第69页/共144页二叉树的基本运算概述二叉树的基本运算概述 归纳起来归

52、纳起来,二叉树有以下基本运算：二叉树有以下基本运算： (1)创建二叉树创建二叉树CreateBTNode(*b,*str)：根据二叉：根据二叉树括号表示法的字符串树括号表示法的字符串*str生成对应的链式存储结构。生成对应的链式存储结构。 (2)查找结点查找结点FindNode(*b,x)：在二叉树：在二叉树b中寻找中寻找data域值为域值为x的结点的结点,并返回指向该结点的指针。并返回指向该结点的指针。 (3)找孩子结点找孩子结点LchildNode(p)和和RchildNode(p)：分别求二叉树中结点分别求二叉树中结点*p的左孩子结点和右孩子结点。的左孩子结点和右孩子结点。第70页/共1

53、44页 (4)求高度求高度BTNodeDepth(*b)：求二叉树：求二叉树b的高度。的高度。若二叉树为空若二叉树为空,则其高度为则其高度为0；否则；否则,其高度等于左子其高度等于左子树与右子树中的最大高度加树与右子树中的最大高度加l。 (5)输出二叉树输出二叉树DispBTNode(*b)：以括号表示法：以括号表示法输出一棵二叉树。输出一棵二叉树。第71页/共144页二叉树的基本运算算法实现二叉树的基本运算算法实现 (1) 创建二叉树创建二叉树CreateBTNode(*b,*str) 用用ch扫描采用括号表示法表示二叉树的字符串。分扫描采用括号表示法表示二叉树的字符串。分以下几种情况：以下

54、几种情况： 若若ch=(：则将前面刚创建的结点作为双亲结点：则将前面刚创建的结点作为双亲结点进栈进栈,并置并置k=1,表示其后创建的结点将作为这个结点的表示其后创建的结点将作为这个结点的左孩子结点；左孩子结点； 若若ch=)：表示栈中结点的左右孩子结点处理完：表示栈中结点的左右孩子结点处理完毕毕,退栈；退栈； 若若ch=,：表示其后创建的结点为右孩子结点；：表示其后创建的结点为右孩子结点；第72页/共144页 其他情况其他情况,表示要创建一个结点表示要创建一个结点,并根据并根据k值建值建立它与栈中结点之间的联系立它与栈中结点之间的联系,当当k=1时时,表示这个结点表示这个结点作为栈中结点的左孩

55、子结点作为栈中结点的左孩子结点,当当k=2时时,表示这个结点表示这个结点作为栈中结点的右孩子结点。如此循环直到作为栈中结点的右孩子结点。如此循环直到str处理处理完毕。算法中使用一个栈完毕。算法中使用一个栈St保存双亲结点保存双亲结点,top为其栈为其栈指针指针,k指定其后处理的结点是双亲结点指定其后处理的结点是双亲结点(保存在栈中保存在栈中)的左孩子结点的左孩子结点(k=1)还是右孩子结点还是右孩子结点(k=2)。第73页/共144页 void CreateBTNode(BTNode * &b,char *str) BTNode *StMaxSize,*p=NULL; int top=-1,

56、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; /*为孩子结点右结点为孩子结点右结点*/第74页/共144页 default:p=(BTNode *)malloc(sizeof(BTNode); p-data=ch;p-lchild=p-rchild=NULL;

57、 if (b=NULL) /*p为二叉树的根结点为二叉树的根结点*/ b=p; else /*已建立二叉树根结点已建立二叉树根结点*/ switch(k) case 1:Sttop-lchild=p;break; case 2:Sttop-rchild=p;break; j+;ch=strj; 第75页/共144页 例如例如,对于括号表示串对于括号表示串A(B(D(,G),C(E,F),建立建立二叉树链式存储结构的过程如下表所示。二叉树链式存储结构的过程如下表所示。ch算法执行的操作算法执行的操作St中元素中元素A建立建立A结点结点,b指向该结点指向该结点空空(A结点进栈结点进栈,k=1AB建

58、立建立B结点结点,因因k=1,将其作为将其作为A结点的左结点的左孩子结点孩子结点A(B结点进栈结点进栈,k=1ABD建立建立D结点结点,因因k=1,将其作为将其作为B结点的左结点的左孩子结点孩子结点AB第76页/共144页ch算法执行的操作算法执行的操作St中元素中元素(D结点进栈结点进栈,k=1ABD,k=2ABDG建立建立G结点结点,因因k=2,将其作为将其作为D结结点的右孩子结点点的右孩子结点ABD)退栈一次退栈一次AB)退栈一次退栈一次A,k=2AC建立建立C结点结点,因因k=2,将其作为将其作为A结结点的右孩子结点点的右孩子结点A(C结点进栈结点进栈,k=1ACE建立建立E结点结点,

59、因因k=1,将其作为将其作为C结结点的左孩子结点点的左孩子结点AC,k=2AC第77页/共144页ch算法执行的操作算法执行的操作St中元素中元素F建立建立F结点结点,因因k=2,将其作为将其作为C结点结点的右孩子结点的右孩子结点AC)退栈一次退栈一次A)退栈一次退栈一次空空ch扫描完毕扫描完毕算法结束算法结束 A B C D E F G 生成的二叉树生成的二叉树第78页/共144页 (2) 查找结点查找结点FindNode(*b,x) 采用先序遍历递归算法查找值为采用先序遍历递归算法查找值为x的结点。找到后返的结点。找到后返回其指针回其指针,否则返回否则返回NULL。算法如下：。算法如下：

60、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); 第79页/共144页 (3) 找孩子结点找孩子结点LchildNode(p)和和RchildNode(p) 直接返回直接返回*p结点的左孩子结点或右孩子结点的指结点的左孩子结点或右孩子结点的指针。算法如下：针。算法如下：

61、 BTNode *LchildNode(BTNode *p) return p-lchild; BTNode *RchildNode(BTNode *p) return p-rchild; 第80页/共144页(4) 求高度求高度BTNodeDepth(*b)求二叉树的高度的递归模型求二叉树的高度的递归模型f()如下：如下： f(NULL)=0 f(b)=MAXf(b-lchild),f(b-rchild)+1 其他情况其他情况对应的算法如下：对应的算法如下：第81页/共144页int BTNodeDepth(BTNode *b) int lchilddep,rchilddep; if (b=

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

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

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

65、树是相似的。 解：判断两棵二叉树是否相似的递归模型解：判断两棵二叉树是否相似的递归模型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) 对应的算法如下：对应的算法如下：第85页/共144页int Like(BTNode *b1,BTNode *b2)/*t1和和t2两棵二叉树相似时返回两棵二叉树相似时返回1,否则返回否则返回0*/ int like1,li

66、ke2; if (b1=NULL & b2=NULL) return 1; else if (b1=NULL | b2=NULL) return 0; else like1=Like(b1-lchild,b2-lchild); like2=Like(b1-rchild,b2-rchild); return (like1 & like2); /*返回返回like1和和like2的与的与*/ 第86页/共144页 例例7.4 假设二叉树采用二叉链存储结构假设二叉树采用二叉链存储结构,设计一个算设计一个算法法Level()求二叉树中指定结点的层数。并利用本节的基求二叉树中指定结点的层数。并利用本节的基本运算编写一个完整的程序本运算编写一个完整的程序,建立教材中图建立教材中图7.8(a)的二叉的二叉树的二叉链树的二叉链,对于用户输入的任何结点值计算出在该二对于用户输入的任何结点值计算出在该二叉树中的层次。叉树中的层次。 解：本题采用递归算法解：本题采用递归算法,设设h返回返回p所指结点的高所指结点的高度度,其初值为其初值为0。找到指定的结点时返回其层次；否。找到指定的结点时返回其层次；否则返回