软件技术基础9-12树

《软件技术基础9-12树》由会员分享，可在线阅读，更多相关《软件技术基础9-12树（136页珍藏版）》请在金锄头文库上搜索。

1、树软件技术基础（五）西安电子科技大学 电子工程学院 林杰1本章要求1.基本要求 （1）掌握掌握树的术语，熟练掌握熟练掌握二叉树的基本概念和性质；掌握掌握 树、森林与二叉树之间的转换方法；掌握掌握二叉树的顺序、链式存 储结构以及类型定义；掌握掌握建立链式存储结构的二叉树的算法。 （2）熟练掌握熟练掌握二叉树的深度优先递归遍历算法及应用，了解广 度优先遍历的方法；了解由遍历序列恢复二叉树的方法；了解线 索二叉树的概念。 （3）掌握掌握哈夫曼树的概念和构造方法，了解哈夫曼编码的概 念。 （4）掌握掌握二叉排序树的概念和构造二叉排序树的方法，了解删 除结点的方法，了解在哪些方面可以应用二叉排序树。 2

2、.重点、难点 重点：二叉树的性质，建立和遍历二叉树的算法及遍历算法的应 用。哈夫曼树的概念、构造及应用。二叉排序树的概念和构造方 法。 难点：二叉树的建立算法，遍历算法的应用，构造哈夫曼编码， 二叉排序树中删除结点的方法。23赌王家族6.1 树的基本概念 树树(Tree)(Tree)是是n(nn(n 0 0) )个结点的有限集合个结点的有限集合T T。 若若n=0n=0时称为空树，否则：时称为空树，否则：(1)(1)有有且只有一个特殊且只有一个特殊的结点时称为的结点时称为树的根树的根(Root)(Root)结点结点；(2)(2)若若n1n1时，其余的结点被分为时，其余的结点被分为m(m0)m(

3、m0)个个互不相交互不相交的的子集子集T T1 1, T, T2 2, T, T3 3TTmm，其中每个子集本身又是一棵树，其中每个子集本身又是一棵树，称其为称其为根的子树根的子树( (SubtreeSubtree) )。这这是树的递归定义，即用树来定义树是树的递归定义，即用树来定义树，而只有一个结点，而只有一个结点 的树必定仅由根的树必定仅由根组成。组成。4 树的基本术语树的基本术语 (1)(1)结点结点(node)(node)：包含包含一个数据元素一个数据元素及及若干指向其他结点的若干指向其他结点的 分支信息分支信息。 (2)(2)结点结点的度的度(degree)(degree) 、树的度

4、树的度：结点所拥有的：结点所拥有的子树的棵数子树的棵数 称为称为结点的度结点的度。树中。树中结点度的最大值结点度的最大值称为称为树的度树的度。 如如图图6-1(b)6-1(b)中结点中结点A A的度是的度是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) 一般的一般的树树树树5 5图图6-1 6-1 树的示例形式树的示例形式(3)(3) 叶子叶子(left)(left)结点结点、非叶子非叶子结点结点

5、树树中中度为度为0 0的的结点，即无后继的结点，称为结点，即无后继的结点，称为叶子结点叶子结点( (或或 终端结点终端结点) )。度度不为不为0 0的结点称为的结点称为非叶子结点非叶子结点( (或非终端结点或分支结或非终端结点或分支结 点点) )。除根除根结点外，分支结点又称为内部结点。结点外，分支结点又称为内部结点。如如图中结点图中结点F F、HH、I I、J J、KK、L L、MM、N N是叶子结点，是叶子结点， 而所有其它结点都是分支结点。而所有其它结点都是分支结点。6 6A AB BD DC CE EGGF FHHI IMMJ JN NKKL L7(4)(4) 孩子结点、双亲结点、兄弟

6、孩子结点、双亲结点、兄弟结点结点 一一个结点的个结点的直接后继直接后继称为该结点的称为该结点的孩子结点孩子结点(child)(child)或子结点或子结点； 相应相应地，一个结点的地，一个结点的直接前趋直接前趋称为称为该结点的该结点的双亲结点双亲结点(parent)(parent) 或父结点或父结点。 同同一双亲结点的所有子结点互称为一双亲结点的所有子结点互称为兄弟结点兄弟结点。如如图中图中结点结点B B 、C C、D D是结点是结点A A的子结点，而结点的子结点，而结点A A是结点是结点B B 、C C、D D的父结点的父结点 ；类似地结点；类似地结点E E 、F F是结点是结点B B的子结

7、点，结点的子结点，结点B B是结点是结点E E 、F F的父结点。的父结点。如图中如图中结点结点B B 、C C、D D是兄弟结点；结点是兄弟结点；结点E E 、F F是兄弟结点。是兄弟结点。ABDCEGFHIMJNKL（5 5） 层次、堂兄弟结点层次、堂兄弟结点 规定规定树中树中根结点的层次为根结点的层次为1 1，其余结点的层次等于其双亲结点的，其余结点的层次等于其双亲结点的 层次加层次加1 1。 若若某结点在第某结点在第l l ( (l l 1 1) )层，则其子结点在第层，则其子结点在第l l+1+1层。层。 双亲双亲结点在同一层上的所有结点互称为结点在同一层上的所有结点互称为堂兄弟结点

8、堂兄弟结点。如图如图6-1(b)6-1(b) 中结点中结点E E、F F、GG、HH、I I、J J。 （6 6）树的树的深度深度( (或高度或高度) )：树中结点的最大层次值，又称为树的：树中结点的最大层次值，又称为树的 深度，如图深度，如图6-1(b)6-1(b)中树的深度为中树的深度为4 4。8 8A AB BD DC CE EGGF FHHI IMMJ JN NKKL L第第1 1层层第第2 2层层第第3 3层层第第4 4层层(7)(7)结点的（层次）路径结点的（层次）路径、祖先、祖先、子孙子孙 从从根结点开始，到达某结点根结点开始，到达某结点p p所经过的所有结点成为所经过的所有结点

9、成为结结 点点p p的的层次路径层次路径( (有且只有一条有且只有一条) )。 结点结点p p的层次路径上的所有结点（的层次路径上的所有结点（p p除外）称为除外）称为p p的的祖祖 先先。 以以某一结点为根的子树中的任意结点称为该结点的某一结点为根的子树中的任意结点称为该结点的子孙子孙 结点结点。9 9A AB BD DC CE EGGF FHHI IMMJ JN NKKL L（8 8）有序）有序树和无序树和无序树树 对于对于一棵树，若其中每一个结点的子树（若有）具有一定的次一棵树，若其中每一个结点的子树（若有）具有一定的次 序，则该树称为序，则该树称为有序树有序树，否则称为，否则称为无序树

10、无序树。例如例如： 若若T1T1，T2T2为有序树，它们是两棵不同的树为有序树，它们是两棵不同的树； 若若T1T1，T2T2为无序树，它们是两棵相同的树。为无序树，它们是两棵相同的树。 A AC CB BA AB BC C1010（9 9）森林）森林(forest)(forest)：m(m0)m(m0)棵互不相交的树的集合。棵互不相交的树的集合。显然，若将一棵树的根结点删除，剩余的子树就构显然，若将一棵树的根结点删除，剩余的子树就构 成了森林。成了森林。1111A AB BD DC CE EGGF FHHI IMMJ JN NKKL L12树的表示形式 倒悬倒悬树树。是最常用的表示形式，如图。

11、是最常用的表示形式，如图6-1(b)6-1(b)。ABDCEGFHIMJNKL图6.1 (b) 一般的树 圆圆圆圆圈表示圈表示结结结结点，点，结结结结点的名字可写在点的名字可写在圆圆圆圆圈内或圈内或圆圆圆圆圈圈旁旁。 连线连线连线连线 表表示示结结结结点之点之间间间间的关系的关系13树的表示形式 嵌套嵌套集合集合: : 是是一些集合的一些集合的 集体，对于任何两个集合集体，对于任何两个集合 ，或者不相交，或者一个或者不相交，或者一个 集合包含另一个集合集合包含另一个集合。右。右 图是图是图图6-1(b)6-1(b)树的嵌套集合树的嵌套集合 形式形式。嵌套嵌套集合形式集合形式HI JDFB KL

12、ECM NGA 圆圆圆圆圈表示圈表示结结结结点点 圆圆圆圆圈的相互包含表示圈的相互包含表示结结结结点之点之间间间间的关系。的关系。ABDCEGFHIMJNKL图6.1 (b) 一般的树14树的表示形式 广义广义表表形式形式 (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(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 括号的相互包含表示括号的相互包含表示结结结结点点间间间间的关的关系。系。

13、ABDCEGFHIMJNKL图6.1 (b) 一般的树15树的表示形式 目录表示目录表示 凹入的凹入的线线线线条表示条表示结结结结点点 线线线线条的条的长长长长短表示短表示结结结结点点间间间间的关系，的关系，长长长长 线线线线条包含短条包含短线线线线条。条。A BCDEFK LABDCEGFHIMJNKL图6.1 (b) 一般的树1616树的存储结构树的存储结构 顺序存储顺序存储 顺序存储时，首先必须对树形结构的结点进行某顺序存储时，首先必须对树形结构的结点进行某 种方式的种方式的线性化线性化，使之成为一个线性序列，然后，使之成为一个线性序列，然后 存储。存储。 链式存储链式存储 链式存储时，

14、链式存储时，使用多指针域的结点形式使用多指针域的结点形式，每一个，每一个 指针域指向一棵子树的根结点。指针域指向一棵子树的根结点。 由于由于树的树的分支数不固定分支数不固定，很难给出一种固定，很难给出一种固定 的存储结构，通常采用二叉树的形式存储的存储结构，通常采用二叉树的形式存储 树。树。6.2 6.2 二叉树二叉树的定义及其的定义及其性质性质 二叉树的定义二叉树的定义我们把满足以下两个条件的树形结构叫做二叉我们把满足以下两个条件的树形结构叫做二叉 树（树（binary treebinary tree）：）： （1 1）每个结点的度都）每个结点的度都不大于不大于2 2； （2 2）每个结点的

15、孩子结点次序不能任意颠倒。）每个结点的孩子结点次序不能任意颠倒。 由此定义可以看出，一个二叉树中的每个结点只由此定义可以看出，一个二叉树中的每个结点只 能含有能含有0 0，1 1或或2 2个孩子，并且每个孩子有左右之个孩子，并且每个孩子有左右之 分。分。 位于左边的孩子叫做位于左边的孩子叫做左孩子左孩子位于右边的孩子称为位于右边的孩子称为右孩子右孩子1717二叉树的基本形态二叉树的基本形态 二叉树有二叉树有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 二叉树的基本形态二叉树的基本形态181819二叉树与一般树型结构的主要区别 树形结构中使用的术语如父母（双亲或前件树形结构中使用的术语如父母（双亲或前件，前，前 趋）趋）、子女（后件，后继）、祖先、子孙、兄弟、子女（后件，后继）、祖先、子孙、兄弟 和路径等在二叉树中仍然可以沿用，但值得注意和路径等在二叉树中仍然可以沿用，但值得注意 的是，的是，二叉树并非一般树形结构的特殊形式，它二叉