软件技术基础树.pptx

《软件技术基础树.pptx》由会员分享，可在线阅读，更多相关《软件技术基础树.pptx（135页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1赌王家族第1页/共135页6.1 树的基本概念树树(Tree)(Tree)是是n(nn(n 0 0)个结点的有限集合个结点的有限集合T T。若若n=0n=0时称为空树，否则：时称为空树，否则：(1)(1)有有且只有一个特殊且只有一个特殊的结点时称为的结点时称为树的根树的根(Root)(Root)结点结点；(2)(2)若若n1n1时，其余的结点被分为时，其余的结点被分为m(m0)m(m0)个个互不相交互不相交的子集的子集T T1 1,T,T2 2,T,T3 3TTmm，其中每个，其中每个子集本身又是一棵树，称其为子集本身又是一棵树，称其为根的子树根的子树(Subtree)(Subtree)。这

2、这是树的递归定义，即用树来定义树是树的递归定义，即用树来定义树，而只有一个结，而只有一个结点的树必定仅由根点的树必定仅由根组成。组成。2第2页/共135页 树的基本术语树的基本术语(1)(1)结点结点(node)(node)：包含包含一个数据元素一个数据元素及及若干指向其他结点的分支若干指向其他结点的分支信息信息。(2)(2)结点结点的度的度(degree)(degree)、树的度树的度：结点所拥有的：结点所拥有的子树的棵数子树的棵数称称为为结点的度结点的度。树中。树中结点度的最大值结点度的最大值称为称为树的度树的度。如如图图6-1(b)6-1(b)中结点中结点A A的度是的度是3 3，结点，

3、结点B B的度是的度是2 2，结点，结点MM的度是的度是0 0，树的树的度是度是3 3。A AA AB BD DC CE EGGF FHHI IMMJ JN NKKL L(a)(a)只有根结点只有根结点(b)(b)一般的树一般的树3 3图图6-1 6-1 树的示例形式树的示例形式第3页/共135页(3)(3)叶子叶子(left)(left)结点结点、非叶子非叶子结点结点树树中中度为度为0 0的的结点，即无后继的结点，称为结点，即无后继的结点，称为叶子结点叶子结点(或终端结点或终端结点)。度度不为不为0 0的结点称为的结点称为非叶子结点非叶子结点(或非终端结点或分支结点或非终端结点或分支结点)。

4、除根除根结点外，分支结点又称为内部结点。结点外，分支结点又称为内部结点。如如图中结点图中结点F F、HH、I I、J J、KK、L L、MM、N N是叶子是叶子结点，而所有其它结点都是分支结点。结点，而所有其它结点都是分支结点。4 4A AB BD DC CE EGGF FHHI IMMJ JN NKKL L第4页/共135页5(4)(4)孩子结点、双亲结点、兄弟孩子结点、双亲结点、兄弟结点结点一一个结点的个结点的直接后继直接后继称为该结点的称为该结点的孩子结点孩子结点(child)(child)或子结点或子结点；相应相应地，一个结点的地，一个结点的直接前趋直接前趋称为称为该结点的该结点的双亲

5、结点双亲结点(parent)(parent)或父结点或父结点。同同一双亲结点的所有子结点互称为一双亲结点的所有子结点互称为兄弟结点兄弟结点。如如图中图中结点结点B B、C C、D D是结点是结点A A的子结点，而结点的子结点，而结点A A是结点是结点B B、C C、D D的父结点；的父结点；类似地结点类似地结点E E、F F是结点是结点B B的子结点，结点的子结点，结点B B是结点是结点E E、F F的父结点。的父结点。如图中如图中结点结点B B、C C、D D是兄弟结点；结点是兄弟结点；结点E E、F F是兄弟结点。是兄弟结点。ABDCEGFHIMJNKL第5页/共135页（5 5）层次、堂

6、兄弟结点层次、堂兄弟结点规定规定树中树中根结点的层次为根结点的层次为1 1，其余结点的层次等于其双亲结点的，其余结点的层次等于其双亲结点的层次加层次加1 1。若若某结点在第某结点在第l l(l l 1 1)层，则其子结点在第层，则其子结点在第l l+1+1层。层。双亲双亲结点在同一层上的所有结点互称为结点在同一层上的所有结点互称为堂兄弟结点堂兄弟结点。如图如图6-1(b)6-1(b)中结点中结点E E、F F、GG、HH、I I、J J。（6 6）树的树的深度深度(或高度或高度)：树中结点的最大层次值，又称为树的深：树中结点的最大层次值，又称为树的深度，如图度，如图6-1(b)6-1(b)中树

7、的深度为中树的深度为4 4。6 6A AB BD DC CE EGGF FHHI IMMJ JN NKKL L第第1 1层层第第2 2层层第第3 3层层第第4 4层层第6页/共135页(7)结点的（层次）路径、祖先、子孙从从根结点开始，到达某结点根结点开始，到达某结点p p所经过的所有结点成为所经过的所有结点成为结点结点p p的的层次路径层次路径(有且只有一条有且只有一条)。结点结点p p的层次路径上的所有结点（的层次路径上的所有结点（p p除外）称为除外）称为p p的的祖先祖先。以以某一结点为根的子树中的任意结点称为该结点的某一结点为根的子树中的任意结点称为该结点的子孙子孙结结点点。7 7A

8、 AB BD DC CE EGGF FHHI IMMJ JN NKKL L第7页/共135页（8 8）有序）有序树和无序树和无序树树对于对于一棵树，若其中每一个结点的子树（若有）具有一定的次序，则该树称为一棵树，若其中每一个结点的子树（若有）具有一定的次序，则该树称为有序树有序树，否则称为，否则称为无序树无序树。例如例如：若若T1T1，T2T2为有序树，它们是两棵不同的树为有序树，它们是两棵不同的树；若若T1T1，T2T2为无序树，它们是两棵相同的树。为无序树，它们是两棵相同的树。A AC CB BA AB BC C8 8第8页/共135页（9）森林(forest)：m(m0)m(m0)棵互不

9、相交的树的集合。棵互不相交的树的集合。显然，若将一棵树的根结点删除，剩余的子树就构成了森林。显然，若将一棵树的根结点删除，剩余的子树就构成了森林。9 9A AB BD DC CE EGGF FHHI IMMJ JN NKKL L第9页/共135页10树的表示形式 倒悬倒悬树树。是最常用的表示形式，如图。是最常用的表示形式，如图6-1(b)6-1(b)。ABDCEGFHIMJNKL图6.1(b)一般的树圆圈表示结点，结圆圈表示结点，结点的名字可写在圆点的名字可写在圆圈内或圆圈旁圈内或圆圈旁。连线表连线表示结点之间示结点之间的关系的关系第10页/共135页11树的表示形式 嵌套嵌套集合集合:是是一

10、些集合的集体，对于任一些集合的集体，对于任何两个集合，何两个集合，或者不相交，或者一个集或者不相交，或者一个集合包含另一个集合合包含另一个集合。右图是。右图是图图6-1(b)6-1(b)树的树的嵌套集合形式嵌套集合形式。嵌套嵌套集合形式集合形式HIJDFBKLECM NGA 圆圈表示结点圆圈表示结点 圆圈的相互包含表示圆圈的相互包含表示结点之间的关系。结点之间的关系。ABDCEGFHIMJNKL图6.1(b)一般的树第11页/共135页12树的表示形式广义表形式(A(B,C,D)(A(B,C,D)(A(B(E,F),C(G),D(H,I,J)(A(B(E,F),C(G),D(H,I,J)(A(

11、B(E(K,L),F),C(G(M,N),D(H,I,J)(A(B(E(K,L),F),C(G(M,N),D(H,I,J)n n括号表示结点括号表示结点n n括号的相互包含表示结点间的关系。括号的相互包含表示结点间的关系。ABDCEGFHIMJNKL图6.1(b)一般的树第12页/共135页13树的表示形式 目录表示目录表示 凹入的线条表示结点凹入的线条表示结点 线条的长短表示结点间的关系，长线条的长短表示结点间的关系，长线条包含短线条。线条包含短线条。ABCDEFKLABDCEGFHIMJNKL图6.1(b)一般的树第13页/共135页1414树的存储结构树的存储结构 顺序存储顺序存储 顺序

12、存储时，首先必须对树形结构的结点进行某种方式的顺序存储时，首先必须对树形结构的结点进行某种方式的线性化线性化，使之成为一，使之成为一个线性序列，然后存储。个线性序列，然后存储。链式存储链式存储 链式存储时，链式存储时，使用多指针域的结点形式使用多指针域的结点形式，每一个指针域指向一棵子树的根结点。，每一个指针域指向一棵子树的根结点。由于由于树的树的分支数不固定分支数不固定，很难给出一种固定的存储结构，通常采用二叉树的形式存，很难给出一种固定的存储结构，通常采用二叉树的形式存储树。储树。第14页/共135页6.2 6.2 二叉树二叉树的定义及其的定义及其性质性质 二叉树的定义二叉树的定义 我们把

13、满足以下两个条件的树形结构叫做二叉树（我们把满足以下两个条件的树形结构叫做二叉树（binary treebinary tree）：）：（1 1）每个结点的度都）每个结点的度都不大于不大于2 2；（2 2）每个结点的孩子结点次序不能任意颠倒。）每个结点的孩子结点次序不能任意颠倒。由此定义可以看出，一个二叉树中的每个结点只能含有由此定义可以看出，一个二叉树中的每个结点只能含有0 0，1 1或或2 2个孩子，并且每个孩子个孩子，并且每个孩子有左右之分。有左右之分。位于左边的孩子叫做位于左边的孩子叫做左孩子左孩子 位于右边的孩子称为位于右边的孩子称为右孩子右孩子1515第15页/共135页二叉树的基本

14、形态二叉树的基本形态 二叉树有二叉树有5 5种基本形态，如图种基本形态，如图6-36-3所示。所示。A AA AA AA A(a)(a)(b)(b)(c)(c)(d)(d)(e)(e)(a)(a)空二叉树空二叉树(b)(b)单结点二叉树单结点二叉树(c)(c)右子树为空右子树为空(d)(d)左子树为空左子树为空(e)(e)左、右子树都不空左、右子树都不空图图6-3 6-3 二叉树的基本形态二叉树的基本形态1616第16页/共135页17二叉树与一般树型结构的主要区别 树形结构中使用的术语如父母（双亲或前件树形结构中使用的术语如父母（双亲或前件，前趋），前趋）、子女（后件，后继）、祖先、子女（后

15、件，后继）、祖先、子孙、兄弟和路径等在二叉树中仍然可以沿用，但值得注意的是，子孙、兄弟和路径等在二叉树中仍然可以沿用，但值得注意的是，二叉树并非一般树二叉树并非一般树形结构的特殊形式，它们属于两种不同的数据结构。形结构的特殊形式，它们属于两种不同的数据结构。二叉树二叉树与一般树型结构的主要区别在于与一般树型结构的主要区别在于：（1 1）二叉树中每个非空结点最多只有两个子女，而一般的）二叉树中每个非空结点最多只有两个子女，而一般的树形结构树形结构中每个非空结点可中每个非空结点可以有多个以有多个子女；子女；（2 2）二叉树中结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下）二叉树中结

16、点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出是左子树还是右子树。而树则不区分。也要明确指出是左子树还是右子树。而树则不区分。第17页/共135页二叉树与一般树型结构的主要区别 为什么说二叉树不等同于度为为什么说二叉树不等同于度为2 2的有序树？的有序树？答答：如果树的根结点只有一棵子树，那么对有序树而言，它就是一个：如果树的根结点只有一棵子树，那么对有序树而言，它就是一个“独生子独生子”，无次序可分，但，无次序可分，但对对二叉树而言，必须明确区分它是根的左子树还是根的右子树二叉树而言，必须明确区分它是根的左子树还是根的右子树，两种情况将构成不同的二叉树。，两种情况将

17、构成不同的二叉树。18第18页/共135页19 性质性质1 1：在非空二叉树中，第：在非空二叉树中，第i i层上至多有层上至多有2 2i-1i-1个结点个结点(i i11)。证明证明：用数学归纳法证明。：用数学归纳法证明。1.1.当当i=1i=1时时：只有一个根结点，：只有一个根结点，2 21 1-1-1=2=20 0=1=1，命题成立。，命题成立。2.2.现现假设对假设对i1i1时，处在时，处在第第i-1i-1层层上至多有上至多有2 2(i-1)(i-1)-1-1个结点。个结点。3.3.由由归纳假设知，第归纳假设知，第i-1i-1层上至多有层上至多有2 2i-2i-2个结点。由于二叉树每个结

18、点的度最大为个结点。由于二叉树每个结点的度最大为2 2，故在第故在第i i层上最大结点数为第层上最大结点数为第i-1i-1层上最大结点数的层上最大结点数的2 2倍。倍。即即 2222i-2i-22 2i-1i-1 证证毕毕二叉树的性质第19页/共135页20二叉树的性质 性质性质2 2：深度为：深度为k k的二叉树至多有的二叉树至多有2 2k k-1-1个结点（个结点（k1k1)。证明证明：深度为：深度为k k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和。的二叉树的最大的结点数为二叉树中每层上的最大结点数之和。由性质由性质1 1知知，二叉树的第，二叉树的第1 1层、第层、第2 2层层

19、 第第k k层上的结点数至多有：层上的结点数至多有：2 20 0、2 21 1 22k-1 k-1。总的结点数至多有：总的结点数至多有：2 20 0+2+21 1+2 2k-1k-1=2=2k k-1 -1 证毕证毕第20页/共135页21二叉树的性质性质3：对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。证明：证明：设二叉树中度为设二叉树中度为1 1的结点数为的结点数为n n1 1，二叉树中总结点数为，二叉树中总结点数为N N，因为二叉树中所有，因为二叉树中所有结点均小于或等于结点均小于或等于2 2，则有，则有：N=nN=n0 0+n+n1 1+n+n2 2设

20、设B B为二叉树中的分支总数为二叉树中的分支总数，除根结点外，其余每个结点都有唯一的一个进入分支除根结点外，其余每个结点都有唯一的一个进入分支,则则有：有：N=B+1N=B+1。二叉树二叉树中的中的分支都是分支都是由度为由度为1 1和和2 2的的结点发出结点发出，所以分支数目为：，所以分支数目为：B Bn n1 1+2+2 n n2 2 整理可得：整理可得：N=B+1=nN=B+1=n1 1+2+2 n n2 2+1+1 n n0 0+n+n1 1+n+n2 2=n=n1 1+2+2 n n2 2+1+1 即即 n n0 0=n=n2 2+1 +1 证证毕毕 第21页/共135页满二叉树 满二

21、叉树满二叉树一一棵深度为棵深度为k k且有且有2 2k k-1-1个结点的二叉树称为满二叉个结点的二叉树称为满二叉树树(Full Binary Tree)(Full Binary Tree)。如如图图6-4(a)6-4(a)就是一棵深度为就是一棵深度为4 4的满二叉树的满二叉树。22894101151213614157213图6-4(a)满二叉树第22页/共135页2323满二叉树 满满二叉树的特点二叉树的特点：基本基本特点是每一层上的结点数总是最大结点数。特点是每一层上的结点数总是最大结点数。满满二叉树的所有二叉树的所有的分支的分支结点都有左、右子树。结点都有左、右子树。可可对满二叉树的结点

22、进行连续编号，若规定从根结点开始，按对满二叉树的结点进行连续编号，若规定从根结点开始，按“自上而下、自自上而下、自左至右左至右”的原则进行的原则进行。图图6-4(a)6-4(a)中满二叉树的顺序表示为（中满二叉树的顺序表示为（1,2,3,4,5,6,7,1,2,3,4,5,6,7,14,1514,15）图图6-4(a6-4(a)满满二叉树二叉树8 89 94 4101011115 5121213136 6141415157 72 21 13 3第23页/共135页24完全二叉树 完全二叉树完全二叉树(Complete Binary Tree)(Complete Binary Tree)：如果如

23、果深度为深度为k k，由，由n n个结点的二叉树，个结点的二叉树，当且仅当其每一个当且仅当其每一个结点都与深度为结点都与深度为k k的满二叉树中编号从的满二叉树中编号从1 1到到n n的结点一一对的结点一一对应应，该二叉树称为完全二叉树。，该二叉树称为完全二叉树。或或深度为深度为k k的满二叉树中编号从的满二叉树中编号从1 1到到n n的前的前n n个结点构成了个结点构成了一棵深度为一棵深度为k k的完全的完全二叉树二叉树，其中其中 2 2k-1k-1 n2n2k k-1-1。完全完全二叉树是满二叉树的一部分，而满二叉树是完全二二叉树是满二叉树的一部分，而满二叉树是完全二叉树的特例叉树的特例。

24、894115211267310136245完全二叉树非完全二叉树5674213第24页/共135页25二叉树的性质 性质性质4 4：具有具有n n个结点的完全个结点的完全二叉树的深度二叉树的深度为为：2 2n n +1 1。其中 x 表示不大于x的最大整数，x 表示不小于x的最小整数。证明证明：假设假设n n个结点的完全个结点的完全二叉树的深度为二叉树的深度为k k 则则根据性质根据性质2 2，k-1k-1层满二叉树结点总数为：层满二叉树结点总数为：n n1 1=2=2k-1k-1-1-1；k k层层满二叉树结点总数为满二叉树结点总数为：n n2 2=2=2k k-1-1；显然显然n n1 1

25、nnnn2 2，进一步进一步n n1 1+1+1 nnnn2 2+1+1，即，即2 2 k-1k-1 n2n2k k 取取对数得：对数得：k-1k-1 2 2n nk 1i1，则序号为，则序号为i i的的结点的双亲结点序号结点的双亲结点序号是是 i/2i/2 。若若2i n2i n，则序号为，则序号为i i的结点无左孩子；的结点无左孩子；若若2in2in，则序号为，则序号为i i的结点的左孩子的序号为的结点的左孩子的序号为2i2i。若若2i+1n2i+1n，则序号为，则序号为i i的结点的结点无无右右孩子孩子；若若2i+1n2i+1n，则，则序号为序号为i i的结点的结点的右孩子的右孩子的序号

26、为的序号为2i+12i+1。第26页/共135页27 可以用归纳法证明其中的（可以用归纳法证明其中的（2 2）和（）和（3 3）：）：当当i=1i=1时，由完全二叉树的定义知，如果时，由完全二叉树的定义知，如果2i=22i=2nn，说明二叉树中存在两个或两，说明二叉树中存在两个或两个以上的结点，所以其左孩子存在且序号为个以上的结点，所以其左孩子存在且序号为2 2；反之，如果；反之，如果2i=2n2i=2n，说明二叉，说明二叉树中不存在序号为树中不存在序号为2 2的结点，其左孩子不存在的结点，其左孩子不存在。同理。同理，如果，如果2i+1=3 2i+1=3 nn，则说，则说明其右孩子存在且序号为

27、明其右孩子存在且序号为3 3，如果，如果2i+1=3 2i+1=3 nn，则二叉树中不存在序号为，则二叉树中不存在序号为3 3的结的结点，其右孩子不存在点，其右孩子不存在。现假设对于编号为现假设对于编号为j(1j(1 j i j i)的结点，的结点，(2)(2)和和(3)(3)成立。即：成立。即：当当 2j2j n n 时，其左时，其左 孩子编号是孩子编号是 2j2j；当；当 2jn2jn 时时，其左孩子不，其左孩子不 存在存在。当当 2j+12j+1 n n 时，其右时，其右 孩子编号是孩子编号是 2j+12j+1；当；当 2j+1n2j+1n 时时，其右孩子不，其右孩子不 存在存在。213

28、第27页/共135页2828 当当i=j+1i=j+1时，由完全二叉树的定义知，时，由完全二叉树的定义知，若其左孩子结点存在，则其左孩若其左孩子结点存在，则其左孩子结点的编号一定等于编号为子结点的编号一定等于编号为j j的右孩子的编号加的右孩子的编号加1 1，即其左孩子的编号，即其左孩子的编号为：为：(2j+1)+1=2(j+1)=2i(2j+1)+1=2(j+1)=2i 如如图图6-56-5所示，且有所示，且有2i2i n n。相反，若。相反，若2i2i n n，则左孩子结点不存在。，则左孩子结点不存在。同样地，若序号为同样地，若序号为i i的结点的右孩子结点存在，则其右孩子的编号为：的结点

29、的右孩子结点存在，则其右孩子的编号为：2i+12i+1，且有，且有2i+12i+1 n n。相反，若。相反，若2i+12i+1 n n，则左孩子结点不存在。结论，则左孩子结点不存在。结论(2)(2)和和(3)(3)得证。得证。j jj+1j+12j2j2j+12j+12j+22j+22j+32j+3 j/2j/2(a)(a)j j和和j+1j+1结点在同一层结点在同一层j+1j+12j+22j+22j+32j+3j j2j2j2j+12j+1(b)i(b)i和和i+1i+1结点不在同一层结点不在同一层图图6-5 6-5 完全二叉树中结点完全二叉树中结点i i和和i+1i+1的左右孩子的左右孩子

30、第28页/共135页29 再由再由(2)(2)和和(3)(3)来证明来证明(1)(1)。当当i=1i=1时，显然编号为时，显然编号为1 1的是根结点，无双亲结的是根结点，无双亲结点。点。当当i1i1时，设编号为时，设编号为i i的结点的双亲结点的编号为的结点的双亲结点的编号为mm，若编号为若编号为i i的结点是其双亲结点的左孩子，则由的结点是其双亲结点的左孩子，则由(2)(2)有：有：i=2m i=2m，即，即m=m=i/2i/2 ；若编号为若编号为i i的结点是其双亲结点的右孩子，则由的结点是其双亲结点的右孩子，则由(3)(3)有：有：i=2m+1 i=2m+1，即，即m=m=(i-1i-1

31、)/2/2 ；当当i1i1时，其双亲结点的编号为时，其双亲结点的编号为 i/2i/2 。证证毕毕第29页/共135页二叉树的存储结构1 顺序存储结构 顺序存储时，首先必须对树形结构的结点进行某种方式的顺序存储时，首先必须对树形结构的结点进行某种方式的线性化，使之成为一线性化，使之成为一个线性序列，然后存储个线性序列，然后存储。这种存储结构适用于完全二叉树这种存储结构适用于完全二叉树。用用一组地址连续的存储单元一组地址连续的存储单元依次依次“自上而下自上而下、自左至右自左至右”存储完全二叉树的数存储完全二叉树的数据元素据元素。30第30页/共135页3131n n对于完全二叉树上编号为对于完全二

32、叉树上编号为i i的结点元素存储在一维数组的下标值为的结点元素存储在一维数组的下标值为i-1i-1的分量中，的分量中，如如图图(c)c)所示。所示。n n对于一般的二叉树，将其每个结点与完全二叉树上的结点相对照，存储在一对于一般的二叉树，将其每个结点与完全二叉树上的结点相对照，存储在一维数组中，如维数组中，如图图(d d)所示。所示。a ab bc cd dh hi ie ej jk kl lf fg g(a)(a)完全二叉树完全二叉树(b)(b)非完全二叉树非完全二叉树a ab bc cd de ef fg gh h1 1 2 2 3 3 4 5 4 5 6 7 6 7 8 9 8 9 10

33、 10 11 1211 12 a a b b c d c d e e f f g g h i h i j j k lk l (c)(c)完全二叉树的顺序存储形式完全二叉树的顺序存储形式1 1 2 3 2 3 4 5 6 4 5 6 7 7 8 9 8 9 10 1110 11a a b b c c d d e e h h f f g g(d)(d)非完全二叉树的顺序存储形式非完全二叉树的顺序存储形式第31页/共135页二叉树的顺序存储结构二叉树的顺序存储结构 利用以上表示方法，可以给出一般二叉树的顺序存储结构的利用以上表示方法，可以给出一般二叉树的顺序存储结构的C C语言描述如下语言描述如下：

34、#define#definemaxsize 1024;maxsize 1024;typedeftypedefintintdatatype;datatype;typedeftypedefstructstruct datatype datamaxsize;datatype datamaxsize;/存放二叉树的向量存放二叉树的向量 intintlast;last;/最后一个结点的下标最后一个结点的下标sequenlist;sequenlist;3232第32页/共135页二叉树的存储二叉树的存储结构：顺序存储结构结构：顺序存储结构 最坏最坏的情况的情况下，下，一个深度为一个深度为k k、且、且只有

35、只有k k个结点个结点的、的、单支二叉树单支二叉树 需要需要长度为长度为2 2k k-1-1的的一维数组。一维数组。D DC CA AB B3333ABCD第33页/共135页34链式存储结构2 2 链式存储结构链式存储结构 设计不同的结点结构可构成不同的链式存储结构设计不同的结点结构可构成不同的链式存储结构。(1)(1)结点的类型及其定义结点的类型及其定义 二叉链表结点二叉链表结点。有三个域：一个数据域，两个分别指向左右子结点的指针域，如图。有三个域：一个数据域，两个分别指向左右子结点的指针域，如图6-7(a)6-7(a)所示。所示。typedef char datatypetypedef

36、char datatype；typedef structtypedef struct node node datatype datatype datadata；struct struct node *lchildnode *lchild，*rchildrchild；bitree bitree；bitree *root;bitree *root;/指向根结点的头指向根结点的头指针指针 当二叉树为空时，则当二叉树为空时，则root=NULLroot=NULL。若结点的某个孩子不存在，则相应的指针域为空。若结点的某个孩子不存在，则相应的指针域为空。二叉二叉链表中，如果有链表中，如果有n n个结点，则

37、有个结点，则有n+1n+1个指针域为空。个指针域为空。第34页/共135页3535链式存储结构 三叉链表结点三叉链表结点。除二叉链表的三个域外，再增。除二叉链表的三个域外，再增加一个指针域，用来指向结点的父结点，如图加一个指针域，用来指向结点的父结点，如图6-6-7(b)7(b)所示。所示。typedef typedef struct struct BTNode3BTNode3 datatype datatype data;data;struct BTNode3 *lchild struct BTNode3 *lchild,*rchild*rchild,*parent*parent;BTNod

38、e3 BTNode3;lchild data rchildlchild data rchildlchild lchild data data rchild parent rchild parent(a)(a)二叉链表结点二叉链表结点(b)(b)三叉链表结点三叉链表结点图图6-7 6-7 链表结点结构形式链表结点结构形式第35页/共135页3636链式存储结构(2)二叉树的链式存储形式 例有一棵一般的二叉树，如图例有一棵一般的二叉树，如图6-8(a)6-8(a)所示。以二叉链表和三叉链表方式存储的结构图所示。以二叉链表和三叉链表方式存储的结构图分别如图分别如图6-8(b)6-8(b)、6-8(c

39、)6-8(c)所示。所示。图图6-8 6-8 二叉树及其链式存储结构二叉树及其链式存储结构(a)(a)二叉树二叉树a af fe ed dc cb bg g(c)(c)三叉链表三叉链表 a a b b c c d d e e f f g g (b)(b)二叉链表二叉链表 a a b b c c d d e e g g f f 第36页/共135页37二叉树建立（二叉链表的建立）算法算法的基本思想的基本思想 1 1）按照按照结点的序号结点的序号，依次输入结点信息，依次输入结点信息，若，若输入的结点输入的结点不是虚结点，则不是虚结点，则建立一个新结点建立一个新结点。2 2）若）若新结点是第新结点是

40、第1 1个结点，则令其为根结点个结点，则令其为根结点，否则，否则将新结将新结点作为孩子链接到它的双亲结点上点作为孩子链接到它的双亲结点上。3 3）如此）如此反复进行，直到输入结束标志反复进行，直到输入结束标志“”为止。为止。adcb输入 abcd#输入：按照二叉树的层次顺序依次输入结点信息第37页/共135页38二叉树建立（二叉链表的建立）adcb输入 a b c d#01234队列q：rearfrontschsch?=chq1.data=aq1.lchild=q1.rchild=rootrearrearq2.data=bq2.lchild=q2.rchild=q1.lchild=schchr

41、earq3.data=cq3.lchild=q3.rchild=q1.rchild=sfrontchrearq4=q2.lchild=s第38页/共135页二叉树的建立二叉树的建立算法算法 bitree bitree*CREATREE()*CREATREE()/*/*建立二叉树函数，函数返回指向根结点的指针建立二叉树函数，函数返回指向根结点的指针*/char char chch；/*/*结点信息变量结点信息变量*/bitree bitree*Q maxsize*Q maxsize;/设置指针类型数组来构成队列设置指针类型数组来构成队列 intintfront,front,rear;rear;/

42、*/*队头和队尾指针变量队头和队尾指针变量*/bitree *root,*bitree *root,*s;s;/*/*根结点指针和中间指针变量根结点指针和中间指针变量*/root=NULL;root=NULL;/*/*二叉树置空二叉树置空*/front=1 front=1;rear=0;rear=0;/*/*设置队列指针变量初值设置队列指针变量初值 ，向量下标为向量下标为0 0的空间未使用的空间未使用*/*/*以上为初始化以上为初始化*/3939第39页/共135页while(ch=getchar()!=#)while(ch=getchar()!=#)/*/*输入一个字符，当不是结束符时执行以

43、下操作输入一个字符，当不是结束符时执行以下操作*/s=NULL;s=NULL;if(ch!=)if(ch!=)/*/*表示虚结点，当不是虚结点则建立新结点表示虚结点，当不是虚结点则建立新结点*/s s=(bitree=(bitree*)malloc(sizeof)malloc(sizeof(bitree);(bitree);s-data=chs-data=ch;s-lchild=NULLs-lchild=NULL;s-rchild=NULLs-rchild=NULL;rear+;rear+;/*/*队尾指针增队尾指针增1 1，指向新结点地址应存放的单元，指向新结点地址应存放的单元*/Qrear

44、=s;Qrear=s;/*/*将新结点地址入队或虚结点指针将新结点地址入队或虚结点指针NULLNULL入队入队*/if(rearif(rear=1)root=s;1)root=s;/*/*输入的第一个结点作为根结点输入的第一个结点作为根结点*/else else if(s&Qfront)if(s&Qfront)/*/*孩子和双亲结点都不是虚结点孩子和双亲结点都不是虚结点*/if(rear%2=0)Qfrontif(rear%2=0)Qfront-lchild=s-lchild=s;/*/*新结点是左孩子新结点是左孩子*/else else QfrontQfront-rchild=s;-rchi

45、ld=s;/*/*新结点是右孩子新结点是右孩子*/if if(rear%2=1)(rear%2=1)front+;front+;/*/*结点结点*QfrontQfront的两个孩子处理完毕，出队列的两个孩子处理完毕，出队列*/return root;return root;/*/*返回根指针返回根指针*/*CREATREE */*CREATREE */4040第40页/共135页6.3 6.3 遍历遍历二叉树及其应用二叉树及其应用 遍历二叉树遍历二叉树(Traversing Binary Tree)(Traversing Binary Tree)：是指按指定的规律对二叉树中的每个结点访问是指按

46、指定的规律对二叉树中的每个结点访问一次且仅访问一次一次且仅访问一次。所谓所谓访问访问是指对结点做某种处理。如：输出信息、修改结点的值等是指对结点做某种处理。如：输出信息、修改结点的值等。为什么需要遍历二叉树？为什么需要遍历二叉树？二叉树二叉树是一种非线性结构是一种非线性结构，通过遍历将二叉树中的结点访问一，通过遍历将二叉树中的结点访问一遍，得到访问结点的顺序序列，故遍历的目的在于遍，得到访问结点的顺序序列，故遍历的目的在于将非线性化结构变成线性化的访问序将非线性化结构变成线性化的访问序列列。遍历方式：遍历方式：深度优先遍历深度优先遍历 广度优先遍历广度优先遍历4141第41页/共135页424

47、2深度优先遍历二叉树深度优先遍历二叉树 若以若以L L、D D、R R分别表示遍历左子树、遍历根结点和分别表示遍历左子树、遍历根结点和遍历右子树，则有六种遍历方案：遍历右子树，则有六种遍历方案：DLRDLR、LDRLDR、LRDLRD、DRLDRL、RDLRDL、RLDRLD。若若规定先左后右规定先左后右，则只有前三种情况三种情况，分别，则只有前三种情况三种情况，分别是：是：DLRDLR先先(根根)序遍历。序遍历。LDRLDR中中(根根)序遍历。序遍历。LRDLRD后后(根根)序遍历序遍历。对于对于二叉树的遍历，分别讨论递归遍历算法和非递二叉树的遍历，分别讨论递归遍历算法和非递归遍历算法。递归

48、遍历算法具有非常清晰的结构，但归遍历算法。递归遍历算法具有非常清晰的结构，但初学者往往难以接受或怀疑，不敢使用。实际上，初学者往往难以接受或怀疑，不敢使用。实际上，递递归算法是由系统通过归算法是由系统通过使用栈使用栈来实现控制的来实现控制的。而。而非递归非递归算法中的控制是由设计者定义和算法中的控制是由设计者定义和使用栈使用栈来实现的来实现的。DataLchildRchild二叉树结点的基本结构二叉树结点的基本结构第42页/共135页4343中序遍历二叉树中序遍历二叉树 算法算法6.3 6.3 中序遍历算法中序遍历算法。void void inorder(bitree*p)inorder(bi

49、tree*p)/中序遍历二叉树，中序遍历二叉树，p p指向二叉树的根指向二叉树的根结点结点 if if(p!=NULL)(p!=NULL)/二叉树二叉树p p非空，则执行以下操作非空，则执行以下操作 inorder inorder(p-lchild);(p-lchild);/中序遍历左子树中序遍历左子树 printf printf(“%c”,p-data);(“%c”,p-data);/访问访问p p所指结点所指结点 inorder inorder(p-rchild);(p-rchild);/中序遍历右子树中序遍历右子树 n中序遍历的过程：中序遍历的过程：1.从二叉树的根结点开始，从二叉树的根

50、结点开始，向树的左下方移动向树的左下方移动，直到遇，直到遇到空结点为止。到空结点为止。2.然后然后访问空结点的父结点访问空结点的父结点。3.接着继续遍历该结点的右子树，如果右子树没有子树接着继续遍历该结点的右子树，如果右子树没有子树可以遍历，那么继续遍历上一层最后一个未被访问的可以遍历，那么继续遍历上一层最后一个未被访问的结点。结点。第43页/共135页4444中序遍历中序遍历结果结果A/B*C*D+EA/B*C*D+E“表达式的中缀形式表达式的中缀形式”调用inorder根结点的值动作1+2*3*4/5A A6NULLNULL5A Aprintf7NULLNULL4/printf8B B9N