数据结构——树型结构.ppt

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

1、第6章树型结构树的基本概念树的基本概念 树的遍历树的遍历 树的线性表示树的线性表示 树类的定义树类的定义 树的存储结构树的存储结构 6.1 6.1 树的基本概念树的基本概念 树树树树是由是由是由是由n(n0)n(n0)n(n0)n(n0)个结点构成的有限集合，个结点构成的有限集合，个结点构成的有限集合，个结点构成的有限集合，n=0n=0n=0n=0的的的的树称为树称为树称为树称为空树空树空树空树；当；当；当；当n0n0n0n0时，树中的结点应该满足以下时，树中的结点应该满足以下时，树中的结点应该满足以下时，树中的结点应该满足以下两个条件：两个条件：两个条件：两个条件：(1)(1)(1)(1)有

2、且仅有一个特定的结点称之为有且仅有一个特定的结点称之为有且仅有一个特定的结点称之为有且仅有一个特定的结点称之为根根根根；(2)(2)(2)(2)其余结点分成其余结点分成其余结点分成其余结点分成m(m0)m(m0)m(m0)m(m0)个互不相交的有限集合个互不相交的有限集合个互不相交的有限集合个互不相交的有限集合T T T T1 1 1 1,T T T T2 2 2 2,T T T Tm m m m，其中每一个集合又都是一棵树，称其中每一个集合又都是一棵树，称其中每一个集合又都是一棵树，称其中每一个集合又都是一棵树，称 T T T T1 1 1 1,T,T,T,T2 2 2 2,T T T Tm

3、 m m m为根结点的为根结点的为根结点的为根结点的子树子树子树子树。BDEFGAHIJKC图图图图6.16.1 在树中采用线段连接两个相关联的结点，如在树中采用线段连接两个相关联的结点，如在树中采用线段连接两个相关联的结点，如在树中采用线段连接两个相关联的结点，如A A A A和和和和B B B B，D D D D和和和和H H H H等。其中等。其中等。其中等。其中A A A A和和和和D D D D是上端结点，是上端结点，是上端结点，是上端结点，B B B B和和和和H H H H是下端结点。是下端结点。是下端结点。是下端结点。称称称称A A A A、D D D D分别是分别是分别是分别

4、是B B B B、H H H H的的的的双亲双亲双亲双亲（或（或（或（或父母父母父母父母或或或或前件前件前件前件），），），），B B B B和和和和H H H H分分分分别为别为别为别为A A A A和和和和D D D D的的的的子女子女子女子女（或（或（或（或孩子孩子孩子孩子或或或或后件后件后件后件）。显然，双亲和子）。显然，双亲和子）。显然，双亲和子）。显然，双亲和子女的关系是相对而言的。图女的关系是相对而言的。图女的关系是相对而言的。图女的关系是相对而言的。图6.16.16.16.1中，中，中，中，B B B B是是是是A A A A的子女，但又的子女，但又的子女，但又的子女，但又是是

5、是是E E E E和和和和F F F F的双亲。由于的双亲。由于的双亲。由于的双亲。由于E E E E和和和和F F F F的双亲为同一结点，称的双亲为同一结点，称的双亲为同一结点，称的双亲为同一结点，称E E E E和和和和F F F F互为互为互为互为兄弟兄弟兄弟兄弟。在任何一棵树中，除根结点外，其它任何。在任何一棵树中，除根结点外，其它任何。在任何一棵树中，除根结点外，其它任何。在任何一棵树中，除根结点外，其它任何一个结点有且仅有一个双亲，有一个结点有且仅有一个双亲，有一个结点有且仅有一个双亲，有一个结点有且仅有一个双亲，有0 0 0 0个或多个子女，且它个或多个子女，且它个或多个子女，

6、且它个或多个子女，且它的子女恰巧为其子树的根结点。我们将一结点拥有的的子女恰巧为其子树的根结点。我们将一结点拥有的的子女恰巧为其子树的根结点。我们将一结点拥有的的子女恰巧为其子树的根结点。我们将一结点拥有的子女数称为该子女数称为该子女数称为该子女数称为该结点的度结点的度结点的度结点的度，树中所有结点度的最大值称，树中所有结点度的最大值称，树中所有结点度的最大值称，树中所有结点度的最大值称为为为为树的度树的度树的度树的度。图。图。图。图6.16.16.16.1中，中，中，中，A A A A的度为的度为的度为的度为3 3 3 3，B B B B的度为的度为的度为的度为2 2 2 2，而，而，而，而

7、C C C C的度的度的度的度为为为为0 0 0 0，整棵树的度为，整棵树的度为，整棵树的度为，整棵树的度为3 3 3 3。称度为。称度为。称度为。称度为0 0 0 0的结点为的结点为的结点为的结点为终端结点终端结点终端结点终端结点或或或或叶叶叶叶子结点子结点子结点子结点，称度不为，称度不为，称度不为，称度不为0 0 0 0的结点为非的结点为非的结点为非的结点为非终端结点终端结点终端结点终端结点或或或或分支结点分支结点分支结点分支结点。显然，显然，显然，显然，A A A A、B B B B、D D D D、H H H H均为分支结点，而均为分支结点，而均为分支结点，而均为分支结点，而E E E

8、 E、F F F F、C C C C、G G G G、J J J J、K K K K、I I I I均为叶子结点。均为叶子结点。均为叶子结点。均为叶子结点。称树中连接两个结点的线段为称树中连接两个结点的线段为称树中连接两个结点的线段为称树中连接两个结点的线段为树枝树枝树枝树枝。在树中，。在树中，。在树中，。在树中，若从结点若从结点若从结点若从结点K K K Ki i i i开始沿着树枝自上而下能到达结点开始沿着树枝自上而下能到达结点开始沿着树枝自上而下能到达结点开始沿着树枝自上而下能到达结点K K K Kj j j j，则称从则称从则称从则称从K K K Ki i i i到到到到K K K K

9、j j j j存在一条存在一条存在一条存在一条路径路径路径路径，路径的长度等于所经，路径的长度等于所经，路径的长度等于所经，路径的长度等于所经过的树枝的条数。在图过的树枝的条数。在图过的树枝的条数。在图过的树枝的条数。在图6.16.16.16.1中，从结点中，从结点中，从结点中，从结点A A A A到结点到结点到结点到结点J J J J存在存在存在存在一条路径，路径的长度为一条路径，路径的长度为一条路径，路径的长度为一条路径，路径的长度为3 3 3 3；从；从；从；从D D D D到到到到K K K K也存在一条路径，也存在一条路径，也存在一条路径，也存在一条路径，路径的长度为路径的长度为路径

10、的长度为路径的长度为2 2 2 2。仔细观察不难发现，从树根到树中。仔细观察不难发现，从树根到树中。仔细观察不难发现，从树根到树中。仔细观察不难发现，从树根到树中任何一个结点均存在一条路径。任何一个结点均存在一条路径。任何一个结点均存在一条路径。任何一个结点均存在一条路径。将从树根到某一结点将从树根到某一结点将从树根到某一结点将从树根到某一结点K K K Ki i i i的路径中的路径中的路径中的路径中K K K Ki i i i前所经过的前所经过的前所经过的前所经过的所有结点称为所有结点称为所有结点称为所有结点称为K K K Ki i i i的的的的祖先祖先祖先祖先；反之，以某结点；反之，以

11、某结点；反之，以某结点；反之，以某结点K K K Ki i i i为根的为根的为根的为根的子树中的任何一个结点都称为子树中的任何一个结点都称为子树中的任何一个结点都称为子树中的任何一个结点都称为K K K Ki i i i的的的的子孙子孙子孙子孙。图。图。图。图6.16.16.16.1中，中，中，中，A A A A、D D D D、H H H H均为均为均为均为J J J J和和和和K K K K的祖先，而的祖先，而的祖先，而的祖先，而G G G G、H H H H、I I I I、J J J J和和和和K K K K均为均为均为均为D D D D的的的的子孙。子孙。子孙。子孙。树中树中树中树

12、中结点的层次结点的层次结点的层次结点的层次：从树根开始定义，根结点为：从树根开始定义，根结点为：从树根开始定义，根结点为：从树根开始定义，根结点为第一层，根的子女结点构成第二层，依次类推，若第一层，根的子女结点构成第二层，依次类推，若第一层，根的子女结点构成第二层，依次类推，若第一层，根的子女结点构成第二层，依次类推，若某结点某结点某结点某结点K K K Kj j j j位于第位于第位于第位于第i i i i层，则其子女就位于第层，则其子女就位于第层，则其子女就位于第层，则其子女就位于第i+1i+1i+1i+1层。称层。称层。称层。称树中结点的最大层次数为树的树中结点的最大层次数为树的树中结点

13、的最大层次数为树的树中结点的最大层次数为树的深度深度深度深度或或或或高度高度高度高度。图。图。图。图6.16.16.16.1中，中，中，中，A A A A结点位于第一层，结点位于第一层，结点位于第一层，结点位于第一层，B B B B、C C C C、D D D D位于第位于第位于第位于第2 2 2 2层，层，层，层，E E E E、F F F F、G G G G、H H H H和和和和I I I I位于第三层等等，整棵树的高度为位于第三层等等，整棵树的高度为位于第三层等等，整棵树的高度为位于第三层等等，整棵树的高度为4 4 4 4。若树中任意结点的子树均看成是从左到右有次若树中任意结点的子树均

14、看成是从左到右有次若树中任意结点的子树均看成是从左到右有次若树中任意结点的子树均看成是从左到右有次序的，不能随意交换，则称该树是序的，不能随意交换，则称该树是序的，不能随意交换，则称该树是序的，不能随意交换，则称该树是有序树有序树有序树有序树；否则称；否则称；否则称；否则称之为之为之为之为无序树无序树无序树无序树。下图。下图。下图。下图6.36.36.36.3中的两棵树，若看成是有序树，中的两棵树，若看成是有序树，中的两棵树，若看成是有序树，中的两棵树，若看成是有序树，它们是不等价的；若看成是无序树，两者相等。它们是不等价的；若看成是无序树，两者相等。它们是不等价的；若看成是无序树，两者相等。

15、它们是不等价的；若看成是无序树，两者相等。DCEFABDEFAB 由由m(mm(m0)0)棵互不相交的树构成的集合称为棵互不相交的树构成的集合称为森森林林。森林和树的概念十分相近，一棵树中每个结点，。森林和树的概念十分相近，一棵树中每个结点，其子树的集合即为一个森林；而在森林中的每棵树其子树的集合即为一个森林；而在森林中的每棵树之上加一个共同的根，森林就成为了一棵树。之上加一个共同的根，森林就成为了一棵树。C图图6.3 6.3 有序树和无序树的比较有序树和无序树的比较 树型结构的其他表示方法：树型结构的其他表示方法：树型结构的其他表示方法：树型结构的其他表示方法：A(B(E,F),C,D(G,

16、H(J,K),I)A(B(E,F),C,D(G,H(J,K),I)(a)(a)(a)(a)图图图图6.16.16.16.1的括号表示法的括号表示法的括号表示法的括号表示法BHJKGIEFDCA(b)图图图图6.16.16.16.1的的的的嵌套集合表示法ABEFCDGHJKI (C)图图图图6.16.16.16.1的的的的凹入表示法 6.2 6.2 树类的定义树类的定义 ADT tree ADT tree ADT tree ADT tree 数据对象数据对象数据对象数据对象D D D D：具有相同性质的数据元素构成的有限具有相同性质的数据元素构成的有限具有相同性质的数据元素构成的有限具有相同性质

17、的数据元素构成的有限 集合。集合。集合。集合。数据关系数据关系数据关系数据关系R R R R：如果如果如果如果D D D D为空或为空或为空或为空或D D D D仅含一个元素，则仅含一个元素，则仅含一个元素，则仅含一个元素，则R R R R为为为为 空；否则空；否则空；否则空；否则D D D D中存在一个特殊的结点中存在一个特殊的结点中存在一个特殊的结点中存在一个特殊的结点rootrootrootroot，称称称称 之为根结点，其无前驱；其它结点被分成互之为根结点，其无前驱；其它结点被分成互之为根结点，其无前驱；其它结点被分成互之为根结点，其无前驱；其它结点被分成互 不相交的不相交的不相交的不

18、相交的m(mm(mm(mm(m 0)0)0)0)个集合，分别构成个集合，分别构成个集合，分别构成个集合，分别构成rootrootrootroot的的的的m m m m 棵子树；若这些子树非空，则它们的根结点棵子树；若这些子树非空，则它们的根结点棵子树；若这些子树非空，则它们的根结点棵子树；若这些子树非空，则它们的根结点 rootrootrootrooti i i i均称为整棵树根结点均称为整棵树根结点均称为整棵树根结点均称为整棵树根结点rootrootrootroot的后继结点；的后继结点；的后继结点；的后继结点；而每棵子树也是一棵树，因而它们中数据元而每棵子树也是一棵树，因而它们中数据元而每

19、棵子树也是一棵树，因而它们中数据元而每棵子树也是一棵树，因而它们中数据元 素间的关系也同样满足素间的关系也同样满足素间的关系也同样满足素间的关系也同样满足R R R R的定义。的定义。的定义。的定义。树的基本操作如下：树的基本操作如下：树的基本操作如下：树的基本操作如下：（1 1 1 1）InittreeInittreeInittreeInittree(T)(T)(T)(T)（2 2 2 2）CleartreeCleartreeCleartreeCleartree(T)(T)(T)(T)（3 3 3 3）EmptytreeEmptytreeEmptytreeEmptytree(T)(T)(T)

20、(T)（4 4 4 4）Root(T)Root(T)Root(T)Root(T)（5 5 5 5）Child(T,a,i)Child(T,a,i)Child(T,a,i)Child(T,a,i)（6 6 6 6）Parent(T,a)Parent(T,a)Parent(T,a)Parent(T,a)（7 7 7 7）Degree(T,a)Degree(T,a)Degree(T,a)Degree(T,a)（8 8 8 8）Depth(T)Depth(T)Depth(T)Depth(T)（9 9 9 9）Choose(T,C)Choose(T,C)Choose(T,C)Choose(T,C)（10

21、101010）AddchildAddchildAddchildAddchild（T,a,i,t1T,a,i,t1T,a,i,t1T,a,i,t1）（11111111）DelchildDelchildDelchildDelchild(T,a,i)(T,a,i)(T,a,i)(T,a,i)（12121212）CreatetreeCreatetreeCreatetreeCreatetree(a,F)(a,F)(a,F)(a,F)（13131313）EqualtreeEqualtreeEqualtreeEqualtree(T1,T2)(T1,T2)(T1,T2)(T1,T2)（14141414）Num

22、ofnodeNumofnodeNumofnodeNumofnode(T)(T)(T)(T)（15151515）preorder(T)preorder(T)preorder(T)preorder(T)（16161616）postorderpostorderpostorderpostorder(T)(T)(T)(T)（17171717）levelorderlevelorderlevelorderlevelorder(T)(T)(T)(T)（18181818）DestroytreeDestroytreeDestroytreeDestroytree(T)(T)(T)(T)ADT Tree ADT Tr

23、ee ADT Tree ADT Tree 6.3 6.3 树的存储结构树的存储结构 根据数据元素之间关系的不同表示方式，常用的根据数据元素之间关系的不同表示方式，常用的根据数据元素之间关系的不同表示方式，常用的根据数据元素之间关系的不同表示方式，常用的树存储结构主要有三种：双亲表示法、孩子表示法和树存储结构主要有三种：双亲表示法、孩子表示法和树存储结构主要有三种：双亲表示法、孩子表示法和树存储结构主要有三种：双亲表示法、孩子表示法和孩子兄弟表示法。孩子兄弟表示法。孩子兄弟表示法。孩子兄弟表示法。6.3.1 6.3.1 双亲表示法双亲表示法 在树中，除根结点没有双亲外，其他每个结点的在树中，除根

24、结点没有双亲外，其他每个结点的在树中，除根结点没有双亲外，其他每个结点的在树中，除根结点没有双亲外，其他每个结点的双亲是唯一确定的。因此，根据树的这种性质，存储双亲是唯一确定的。因此，根据树的这种性质，存储双亲是唯一确定的。因此，根据树的这种性质，存储双亲是唯一确定的。因此，根据树的这种性质，存储树中结点时，可以包含两个信息：结点的值树中结点时，可以包含两个信息：结点的值树中结点时，可以包含两个信息：结点的值树中结点时，可以包含两个信息：结点的值datadatadatadata和体和体和体和体现结点之间相互关系的属性现结点之间相互关系的属性现结点之间相互关系的属性现结点之间相互关系的属性_该结

25、点的双亲该结点的双亲该结点的双亲该结点的双亲parentparentparentparent。借助于每个结点的这两个信息便可唯一地表示任何一借助于每个结点的这两个信息便可唯一地表示任何一借助于每个结点的这两个信息便可唯一地表示任何一借助于每个结点的这两个信息便可唯一地表示任何一棵树。这种表示方法称为棵树。这种表示方法称为棵树。这种表示方法称为棵树。这种表示方法称为双亲表示法双亲表示法双亲表示法双亲表示法。#define MAXSIZE 100 define MAXSIZE 100 define MAXSIZE 100 define MAXSIZE 100 typedeftypedeftyped

26、eftypedef char char char char datatype datatype datatype datatype;/*;/*;/*;/*结点值的类型结点值的类型结点值的类型结点值的类型*/*/*/*/typedef structtypedef structtypedef structtypedef struct node /*node /*node /*node /*结点的类型结点的类型结点的类型结点的类型*/*/*/*/datatypedatatypedatatypedatatype data;data;data;data;int int int int parent;/*

27、parent;/*parent;/*parent;/*结点双亲的下标结点双亲的下标结点双亲的下标结点双亲的下标*/*/*/*/node;node;node;node;typedef structtypedef structtypedef structtypedef struct tree tree tree tree node node node node treelisttreelisttreelisttreelistMAXSIZE;/*MAXSIZE;/*MAXSIZE;/*MAXSIZE;/*存放结点的数组存放结点的数组存放结点的数组存放结点的数组*/*/*/*/int int int

28、int length,root;/*length,root;/*length,root;/*length,root;/*树中实际所含结点的树中实际所含结点的树中实际所含结点的树中实际所含结点的 个数及根结点的位置个数及根结点的位置个数及根结点的位置个数及根结点的位置*/*/*/*/tree;tree;tree;tree;BCDEFGAHIKJdatadataparentparentA A-1-1B B0 0C C0 0DD0 0E E1 1F F1 1GG3 3HH3 3I I6 6J J6 6K K6 6012345678910rootroot (a)a)一棵树一棵树一棵树一棵树 (b)(a

29、)b)(a)图的双亲表示法图的双亲表示法图的双亲表示法图的双亲表示法 图图图图6.46.46.3.2 孩子表示法孩子表示法 采用孩子表示法表示一棵树时，树中每个结点除采用孩子表示法表示一棵树时，树中每个结点除采用孩子表示法表示一棵树时，树中每个结点除采用孩子表示法表示一棵树时，树中每个结点除了存储其自身的值之外，还必须指出其所有子女的位了存储其自身的值之外，还必须指出其所有子女的位了存储其自身的值之外，还必须指出其所有子女的位了存储其自身的值之外，还必须指出其所有子女的位置，即整棵树中所有结点的相互关系是通过指明结点置，即整棵树中所有结点的相互关系是通过指明结点置，即整棵树中所有结点的相互关系

30、是通过指明结点置，即整棵树中所有结点的相互关系是通过指明结点子女的位置来体现的，称这种表示法为孩子表示法。子女的位置来体现的，称这种表示法为孩子表示法。子女的位置来体现的，称这种表示法为孩子表示法。子女的位置来体现的，称这种表示法为孩子表示法。根据子女位置的实现方法不同，根据子女位置的实现方法不同，根据子女位置的实现方法不同，根据子女位置的实现方法不同，孩子表示法孩子表示法孩子表示法孩子表示法分为三种：分为三种：分为三种：分为三种：指针方式的孩子表示法指针方式的孩子表示法指针方式的孩子表示法指针方式的孩子表示法 、数组方式的孩子表示法、数组方式的孩子表示法、数组方式的孩子表示法、数组方式的孩子

31、表示法、链表方式的孩子表示法链表方式的孩子表示法链表方式的孩子表示法链表方式的孩子表示法 。1 1 1 1、指针方式的孩子表示法指针方式的孩子表示法指针方式的孩子表示法指针方式的孩子表示法 指针方式的孩子表示法中每个结点通常包含两个指针方式的孩子表示法中每个结点通常包含两个指针方式的孩子表示法中每个结点通常包含两个指针方式的孩子表示法中每个结点通常包含两个域：一个是元素的值域域：一个是元素的值域域：一个是元素的值域域：一个是元素的值域datadatadatadata，另一个为指针数组，数另一个为指针数组，数另一个为指针数组，数另一个为指针数组，数组中的每个元素均为一个指向该结点子女的指针；一组

32、中的每个元素均为一个指向该结点子女的指针；一组中的每个元素均为一个指向该结点子女的指针；一组中的每个元素均为一个指向该结点子女的指针；一棵棵棵棵m m m m度的树，其指针数组的大小即为度的树，其指针数组的大小即为度的树，其指针数组的大小即为度的树，其指针数组的大小即为m m m m。#define m 3 /*#define m 3 /*#define m 3 /*#define m 3 /*树的度数树的度数树的度数树的度数*/*/*/*/typedeftypedeftypedeftypedef char char char char datatype datatype datatype d

33、atatype;/*;/*;/*;/*结点值的类型结点值的类型结点值的类型结点值的类型*/*/*/*/typedef structtypedef structtypedef structtypedef struct node node node node /*/*/*/*结点的类型结点的类型结点的类型结点的类型*/*/*/*/datatypedatatypedatatypedatatype data;data;data;data;struct struct struct struct node*childm;/*node*childm;/*node*childm;/*node*childm;/

34、*指向子女的指针数组指向子女的指针数组指向子女的指针数组指向子女的指针数组*/*/*/*/node,*tree;node,*tree;node,*tree;node,*tree;tree root;tree root;tree root;tree root;其中其中其中其中rootrootrootroot表示指向树根结点的指针。表示指向树根结点的指针。表示指向树根结点的指针。表示指向树根结点的指针。A AB BC C DDE E F F GGHH I I J J K K rootdatachild0child1 child2 图图图图6.46.4中中中中(a)a)图的指针方式的孩子表示法图的指

35、针方式的孩子表示法图的指针方式的孩子表示法图的指针方式的孩子表示法2 2 2 2、数组方式的孩子表示法数组方式的孩子表示法数组方式的孩子表示法数组方式的孩子表示法 为了查找方便，可以将树中的所有结点存储在为了查找方便，可以将树中的所有结点存储在为了查找方便，可以将树中的所有结点存储在为了查找方便，可以将树中的所有结点存储在一个一维数组中，这样每个结点子女的位置便可以一个一维数组中，这样每个结点子女的位置便可以一个一维数组中，这样每个结点子女的位置便可以一个一维数组中，这样每个结点子女的位置便可以通过数组的下标来体现，称这种孩子表示法为数组通过数组的下标来体现，称这种孩子表示法为数组通过数组的下

36、标来体现，称这种孩子表示法为数组通过数组的下标来体现，称这种孩子表示法为数组方式的孩子表示法。方式的孩子表示法。方式的孩子表示法。方式的孩子表示法。#define m 3 define m 3 define m 3 define m 3#define MAXSIZE 20#define MAXSIZE 20#define MAXSIZE 20#define MAXSIZE 20 typedeftypedeftypedeftypedef char char char char datatype datatype datatype datatype;typedef struct typedef s

37、truct typedef struct typedef struct node node node node datatype datatype datatype datatype data;data;data;data;int int int int childm;childm;childm;childm;treenodetreenodetreenodetreenode;treenode treenode treenode treenode treeMAXSIZE;treeMAXSIZE;treeMAXSIZE;treeMAXSIZE;int int int int root;root;r

38、oot;root;int int int int length;length;length;length;datadatachild0child0A A1 1B B4 4C C-1-1DD6 6E E-1-1F F-1-1GG8 8HH-1-1I I-1-1J J-1-1K K-1-1012345678910child1child1 child2child22 23 35 5-1-1-1-1-1-17 7-1-1-1-1-1-1-1-1-1-19 91010-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1root 图图图图6.46.4中中中中(a)a)图的数组方式的孩子表示法图

39、的数组方式的孩子表示法图的数组方式的孩子表示法图的数组方式的孩子表示法3 3 3 3、链表方式的孩子表示法链表方式的孩子表示法链表方式的孩子表示法链表方式的孩子表示法 在树的链表方式的孩子表示法中，把每个结点在树的链表方式的孩子表示法中，把每个结点在树的链表方式的孩子表示法中，把每个结点在树的链表方式的孩子表示法中，把每个结点的子女排列起来形成一个单链表，这样的子女排列起来形成一个单链表，这样的子女排列起来形成一个单链表，这样的子女排列起来形成一个单链表，这样n n n n个结点就形个结点就形个结点就形个结点就形成成成成n n n n个单链表；而个单链表；而个单链表；而个单链表；而n n n

40、n个单链表的头指针又组成一个线个单链表的头指针又组成一个线个单链表的头指针又组成一个线个单链表的头指针又组成一个线性表，为了查找方便，使用数组加以存储。性表，为了查找方便，使用数组加以存储。性表，为了查找方便，使用数组加以存储。性表，为了查找方便，使用数组加以存储。#define MAXSIZE 50define MAXSIZE 50define MAXSIZE 50define MAXSIZE 50typedef typedef typedef typedef charcharcharchar datatype datatype datatype datatype;typedef struc

41、t chnodetypedef struct chnodetypedef struct chnodetypedef struct chnode /*/*/*/*孩子结点的类型孩子结点的类型孩子结点的类型孩子结点的类型*/*/*/*/intintintint child;child;child;child;struct chnode struct chnode struct chnode struct chnode *next;*next;*next;*next;chnode chnode chnode chnode,*,*,*,*chpoint chpoint chpoint chpoint;

42、typedef struct typedef struct typedef struct typedef struct /*/*/*/*树中每个结点的类型树中每个结点的类型树中每个结点的类型树中每个结点的类型*/*/*/*/datatypedatatypedatatypedatatype data;data;data;data;chpoint firstchild chpoint firstchild chpoint firstchild chpoint firstchild;/*;/*;/*;/*指向第一个子女的指针指向第一个子女的指针指向第一个子女的指针指向第一个子女的指针*/*/*/*/

43、node;node;node;node;typedef structtypedef structtypedef structtypedef struct /*/*/*/*树的类型树的类型树的类型树的类型*/*/*/*/nodenodenodenode treelist treelist treelist treelist MAXSIZE;MAXSIZE;MAXSIZE;MAXSIZE;int int int int length,rootlength,rootlength,rootlength,root；tree;tree;tree;tree;A AB BC CDDE EF FGGHHI IJ

44、 JK K012345678910child1 12 23 34 45 56 67 78 89 91010nextdatafirstchildtreelistrootroot 图图图图6.46.4中中中中(a)a)图的链表方式的孩子表示法图的链表方式的孩子表示法图的链表方式的孩子表示法图的链表方式的孩子表示法6.3.3 孩子兄弟表示法孩子兄弟表示法 所谓孩子兄弟表示法，即在存储树中每个结点所谓孩子兄弟表示法，即在存储树中每个结点所谓孩子兄弟表示法，即在存储树中每个结点所谓孩子兄弟表示法，即在存储树中每个结点时，除了包含该结点值域外，还设置两个指针域时，除了包含该结点值域外，还设置两个指针域时，

45、除了包含该结点值域外，还设置两个指针域时，除了包含该结点值域外，还设置两个指针域firstchildfirstchildfirstchildfirstchild和和和和rightsiblingrightsiblingrightsiblingrightsibling，分别指向该结点的第分别指向该结点的第分别指向该结点的第分别指向该结点的第一个子女和其右兄弟，即以二叉链表方式加以存储，一个子女和其右兄弟，即以二叉链表方式加以存储，一个子女和其右兄弟，即以二叉链表方式加以存储，一个子女和其右兄弟，即以二叉链表方式加以存储，因此该方法也常被称为二叉树表示法。因此该方法也常被称为二叉树表示法。因此该方法

46、也常被称为二叉树表示法。因此该方法也常被称为二叉树表示法。typedeftypedeftypedeftypedef char char char char datatype datatype datatype datatype;/*;/*;/*;/*树中结点值的类型树中结点值的类型树中结点值的类型树中结点值的类型*/*/*/*/typedef structtypedef structtypedef structtypedef struct node/*node/*node/*node/*树中每个结点的类型树中每个结点的类型树中每个结点的类型树中每个结点的类型*/*/*/*/datatypeda

47、tatypedatatypedatatype data;data;data;data;struct struct struct struct node *node *node *node *firstchild firstchild firstchild firstchild,*,*,*,*rightsiblingrightsiblingrightsiblingrightsibling;node,*node,*node,*node,*pnode pnode pnode pnode;pnode pnode pnode pnode root;/*root;/*root;/*root;/*指向树根结

48、点的指针指向树根结点的指针指向树根结点的指针指向树根结点的指针*/*/*/*/A AB BC C DDE E F F GGH H I I J J K K data firstchild rightsiblingroot 图图图图6.46.4中中中中(a)a)图的孩子兄弟表示法图的孩子兄弟表示法图的孩子兄弟表示法图的孩子兄弟表示法 6.4 6.4 树的遍历树的遍历 所谓所谓所谓所谓树的遍历树的遍历树的遍历树的遍历，指按某种规定的顺序访问树中，指按某种规定的顺序访问树中，指按某种规定的顺序访问树中，指按某种规定的顺序访问树中的每一个结点一次，且每个结点仅被访问一次。树的每一个结点一次，且每个结点仅

49、被访问一次。树的每一个结点一次，且每个结点仅被访问一次。树的每一个结点一次，且每个结点仅被访问一次。树的遍历方式分为以下三种：的遍历方式分为以下三种：的遍历方式分为以下三种：的遍历方式分为以下三种：（1 1 1 1）树的）树的）树的）树的前序遍历前序遍历前序遍历前序遍历：首先访问根结点，再依次按前：首先访问根结点，再依次按前：首先访问根结点，再依次按前：首先访问根结点，再依次按前序遍历的方式访问根结点的每一棵子树。序遍历的方式访问根结点的每一棵子树。序遍历的方式访问根结点的每一棵子树。序遍历的方式访问根结点的每一棵子树。（2 2 2 2）树的）树的）树的）树的后序遍历后序遍历后序遍历后序遍历：

50、首先按后序遍历的方式访问根：首先按后序遍历的方式访问根：首先按后序遍历的方式访问根：首先按后序遍历的方式访问根结点的每一棵子树，然后再访问根结点。结点的每一棵子树，然后再访问根结点。结点的每一棵子树，然后再访问根结点。结点的每一棵子树，然后再访问根结点。（3 3 3 3）树的）树的）树的）树的层次遍历层次遍历层次遍历层次遍历：首先访问第一层上的根结点，：首先访问第一层上的根结点，：首先访问第一层上的根结点，：首先访问第一层上的根结点，然后从左到右依次访问第二层上的所有结点，再以然后从左到右依次访问第二层上的所有结点，再以然后从左到右依次访问第二层上的所有结点，再以然后从左到右依次访问第二层上的