《数据结构A》第05章

《《数据结构A》第05章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构DataStructuresinC++南京邮电大学计算机学院陈慧南2006年9月第5章树南京邮电大学计算机学院陈慧南2006年9月5.1树的基本概念5.2二叉树5.3二叉树的遍历5.5树和森林5.6堆和优先权队列5.7哈夫曼树和哈夫曼编码5.8并查集和等价关系南京邮电大学计算机学院陈慧南2006年9月5.1树的基本概念南京邮电大学计算机学院陈慧南2006年9月树形结构是元素之间有着分层关系的结构，它类似于自然界中的树。这是一类很重要的非线性数据结构。一方面，计算机应用中，常常出现嵌套的数

2、据，树结构提供了对该类数据的自然表示。另一方面利用树结构，我们可以有效地解决一些算法问题。南京邮电大学计算机学院陈慧南2006年9月图5-1西欧语言谱系图原始印欧语古意大利语日耳曼语西日耳曼语拉丁语西班牙语法语意大利语希腊语北日耳曼语冰岛语瑞典语挪威语英语荷兰语德语古希腊语南京邮电大学计算机学院陈慧南2006年9月5.1.1树的定义定义5.1树是包括n个结点的有限非空集合D，R是D中元素的序偶的集合，R满足以下特性：（1）有且仅有一个结点rD，不存在任何结点vD，vr，使得R，

3、称r为树的根；（2）除根r以外的所有结点uD，都有且仅有一个结点vD，vu，使得R。这样定义的树也称有根树，简称树。南京邮电大学计算机学院陈慧南2006年9月定义5.2树是包括n个结点的有限非空集合T，其中，一个特定的结点r称为根，其余结点T-{r}划分成m（m0）个互不相交的子集T1,T2,,Tm，其中，每个子集都是树，被称为树根r的子树。南京邮电大学计算机学院陈慧南2006年9月5.1.2基本术语树中元素常称为结点。根和它的子树根（如果存在）之间形成一条边。如果从某个结

4、点沿着树中的边可到达另一个结点，则称这两个结点间存在一条路径。南京邮电大学计算机学院陈慧南2006年9月若一个结点有子树，那么该结点称为子树根的双亲，子树的根是该结点的孩子。有相同双亲的结点互为兄弟。一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点路径上的所有结点都是该结点的祖先。南京邮电大学计算机学院陈慧南2006年9月一个结点拥有的子树数称为该结点的度。度为零的结点称为叶子，其余结点称为分支结点。树中结点的最大的度称为树的度。树是层次结构的，规定根结点的层次为1，其结点的层

5、次等于其双亲结点的层次加1。树中结点的最大层次称为该树的高度。南京邮电大学计算机学院陈慧南2006年9月如果树中结点的各子树之间的次序是不重要的，可以交换位置，这样的树称为无序树。也就是我们通常所说的树。如果将树中结点的各棵子树看成是从左到右有次序的，则称该树为有序树。从左到右，可分别称这些子树为第一子树，第二子树等等。森林是树的集合。果园或称有序森林是有序树的有序集合。南京邮电大学计算机学院陈慧南2006年9月5.2二叉树南京邮电大学计算机学院陈慧南2006年9月5.2.1二叉树的定义定义5.

6、3二叉树是结点的有限集合，该集合或者为空集，或者是由一个根和两棵互不相交的，称为该根的左子树和右子树的二叉树组成。南京邮电大学计算机学院陈慧南2006年9月二叉树的五种基本形态二叉树与树的区别二叉树可以为空二叉树二叉树结点的子树分为左、右子树南京邮电大学计算机学院陈慧南2006年9月5.2.2二叉树的性质性质5.1二叉树的第i(i1)层上至多有2i-1个结点。证明：当i=1时，二叉树只有一个结点，结论成立。设当i=k时结论成立，则当i=k+1时，因为每个结点最多只有两个孩子，所以，第k+1层上

7、至多有2*2k-1=2k个结点，性质成立。南京邮电大学计算机学院陈慧南2006年9月性质5.2高度为h的二叉树上至多有2h–1个结点。证明：当h=0时，二叉树为空二叉树。当h>0时，利用性质5－1，高度为h的二叉树中结点的总数最多为：南京邮电大学计算机学院陈慧南2006年9月性质5.3包含n个元素的二叉树的高度至少为log2(n+1)证明：由性质2，高度为h的二叉树最多有2h–1个结点，因而n2h–1,则有hlog2(n+1)。因h是整数，所以hlog2(n+1)。南京邮电大学计算

8、机学院陈慧南2006年9月性质5.4任意一棵二叉树中，若叶结点的个数为n0，度为2的结点的个数为n2，则必有n0=n2+1。证明：设二叉树的结点总数为n，则n=n0+n1+n2孩子数为n-1=n1+2n2，因此，n0=n2+1南京邮电大学计算机学院陈慧南2006年9月定义5.4高度为h的二叉树恰好有2h–1个结点时称为满二叉树。定义5.5一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上，这样的二叉树称为完全二叉树。定义5.6扩充二叉树也称2－树，扩充二叉