理学数据结构树形结构.pptx

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

1、例例7.37.3：A AB BC CD DE EF FG GH HI IJ JK KL LM M不是一棵树不是一棵树,因为因为:子树子树 Tree-H=HTree-H=H，MM子树子树 Tree-I=ITree-I=I，MM出现了交叉，违反树的定义。出现了交叉，违反树的定义。树树的的定定义义是是递递归归的的，因因为为在在树树的的定定义义中中有有用用到到树树的的定定义义。它它刻刻画画了了树树的的固固有有特性，即一棵树由若干棵子树构成，而子树又由更小的若干棵子树构成。特性，即一棵树由若干棵子树构成，而子树又由更小的若干棵子树构成。树是一种非线性数据结构，具有以下特点：树是一种非线性数据结构，具有以

2、下特点：它它的的每每个个节节点点都都可可以以有有不不止止一一个个后后继继(除除根根以以外外的的所所有有结结点点)，都都有有且且只只有有一一个个前驱前驱；这些数据结点按分支关系组织起来，清晰地反映了数据元素之间的层次关系。这些数据结点按分支关系组织起来，清晰地反映了数据元素之间的层次关系。可以看出，数据元素之间存在的关系是一对多的，或者多对一的关系。可以看出，数据元素之间存在的关系是一对多的，或者多对一的关系。第1页/共31页补充说明补充说明树的分类：树的分类：(1)(1)自由树自由树(无根树无根树)：结点的排列无关紧要。：结点的排列无关紧要。结点结点数为数为1 1结点结点数为数为2 2结点结点

3、数为数为3 3结点结点数为数为4 4(2)(2)有根树：根结点位于树的顶。有根树：根结点位于树的顶。(默认讨论的树默认讨论的树)结点结点数为数为1 1结点结点数为数为2 2结点结点数为数为3 3结点结点数为数为4 4(3)(3)有序树：能表示第一个孩子、第二孩子有序树：能表示第一个孩子、第二孩子(如族谱、二叉树就是有序的如族谱、二叉树就是有序的)第2页/共31页二、树的形式化定义：二、树的形式化定义：(数学语言定义数学语言定义)树树定定义义为为集集合合：T TK,RK,R。K K是是包包含含 n n 个个结结点点的的有有穷穷集集合合(n0)(n0)，关关系系R R满满足以下条件：足以下条件：(

4、1)(1)有有且且仅仅有有一一个个结结点点k k0 0KK，它它对对于于关关系系 R R 来来说说没没有有前前驱驱结结点点，结结点点k k0 0称称作树的根。作树的根。(2)(2)除结点除结点k k0 0外，外，K K中的每个结点中的每个结点对于关系对于关系R R来说都来说都有且仅有一个前驱结点有且仅有一个前驱结点。(3)K(3)K中中每个结点每个结点对于关系对于关系R R来说来说可以有多个后继结点可以有多个后继结点。三、抽象数据类型树的定义：三、抽象数据类型树的定义：ADT TreeADT Tree 数据对象：数据对象：D=aD=ai i|1in,n0|1in,n0，a ai iElemTy

5、peElemType类型类型 数据关系：数据关系：R=aR=|a|ai i,a,aj jD,1in,1jn,D,1in,1jn,其中每个元素只有一个前驱，其中每个元素只有一个前驱，可以有零个或多个后继结点，有且仅有一个元素没有前驱可以有零个或多个后继结点，有且仅有一个元素没有前驱 基本运算：基本运算：InitTree(&t);/*InitTree(&t);/*初始化树：构造一个只有一个元素的树初始化树：构造一个只有一个元素的树*/ClearTree(&t);/*ClearTree(&t);/*销毁树：释放树销毁树：释放树t t占用的存储空间占用的存储空间*/Parent(t);/*Parent

6、(t);/*求元素求元素t t的前驱的前驱*/Sons(t);/*Sons(t);/*求元素求元素t t的后继的后继*/第3页/共31页7.1.27.1.2 树的逻辑表示方法树的逻辑表示方法(其它表示形式其它表示形式)1.1.树树形形表表示示法法：这这是是树树的的最最基基本本的的表表示示，使使用用一一棵棵倒倒置置的的树树表表示示树树结结构构，非非常常直观和形象。直观和形象。A AB BC CD DE EF FG GH HI IJ JK KL LM M2.2.集合法集合法Tree-ATree-A的结构：的结构：结点结点A A包括包括B,C,DB,C,D 结点结点B B包括包括E,FE,F 结点结

7、点C C包括包括GG 结点结点D D包括包括H,I,JH,I,J 结点结点E E包括包括K,LK,L 结点结点H H包括包括MM第4页/共31页A AB BC CD DE EF FG GH HI IJ JK KL LM M3.3.范式图法或文氏图法范式图法或文氏图法(Venn Diagram)(Venn Diagram)每每棵棵树树对对应应一一个个圆圆圈圈，圆圆圈圈包包含含根根结结点点和和子子树树的的圆圆圈圈，同同一一棵棵根根结结点点下下的的各各子树对应的圆圈是不能相交的。子树对应的圆圈是不能相交的。A AB BC CD DE EF FG GH HI IJ JK KL LM MA:B,C,DA

8、:B,C,DB:E,FB:E,FC:GC:GD:H,I,JD:H,I,JE:K,LE:K,LH:MH:M第5页/共31页4.4.缩格法缩格法(Indentation)(Indentation)或凹入表示法或凹入表示法A AB BC CD DE EF FG GH HI IJ JK KL LM M5.5.嵌套括弧法嵌套括弧法(Nested Parentheses)(Nested Parentheses)用用最最外外层层括括弧弧表表示示树树的的根根，子子树树嵌嵌套套在在根根括弧之内。括弧之内。(A(A(B ,C ,D B ,C ,D )(E ,FE ,F)(G)(G)(H ,I,JH ,I,J)(K

9、,LK,L)(M M)6.6.层数号码法层数号码法(Level Number Format)(Level Number Format)用层数来表示结点所在的位置用层数来表示结点所在的位置 1 1 A A2 2 B B2 2 C C2 2 D D3 3 E E3 3 F F3 3 G G3 3 H H3 3 I I3 3 J J4 4 K K4 4 L L4 4 M MA:B,C,DA:B,C,DB:E,FB:E,FC:GC:GD:H,I,JD:H,I,JE:K,LE:K,LH:MH:M第6页/共31页7.1.37.1.3 树的基本术语树的基本术语 结点的度和树的度：结点的度和树的度：(1)(1

10、)结点拥有的子树的个数称为该结点的度；结点拥有的子树的个数称为该结点的度；A AB BC CD DE EF FG GH HI IJ JK KL LM M结结点点A A的的度度为为3 3、B B的的度度为为2 2、C C的的度度为为1 1、D D的的度度为为3 3、F,F,G,I,J,K,L G,I,J,K,L 和和 M M 的度为的度为0 0；(2)(2)树树中中各各结结点点度度的的最最大大值值称称为为树树的的度度，通通常将度为常将度为 m m 的树称为的树称为 m m 次树。次树。如左图树如左图树 A A 的度为的度为3 3。分支结点与叶结点：分支结点与叶结点：(1)(1)度度不不为为0 0

11、的的结结点点称称为为非非终终端端结结点点，又叫分支结点；又叫分支结点；(2)(2)度为度为0 0的结点称为终端结点或叶结点；的结点称为终端结点或叶结点；(3)(3)在分支结点中在分支结点中,每个结点的分支数就是该结点的度。每个结点的分支数就是该结点的度。如如对对于于度度为为1 1的的结结点点，其其分分支支数数为为1 1，被被称称为为单单分分支支结结点点；对对于于度度为为2 2的的结结点点，其其分支数为分支数为2 2，被称为双分支结点，其余类推。，被称为双分支结点，其余类推。第7页/共31页 路径与路径长度：路径与路径长度：对对于于任任意意两两个个结结点点 k ki i 和和 k kj j，若若

12、树树中中存存在在一一个个结结点点序序列列k ki i,k ki1i1,k ki2i2,k kinin,k kj j，使使得得序序列列中中除除 k ki i 外外的的任任一一结结点点都都是是其其在在序序列列中中的的前前一一个个结结点点的的后后继继,则则称称该该结结点点序序列列为为由由 k ki i 到到 k kj j 的的一一条条路路径径，用用路路径径所所通通过过的的结结点点序序列列(k(ki i,k ki1i1,k ki2i2,k kj j)表表示示这这条条路路径径。路路径径的的长长度度等等于于路路径径所所通通过过的的结结点点数数目目减减1(1(即即路路径径上上分分支支数数目目)。可可见见，路

13、路径径就就是是从从 k ki i 出出发发“自自上上而而下下”到到达达 k kj j 所所通通过过的的树树中中结结点序列。显然，从树的根结点到树中其余结点均存在一条路径。点序列。显然，从树的根结点到树中其余结点均存在一条路径。A AB BC CD DE EF FG GH HI IJ JK KL LM M例如：例如：A A 到到 L L 的路径：的路径：A(kA(ki i)B B(k(ki1i1)E E(k(ki2i2)L L(k(kj j)也可以表示为：也可以表示为：(A,B,E,J)(A,B,E,J)路径长度：路径长度：3 3，有以下两种计算方法，有以下两种计算方法 -结点数结点数 1 1-

14、分支数分支数第8页/共31页 孩子结点、双亲结点和兄弟结点：孩子结点、双亲结点和兄弟结点：在在一一棵棵树树中中，每每个个结结点点的的后后继继，被被称称作作该该结结点点的的孩孩子子结结点点(或或子子女女结结点点)。相相应应地地，该该结结点点被被称称作作孩孩子子结结点点的的双双亲亲结结点点(或或父父母母结结点点)。具具有有同同一一双双亲亲的的孩孩子子结结点点互互为为兄兄弟弟结结点点。进进一一步步推推广广这这些些关关系系，可可以以把把每每个个结结点点的的所所有有子子树树中中的的结结点点称称为为该该结结点点的的子子孙孙结结点点，从从树树根根结结点点到到达达该该结结点点的的路路径径上上经经过过的的所所有

15、有结结点点被被称称作作该该结点的祖先结点。结点的祖先结点。结点的层次和树的高度结点的层次和树的高度 树树中中的的每每个个结结点点都都处处在在一一定定的的层层次次上上。结结点点的的层层次次从从树树根根开开始始定定义义，根根结结点点为为第第1 1层层，它它的的孩孩子子结结点点为为第第2 2层层，以以此此类类推推。一一个个结结点点所所在在的的层层次次为为其其双双亲亲结结点点所在的层次加所在的层次加1 1。树中结点的最大层次称为。树中结点的最大层次称为树的高度树的高度(或或树的深度树的深度)。有序树和无序树：有序树和无序树：若若树树中中各各结结点点的的子子树树是是按按照照一一定定的的次次序序从从左左向

16、向右右安安排排的的，且且相相对对次次序序是是不不能能随意变换的，则称为随意变换的，则称为有序树有序树，否则称为，否则称为无序树无序树。如家族的族谱就是有序树，可以表示子女之间的大小关系。如家族的族谱就是有序树，可以表示子女之间的大小关系。森林：森林：n n(n(n0)0)个个互互不不相相交交的的树树的的集集合合称称为为森森林林。森森林林的的概概念念与与树树的的概概念念十十分分相相近近，因因为为只只要要把把树树的的根根结结点点删删去去就就成成了了森森林林。反反之之，只只要要给给 n n 棵棵独独立立的的树树加加上上一个结点，并把这一个结点，并把这 n n 棵树作为该结点的子树，则森林就变成了树。

17、棵树作为该结点的子树，则森林就变成了树。第9页/共31页7.1.4 7.1.4 树的性质树的性质性质性质1 1：树中的结点数等于所有结点的度数加树中的结点数等于所有结点的度数加1 1。证明：证明：根根据据树树的的定定义义，在在一一棵棵树树中中除除树树根根结结点点外外，每每个个结结点点有有且且仅仅有有一一个个前前驱驱结结点点。也也就就是是说说，每每个个结结点点与与指指向向它它的的一一个个分分支支一一一一对对应应，所所以以除除树树根根之之外外的的结结点点数数等等于所有结点的分支数于所有结点的分支数(度数度数)，从而可得树中的结点数等于所有结点的度数加，从而可得树中的结点数等于所有结点的度数加1 1

18、。A AB BC CD DE EF FG GH HI IJ JK KL LM M除除树树根根结结点点外外，每每个个结结点点与与指指向向它它的的一一个个分分支支一一对应一一对应;1 12 23 34 45 56 67 78 89 9101011111212除树根之外的结点数等于分支数除树根之外的结点数等于分支数(结点度数和结点度数和););第10页/共31页性质性质2 2：度为度为 m m 的树中第的树中第 i i 层上至多有层上至多有 m mi-1i-1个个 结点，结点，i1i1。证明：证明：(采用数学归纳法采用数学归纳法)对对于于第第一一层层，因因为为树树中中的的第第一一层层上上只只有有一一

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

20、多多为为第第(i-1)(i-1)层层上上结结点点数数的的 m m 倍倍，即即至至多多为为m mi-2i-2m=mm=mi-1i-1个个，这这与命题相同，故命题成立。与命题相同，故命题成立。第11页/共31页性质性质3 3：高度为高度为 h h 的的 m m 次树至多有次树至多有 个结点。个结点。证明：证明：由由树树的的性性质质2 2可可知知，第第 i i 层层上上最最多多结结点点数数为为 m mi-1i-1(i=1,2,(i=1,2,h),h)，显显然然当当高高度度为为 h h 的的 m m 次次树树(即即度度为为 m m的的树树)上上每每一一层层都都达达到到最最多多结结点点数数时时，整整个个

21、 m m 次次树树具具有最多结点数，因此有：有最多结点数，因此有：整个树的最多结点数整个树的最多结点数 =每一层最多结点数之和每一层最多结点数之和 =m=m0 0+m+m1 1+m+m2 2+m+mh-1h-1=当一棵当一棵m m次树上的结点数达到：次树上的结点数达到：(m(mh h-1)/(m-1)-1)/(m-1)则称该树为满则称该树为满m m次数。次数。例如高度为例如高度为3 3的满的满2 2次树次树(每个结点的度最大为每个结点的度最大为2)2)，总结点数，总结点数=(2=(23 3-1)/(2-1)=7-1)/(2-1)=71 12 23 34 45 56 67 7性质性质4 4：具有

22、具有 n n 个结点的个结点的 m m 次树的最小高度为次树的最小高度为 logm(n(m-1)+1)logm(n(m-1)+1)。证明：略证明：略第12页/共31页例例7.47.4：若若一一棵棵三三次次树树中中度度为为 3 3 的的结结点点个个数数为为2 2，度度为为 2 2 的的结结点点个个数数为为1 1，度度为为1 1的结点个数为的结点个数为2 2，则该三次树中总的结点个数和度为，则该三次树中总的结点个数和度为0 0的结点个数分别是多少？的结点个数分别是多少？解：设该三次树中总的结点个数：解：设该三次树中总的结点个数：n n 度为度为0 0的结点个数：的结点个数：n n0 0 度为度为1

23、 1的结点个数：的结点个数：n n1 1 度为度为2 2的结点个数：的结点个数：n n2 2 度为度为3 3的结点个数：的结点个数：n n3 3 由已知条件得到：由已知条件得到：n n1 1=2=2，n n2 2=1=1，n n3 3=2=2 由树的性质由树的性质1 1可知：可知：(树中的结点数等于所有结点的度数加树中的结点数等于所有结点的度数加1 1)n=0 n=0n n0 0+1+1n n1 1+2+2n n2 2+3+3n n3 3+1+1 =11 =11 又因为：又因为：n=nn=n0 0+n n1 1+n n2 2+n n3 3 即：即：n n0 0=n =n-n n1 1-n n2

24、 2-n n3 3 =11-2-1-2 =11-2-1-2 =6 =6 所以该三次树中总的结点个数和度为所以该三次树中总的结点个数和度为0 0的结点个数分别是的结点个数分别是1111和和6 6。第13页/共31页7.1.5 7.1.5 树的基本运算树的基本运算 由由于于树树是是非非线线性性结结构构，结结点点之之间间的的关关系系较较线线性性结结构构复复杂杂得得多多，所所以以树树的的运运算算较以前讨论过的各种线性数据结构的运算要复杂许多。较以前讨论过的各种线性数据结构的运算要复杂许多。树的运算主要分为三大类：树的运算主要分为三大类：(1)(1)第一类，寻找满足某种特定关系的结点，如寻找当前结点的双

25、亲结点等；第一类，寻找满足某种特定关系的结点，如寻找当前结点的双亲结点等；(2)(2)第第二二类类，插插入入或或删删除除某某个个结结点点，如如在在树树的的当当前前结结点点上上插插入入一一个个新新结结点点或或删删除当前结点的第除当前结点的第i i个个孩子结点等；孩子结点等；(3)(3)第三类，第三类，遍历树中每个结点遍历树中每个结点(重点内容重点内容)。树树的的遍遍历历运运算算是是指指按按某某种种方方式式访访问问树树中中的的每每一一个个结结点点，且且每每一一个个结结点点只只被被访访问问一一次次。树树的的遍遍历历运运算算的的算算法法主主要要有有先先根根遍遍历历和和后后根根遍遍历历两两种种。注注意意

26、，下下面面的的先先根遍历和后根遍历算法都是递归的。根遍历和后根遍历算法都是递归的。1.1.先根遍历先根遍历 先根遍历过程为：先根遍历过程为：(1)(1)访问根结点；访问根结点；(2)(2)按照从左到右的次序先根遍历根结点的每一棵子树。按照从左到右的次序先根遍历根结点的每一棵子树。第14页/共31页例例7.57.5：求该树的先序遍历次序。：求该树的先序遍历次序。(1)(1)访问根结点；访问根结点；(2)(2)按照从左到右的次序先根遍历根结点的每一棵子树。按照从左到右的次序先根遍历根结点的每一棵子树。R RA AB BC CD DE EF FG GH HK KR R按照从左到右的次序先根遍历子树按

27、照从左到右的次序先根遍历子树A A、B B、C C遍历每个子树时又要按照原则遍历每个子树时又要按照原则(1)(1)和和(2)(2)进行进行即遍历即遍历B B之前应完成之前应完成A A的遍历。的遍历。A A D D E E B B C C F F G G H H K K2.2.后根遍历后根遍历 后根遍历过程为：后根遍历过程为：(1)(1)按照从左到右的次序后根遍历根结点的每一棵子树；按照从左到右的次序后根遍历根结点的每一棵子树；(2)(2)访问根结点。访问根结点。遇到遇到R R时不访问，要待到其所有子树全部访问完毕时不访问，要待到其所有子树全部访问完毕(左至右左至右)，即准备访问，即准备访问A

28、A；处理处理A A时遵守同样的规则。时遵守同样的规则。D D E E A A B B G G H H K K F F C C R R第15页/共31页A AB BC CD DE EF FG GH HI IJ JK KL LM M练习：写出下面这棵树的先根和后根遍历次序。练习：写出下面这棵树的先根和后根遍历次序。先根遍历：先根遍历：A,B,E,K,L,F,C,G,D,H,M,I,JA,B,E,K,L,F,C,G,D,H,M,I,J后根遍历：后根遍历：K,L,E,F,B,G,C,M,H,I,J,D,AK,L,E,F,B,G,C,M,H,I,J,D,A第16页/共31页7.1.6 7.1.6 树的存

29、储结构树的存储结构 树的存储既要求保存结点的数据元素本身，又要存储结点之间的逻辑关系。树的存储既要求保存结点的数据元素本身，又要存储结点之间的逻辑关系。1.1.二维数组表示法二维数组表示法(Array Representation,(Array Representation,补充补充)数组中的行数目用树中结点数的数目表示，列数用树的度数组中的行数目用树中结点数的数目表示，列数用树的度+1+1表示。表示。例例7.67.6：A AB BC CD DE EF FG GH HI IJ JK KL LM MA:B,C,DA:B,C,DB:E,FB:E,FC:GC:GD:H,I,JD:H,I,JE:K,L

30、E:K,LH:MH:M该树有该树有1313个结点即数组有个结点即数组有1313行，树的度为行，树的度为3 3所以数组要有所以数组要有4 4列列 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 91010111112121313 1 2 3 4 1 2 3 4 A A B B C C D D E E F F G G H H I I J J K K L L M M 1 2 3 (1 2 3 (子树根的地址子树根的地址)4 5 -4 5 -6 -6 -7 8 9 7 8 910 11 -10 11 -12 -12 -特特点点：查查找找任任一一结结点点的的孩孩子子结结点点非非常常方

31、方便，查找父结点麻烦便，查找父结点麻烦解决方法：增加一列存储父结点的地址解决方法：增加一列存储父结点的地址5 5-1-10 00 00 01 11 12 23 33 33 34 44 47 7第17页/共31页2.2.双亲存储结构双亲存储结构 这这种种存存储储结结构构是是一一种种顺顺序序存存储储结结构构，用用一一组组连连续续空空间间存存储储树树的的所所有有结结点点，同同时在每个结点中附设一个伪指针时在每个结点中附设一个伪指针(下标下标)指示其双亲结点的位置。指示其双亲结点的位置。R RA AB BC CD DE EF FG GH HK K按按层及由左到右的顺序给结点编号：层及由左到右的顺序给结

32、点编号：0 01 12 23 34 45 56 67 78 89 9用一维数组来存储这用一维数组来存储这1010个结点个结点每个结点对应一个数组元素每个结点对应一个数组元素每个元素包括两个域每个元素包括两个域数据域数据域:存放该结点所包含的数据存放该结点所包含的数据指针域指针域:指出该结点的双亲结点的位置指出该结点的双亲结点的位置数数组组下标下标结结点点的的数据域数据域双双亲亲位置位置 0 R 0 R-1-1 1 A 1 A0 0 2 B 2 B 0 0 3 C 3 C 0 0 4 D 4 D 1 1 5 E 5 E 1 1 6 F 6 F 3 3 7 G 7 G 6 6 8 H 8 H 6

33、6 9 K 9 K 6 6特点特点:利用每个结点只有一个利用每个结点只有一个双亲双亲(除根以外除根以外)的特性；的特性；求求某某个个结结点点的的双双亲亲结结点点十十分分容容易易，但但求求某某个个结结点点的的孩孩子子结结点点时需要遍历整个结构。时需要遍历整个结构。结点描述：结点描述：#define MAX-TREE-SIZE 100#define MAX-TREE-SIZE 100 typedef struct PTNode typedef struct PTNode TElemType data;TElemType data;int parent;int parent;PTNode;PTNod

34、e;typedef struct typedef struct PTNode nodesMAX-TREE-SIZE;PTNode nodesMAX-TREE-SIZE;int n;/*int n;/*结点的个数结点的个数*/Ptree;Ptree;第18页/共31页R RA AB BC CD DE EF FG GH HK K0 01 12 23 34 45 56 67 78 89 9数数组组下标下标结结点点的的数据域数据域双双亲亲位置位置 0 R 0 R-1-1 1 A 1 A0 0 2 B 2 B 0 0 3 C 3 C 0 0 4 D 4 D 1 1 5 E 5 E 1 1 6 F 6 F

35、 3 3 7 G 7 G 6 6 8 H 8 H 6 6 9 K 9 K 6 6存储结构的讨论：存储结构的讨论：现有另一棵树：现有另一棵树：W WX XY YZ Z10 W -110 W -111 X 1011 X 1012 Y 1012 Y 1013 Z 1013 Z 10-多棵树可共享存储空间多棵树可共享存储空间 -适用查找父结点，不适用查找孩子结点适用查找父结点，不适用查找孩子结点 -面向对象技术中等价类的应用与该存储摸式的思路一致面向对象技术中等价类的应用与该存储摸式的思路一致如果树合并：如果树合并：0 0 1 1第19页/共31页R RA AB BC CD DE EF FG GH H

36、K K3.3.孩子链表存储结构孩子链表存储结构(1)(1)基本存储方式基本存储方式 每个结点所含域的个数由各结点的度来决定。每个结点所含域的个数由各结点的度来决定。HeadHeadR RA AB BC CD DE EF FG GH HK K用用数数组组表表示示树树时时操操作作方方式式简简单单，但但浪浪费费内内存存；以以链链表表表表示示树树节节省省空空间间，但但每每个个结结点点的的结结构构不不同同，因因此此进进行行插插入入和和删删除除操操作作时时的流程非常复杂。的流程非常复杂。改进的方法是使每个节点结构相同。改进的方法是使每个节点结构相同。域的个数即为树的度数。域的个数即为树的度数。第20页/共

37、31页R RA AB BC CD DE EF FG GH HK K(2)(2)改进一：各结点的结构一致改进一：各结点的结构一致(指针域的个数即为树的度数，该树的度为指针域的个数即为树的度数，该树的度为3)3)HeadHeadR RA AB BC CD DE E F F G GH HK K 此方法的空间利用率并不高；此方法的空间利用率并不高；树树的的存存储储结结构构有有很很多多，都都有有各各自自的的优优缺缺点点。常常用用的的方方式式将将顺序与链式的特性结合在一起。顺序与链式的特性结合在一起。第21页/共31页(3)(3)改进二改进二:整体是一个数组、一个元素存一个结点整体是一个数组、一个元素存一

38、个结点每个结点有两个域：数据域、指针域每个结点有两个域：数据域、指针域(链表头链表头)；每个结点指针指向自己的第一个孩子；每个结点指针指向自己的第一个孩子；每个孩子指针按顺序指向自己第一个兄弟；每个孩子指针按顺序指向自己第一个兄弟；R RA AB BC CD DE EF FG GH HK Kdatadatalinklink 0 R 0 R 1 A 1 A 2 B 2 B 3 C 3 C 4 D 4 D 5 E 5 E 6 F 6 F 7 G 7 G 8 H 8 H 9 K 9 K下标序号下标序号1 12 23 3 存储方式类似双亲存储结构存储方式类似双亲存储结构(区别在于区别在于指针域不是下标

39、指针域不是下标)表表示示R R的的第第一一个个孩孩子子存存储储在在1 1号号下下标标元元素素中中、第第二二个个在在2 2号号、第第三三个个在在3 3号号。访访问问时时只只要要找找到到第第一一个个孩孩子子就就可可以以沿孩子链表寻访所有子树。沿孩子链表寻访所有子树。4 45 5 6 6 7 78 89 9 表示父子关系表示父子关系表示兄弟关系表示兄弟关系第22页/共31页datadatalinklink 0 R 0 R 1 A 1 A 2 B 2 B 3 C 3 C 4 D 4 D 5 E 5 E 6 F 6 F 7 G 7 G 8 H 8 H 9 K 9 K表头指针表头指针1 12 23 3 4

40、 45 5 6 6 7 78 89 9 结构描述：结构描述：#define MAX-TREE-SIZE 100#define MAX-TREE-SIZE 100typedef struct CTNode typedef struct CTNode int child;int child;struct CTNode*next;struct CTNode*next;*ChildPtr;*ChildPtr;typedef struct typedef struct TElemType data;TElemType data;ChildPtr firstchild;/*ChildPtr firstch

41、ild;/*孩子链表头指针孩子链表头指针*/CTBox;CTBox;typedef struct typedef struct CTBox nodesMAX-TREE-SIZE;CTBox nodesMAX-TREE-SIZE;Ctree;Ctree;孩子结点结构孩子结点结构数据元素的结构数据元素的结构讨论：讨论：插入结点插入结点(如插入如插入X X为为A A的孩子的孩子)R RA AB BC CD DE EF FG GH HK KX X-增加数组元素并修改链表增加数组元素并修改链表X X10101010删除结点要引起数据移动删除结点要引起数据移动该结构在图中还将用到该结构在图中还将用到第23

42、页/共31页(4)(4)改进三改进三：带双亲的孩子链表：带双亲的孩子链表结点由三个域组成结点由三个域组成:数据域、指向第一个孩子的指针域数据域、指向第一个孩子的指针域 和指向双亲的指针域和指向双亲的指针域即即在在孩孩子子表表示示法法中中增增加加一一个个指指向向双双亲亲的的指指针针域域(引引入入双双亲存储结构的理念亲存储结构的理念)R RA AB BC CD DE EF FG GH HK K0 01 12 23 34 45 56 67 78 89 9datadatalinklink 0 R 0 R 1 A 1 A 2 B 2 B 3 C 3 C 4 D 4 D 5 E 5 E 6 F 6 F 7

43、 G 7 G 8 H 8 H 9 K 9 K1 12 23 3 4 45 5 6 6 7 78 89 9 parentparent0 -1 0 -1 1 0 1 0 2 0 2 0 3 0 3 0 4 1 4 1 5 1 5 1 6 3 6 3 7 6 7 6 8 6 8 6 9 6 9 6 即可以访问每个结点的孩子，也可访问双亲。即可以访问每个结点的孩子，也可访问双亲。第24页/共31页4.4.孩子、兄弟链存储结构孩子、兄弟链存储结构 孩孩子子兄兄弟弟链链存存储储结结构构是是为为每每个个结结点点设设计计三三个个域域：一一是是数数据据元元素素域域、二二是是该该结结点第一个孩子结点的指针域、三是

44、该结点下一个兄弟结点的指针域。点第一个孩子结点的指针域、三是该结点下一个兄弟结点的指针域。R RA AB BC CD DE EF FG GH HK KHeadHeadR RA AD DB BC CF FE E G GH HK K 结点描述：结点描述：typedef struct tnodetypedef struct tnode ElemType data;ElemType data;struct tnode*hp;/*struct tnode*hp;/*指向兄弟指向兄弟*/struct tnode*vp;/*struct tnode*vp;/*指向孩子结点指向孩子结点*/tnodetnode

45、第25页/共31页7.1.7 7.1.7 树的应用树的应用(补充补充)例例7.77.7 皇后问题皇后问题:皇皇后后(N-Queens)(N-Queens)问问题题是是将将N N个个棋棋子子摆摆入入一一个个NNNN的的矩矩阵阵，并并且且规规定定每每一一行行、每每一一列列、每每一一从从右右上上到到左左下下、从从左左上上到到右右下下的的斜斜线线，均均只只放放置置一一个个棋棋子子，不不能能有有重重复的情形发生。以复的情形发生。以4444为例：为例：矩阵中放入棋子时以数码编号，矩阵中放入棋子时以数码编号，1 1(1,1(1,1)(2,1(2,1)(2,2(2,2)(2,3(2,3)2 2(2,4(2,4

46、)(3,1)(3,1)(3,2)(3,2)(3,3)(3,3)(3,4)(3,4)1 12 2(3,1)(3,1)3 3(3,2)(3,2)(3,3)(3,3)(3,4)(3,4)(4,1)(4,1)(4,2)(4,2)(4,3)(4,3)(4,4)(4,4)第26页/共31页1 1(1,1(1,1)(2,1(2,1)(2,2(2,2)(2,3(2,3)(2,4(2,4)(3,1)(3,1)(3,2)(3,2)(3,3)(3,3)(3,4)(3,4)(3,1)(3,1)(3,2)(3,2)(3,3)(3,3)(3,4)(3,4)(4,1)(4,1)(4,2)(4,2)(4,3)(4,3)(4,

47、4)(4,4)(1,2)(1,2)2 2(2,1)(2,1)(2,2)(2,2)(2,3)(2,3)(2,4)(2,4)3 3(3,1)(3,1)(3,2)(3,2)(3,3)(3,3)(3,4)(3,4)4 4(4,1)(4,1)(4,2)(4,2)(4,3)(4,3)(4,4)(4,4)1 12 23 34 41 12 23 31 12 2第27页/共31页例例7.8 7.8 决策树决策树 假假设设有有八八枚枚硬硬币币分分别别编编号号为为a a、b b、c c、d d、e e、f f、g g、h h，在在这这八八枚枚硬硬币币中中，其其中中有有一一枚枚是是假假币币，其其重重量量也也不不同同于

48、于其其他他的的七七枚枚硬硬币币，但但不不知知道道假假币币是是比比较较轻轻或或比比较较重重。现现在在希希望望能能利利用用一一具具天天平平来来找找出出该该枚枚假假币币，同同时时也也能能准准确确地地测测出出该该假假币币比比其其它它的的硬硬币币重重或或是是轻轻，此此外外还还要要求求比比较较的的次次数数越越少少越越好好。下下图图是是八八枚枚硬硬币币找找出出其其中一枚假币的决策树，可表示一连串的决策由此找到问题的答案。中一枚假币的决策树，可表示一连串的决策由此找到问题的答案。a+b+c?d+e+fa+b+c?d+e+fa+d?b+ea+d?b+ea-Ha-H e-Le-L c-Hc-H f-Lf-L b-

49、Hb-H d-Ld-L g-Hg-H h-Lh-L h-Hh-H g-Lg-L b-Lb-L d-Hd-H c-Lc-L f-Hf-H a-La-L e-He-Hg?ag?ah?ah?ag?hg?hb?ab?ac?ac?aa?ba?ba+d?b+ea+d?b+ed?ad?aa?ca?ca?ba?b =取出八枚硬币中的六枚取出八枚硬币中的六枚(a,b,c,d,e,f)(a,b,c,d,e,f)分成两堆放至于天平上；分成两堆放至于天平上；因为因为 a+b+c d+e+f a+b+c d+e+f 这表示这表示 g,h g,h 为真币，假币在前六枚中；为真币，假币在前六枚中；拿掉拿掉 c,f c,f

50、并将并将 b,d b,d 互换，互换，比较得比较得a+db+ea+d b+ea+d b+e用用a a 和和 d d 比较比较 若若 a=da=d，因，因 d d 为真币，可得为真币，可得 e e 是一枚假币且较重。是一枚假币且较重。g,h g,h 为真币为真币a a或或e e为假为假b b或或d d为假为假c c或或f f为假为假g g或或h h为假为假g,h g,h 为真币为真币a a或或e e为假为假b b或或d d为假为假第29页/共31页作业：作业：写出下面这棵树的写出下面这棵树的带双亲孩子链表和带双亲孩子链表和孩子、兄弟链存储结构。并回答下述问孩子、兄弟链存储结构。并回答下述问题：题