《南开大学 数据结构Week9 树与二叉树》由会员分享，可在线阅读，更多相关《南开大学 数据结构Week9 树与二叉树（33页珍藏版）》请在金锄头文库上搜索。
1、http:/树和二叉树树和二叉树树型结构是一类非常重要的非线性结构。直观 地，树型结构是树型结构是一类非常重要的非线性结构。直观 地，树型结构是以分支关系定义的层次结构以分支关系定义的层次结构。树在计算机领域中也有着广泛的应用，例如在 编译程序中，用树来表示源程序的语法结构；在数据库 系统中，可用树来组织信息；在分析算法的行为时，可 用树来描述其执行过程等等。本章将详细讨论树和二叉树数据结构，主要介 绍树和二叉树的概念、术语，二叉树的遍历算法。树和 二叉树的各种存储结构以及建立在各种存储结构上的操 作及应用等。树在计算机领域中也有着广泛的应用，例如在 编译程序中，用树来表示源程序的语法结构；在
2、数据库 系统中，可用树来组织信息；在分析算法的行为时，可 用树来描述其执行过程等等。本章将详细讨论树和二叉树数据结构，主要介 绍树和二叉树的概念、术语，二叉树的遍历算法。树和 二叉树的各种存储结构以及建立在各种存储结构上的操 作及应用等。http:/树的基本概念树的基本概念1 树的定义树的定义 树树(Tree)是是n(n0)个结点的有限集合个结点的有限集合T，若，若n=0 时称为空树，否则：时称为空树，否则： 有且只有一个特殊的称为树的根有且只有一个特殊的称为树的根(Root)结点；结点； 若若n1时，其余的结点被分为时，其余的结点被分为m(m0)个个互不相交互不相交的子集的子集 T1, T2
3、, T3Tm，其中每个子集本身又是一棵树，称其为根的 子树，其中每个子集本身又是一棵树，称其为根的 子树(Subtree)。 这是树的递归定义，即用树来定义树，而只有一个 结点的树必定仅由根组成。这是树的递归定义，即用树来定义树，而只有一个 结点的树必定仅由根组成。树的定义和基本术语树的定义和基本术语http:/2 树的基本术语树的基本术语 结点结点(node)：一个数据元素及其若干指向其子树的分支。：一个数据元素及其若干指向其子树的分支。 结点的度结点的度(degree) 、树的度树的度：结点所拥有的子树的棵数称 为：结点所拥有的子树的棵数称 为结点的度结点的度。树中结点度的最大值称为。树中
4、结点度的最大值称为树的度树的度。树的示例形式AABDCEGFHIMJNKL(a)只有根结点(b)一般的树A的度是3 B的度是2 K的度是0A的度是3 B的度是2 K的度是0树的度是3 http:/ 叶子叶子(leaf)结点结点、非叶子结点非叶子结点：树中：树中度为度为0的结点称为的结点称为叶子 结点叶子 结点(或(或终端结点终端结点)。相对应地，)。相对应地，度不为度不为0的结点称为的结点称为非叶子结 点非叶子结 点(或或非终端结点非终端结点或或分支结点分支结点)。除根结点外，分支结点又称为)。除根结点外，分支结点又称为 内部结点内部结点。结点。结点H、I、J、K、L、M、N是叶子结点，而所有
5、其它结 点都是分支结点。是叶子结点，而所有其它结 点都是分支结点。 孩子结点孩子结点、双亲结点双亲结点、兄弟结点兄弟结点一个结点的一个结点的子树的根子树的根称为该结点的称为该结点的孩子结点孩子结点(child)或子结点； 相应地，该结点是其孩子结点的或子结点； 相应地，该结点是其孩子结点的双亲结点双亲结点(parent)或父结点。或父结点。http:/ 结点结点B 、C、D是结点是结点A的子结点，而结点的子结点，而结点A是结点是结点B 、C、D的父 结点；类似地结点的父 结点；类似地结点E 、F是结点是结点B的子结点，结点的子结点，结点B是结点是结点E 、F 的父结点。同一双亲结点的所有子结点
6、互称为的父结点。同一双亲结点的所有子结点互称为兄弟结点兄弟结点。结点。结点B 、C、D是兄弟结点；结点是兄弟结点；结点E 、F是兄弟结点。是兄弟结点。 层次、堂兄弟结点层次、堂兄弟结点规定树中根结点的层次为规定树中根结点的层次为1，其余结点的层次等于其双亲结 点的层次加，其余结点的层次等于其双亲结 点的层次加1。若某结点在第。若某结点在第l(l1)层，则其子结点在第层，则其子结点在第l+1层。双亲结点在同一层上的所有结点互称为层。双亲结点在同一层上的所有结点互称为堂兄弟结点堂兄弟结点。结点。结点E、 F、G、H、I、J。http:/ 结点的层次路径、祖先、子孙结点的层次路径、祖先、子孙从根结点
7、开始，到达某结点从根结点开始，到达某结点p所经过的所有结点成为结点所经过的所有结点成为结点p的的 层次路径层次路径(有且只有一条)。结点(有且只有一条)。结点p的层次路径上的所有结点（的层次路径上的所有结点（p除外）称为除外）称为p的的祖先祖先 (ancester) 。以某一结点为根的子树中的任意结点称为该结点的。以某一结点为根的子树中的任意结点称为该结点的子孙结点子孙结点 (descent)。 树的深度树的深度(depth)：树中结点的最大层次值，又称为树的高 度。：树中结点的最大层次值，又称为树的高 度。 有序树和无序树有序树和无序树：对于一棵树，若其中每一个结点的子树 （若有）具有一定的
8、次序，则该树称为对于一棵树，若其中每一个结点的子树 （若有）具有一定的次序，则该树称为有序树有序树，否则称为，否则称为无 序树无 序树。http:/ 森林森林(forest)：是是m(m0)棵互不相交的树的集合。显然， 若将一棵树的根结点删除，剩余的子树就构成了森林。棵互不相交的树的集合。显然， 若将一棵树的根结点删除，剩余的子树就构成了森林。3 树的表示形式树的表示形式 倒悬树倒悬树。是最常用的表示形式。是最常用的表示形式。 嵌套集合嵌套集合。是一些集合的集体，对于任何两个集合，或者 不相交，或者一个集合包含另一个集合。是一些集合的集体，对于任何两个集合，或者 不相交，或者一个集合包含另一个
9、集合。 广义表形式广义表形式。图。图6-2(b)是树的广义表形式。是树的广义表形式。 凹入法表示形式凹入法表示形式。树的表示方法的多样化说明了树结构的重要性。树的表示方法的多样化说明了树结构的重要性。http:/树的表示形式(a)嵌套集合嵌套集合形式(b) 广义表广义表形式(A(B(E(K,L),F),C(G(M,N),D(H,I,J)HIJDFBKLECMNGA树的抽象数据类型定义树的抽象数据类型定义ADT Tree数据对象D：D是具有相同数据类型的数据元素的集合。数据关系R：若D为空集，则称为空树；基本操作：CreateTree()ClearTree() ADT Tree /见数据结构P1
10、19二叉树二叉树 二叉树的定义二叉树的定义 1二叉树的定义二叉树的定义二叉树二叉树(Binary tree)是是n(n0)个结点的有限集合。 若个结点的有限集合。 若n=0时称为空树，否则：时称为空树，否则： 有且只有一个特殊的称为树的根有且只有一个特殊的称为树的根(Root)结点；结点； 若若n1时，其余的结点被分成为时，其余的结点被分成为二个互不相交的二个互不相交的子集子集T1,T2， 分别称之为左， 分别称之为左、右子树，并且左右子树，并且左、右子树又都是二叉树。右子树又都是二叉树。由此可知，二叉树的由此可知，二叉树的定义是递归定义是递归的。的。二叉树在树结构中起着非常重要的作用。因为二
11、叉树结构 简单，存储效率高，树的操作算法相对简单，且任何树都很容 易转化成二叉树结构。上节中引入的有关树的术语也都适用于 二叉树。二叉树在树结构中起着非常重要的作用。因为二叉树结构 简单，存储效率高，树的操作算法相对简单，且任何树都很容 易转化成二叉树结构。上节中引入的有关树的术语也都适用于 二叉树。 2二叉树的基本形态二叉树的基本形态二叉树有二叉树有5种基本形态，如图所示。种基本形态，如图所示。AAAA(a)(b)(c)(d)(e)(a) 空二叉树二叉树(b) 单结点二叉树二叉树(c) 右子树为空右子树为空(d) 左子树为空左子树为空(e) 左左、右子树都不空二叉右子树都不空二叉树的基本形态
12、二叉树的性质二叉树的性质 性质性质1：在非空二叉树中，第i层上至多有：在非空二叉树中，第i层上至多有2i-1个结点个结点(i1)。 证明：用数学归纳法证明。证明：用数学归纳法证明。当当i=1时：只有一个根结点，时：只有一个根结点，21-1=20=1，命题成立。，命题成立。现假设对现假设对i1时，处在第时，处在第i-1层上至多有层上至多有2(i-1)-1个结点。个结点。由归纳假设知，第由归纳假设知，第i-1层上至多有层上至多有2i-2个结点。由于二叉树 每个结点的度最大为个结点。由于二叉树 每个结点的度最大为2，故在第i层上最大结点数为第，故在第i层上最大结点数为第i-1层上 最大结点数的层上
13、最大结点数的2倍。倍。即即22i-22i-1证毕证毕 性质性质2：深度为：深度为k的二叉树至多有的二叉树至多有2k-1个结点个结点（k1) 。 证明：深度为证明：深度为k的二叉树的最大的结点数为二叉树中每层上的 最大结点数之和。的二叉树的最大的结点数为二叉树中每层上的 最大结点数之和。由性质由性质1知，二叉树的第，二叉树的第1层层、第第2层第层第k层上的结点数 至多有：层上的结点数 至多有： 20、21 2k-1 。 总的结点数至多有：结点数至多有： 20+21+ + +2k-1=2k-1 证毕证毕 性质性质3：对任何一棵二叉树，若其叶子结点数为：对任何一棵二叉树，若其叶子结点数为n0，度为，
14、度为2 的结点数为的结点数为n2，则，则n0=n2+1。 证明：证明：设二叉树中度为设二叉树中度为1的结点数为的结点数为n1，二叉树中总结点数为，二叉树中总结点数为 N，因为二叉树中所有结点均小于或等于，因为二叉树中所有结点均小于或等于2，则有：，则有： N=n0+n1+n2 再看二叉树中的分支数：再看二叉树中的分支数：除根结点外，其余每个结点都有唯一的一个进入分支，而 所有这些分支都是由度为除根结点外，其余每个结点都有唯一的一个进入分支，而 所有这些分支都是由度为1和和2的结点射出的。设的结点射出的。设B为二叉树 中的分支总数，则有：为二叉树 中的分支总数，则有：N=B+1Bn1+2 n2N
15、=B+1=n1+2 n2+1n0+n1+n2=n1+2 n2+1即n0=n2+1 证毕证毕满二叉树和完全二叉树满二叉树和完全二叉树 一棵深度为一棵深度为k且有且有2k-1个结点的二叉树称为个结点的二叉树称为满二 叉树满二 叉树(Full Binary Tree)。http:/894101151213614157213894101152112673(a) 满二叉树(b) 完全二叉树1362455674213(c) 非完全二叉树 满二叉树的特点满二叉树的特点： 基本特点是每一层上的结点数总是最大结点数。基本特点是每一层上的结点数总是最大结点数。 满二叉树的所有的支结点都有左满二叉树的所有的支结点都有左、右子树。右子树。 可对满二叉树的结点进行连续编号，若规定从根结点开始， 按可对满二叉树的结点进行连续编号，若规定从根结点开始， 按“自上而下自上而下、自左至右自左至右”的原则进行。的原则进行。 完全二叉树完全二叉树( (Complete Binary
