《数据结构a》第05章——02

《《数据结构a》第05章——02》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构DataStructuresinC++南京邮电大学计算机学院2006年9月第5章树5.1树的基本概念5.2二叉树5.3二叉树的遍历5.4二叉树遍历的非递归算法5.5树和森林5.6堆和优先权队列5.7哈夫曼树和哈夫曼编码5.8并查集和等价关系南京邮电大学计算机学院2006年9月5.2二叉树5.1树的基本概念5.2二叉树5.3二叉树的遍历5.4二叉树遍历的非递归算法5.5树和森林5.6堆和优先权队列5.7哈夫曼树和哈夫曼编码5.8并查集和等价关系南京邮电大学计算机学院2006年9月5.2.1二叉树的定义定义5.3二叉树是结点的有限集合，该集合或者为空集，或者是由一个根和两棵

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

3、时，二叉树为空二叉树。当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)。南京邮电大学计算机学院陈慧南2006年9月性质5.4任意一棵二叉树中，若叶结点的个数为n0，度为2的结点的个数为n2，则必有n0=n2+1。证明：设二叉树的结点总数为n，则n=n0+n1+n2孩子数为n-1=n1+2n2，因此，n0=n2+1南京邮

4、电大学计算机学院陈慧南2006年9月定义5.4高度为h的二叉树恰好有2h–1个结点时称为满二叉树。定义5.5一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上，这样的二叉树称为完全二叉树。定义5.6扩充二叉树也称2－树，扩充二叉树中除叶子结点外，其余结点都必须有两个孩子。南京邮电大学计算机学院陈慧南2006年9月南京邮电大学计算机学院陈慧南2006年9月性质5.5具有n个结点的完全二叉树的高度为log2(n+1)。证明：设完全二叉树的高度为h，则除最下层外，前h-1层形成满二叉树，总共有2h-11个结点；而最下层，即第h层的结点个数

5、最多不超过2h-1个。因此有2h-110，则该结点的双亲的序号为(i-1)/2；南京邮电大学计算机学院陈慧南2006年9月（3）若2i+1

6、，否则该结点无左孩子；(4)若2i+2

7、lse。MakeTree(x,left,right):构造一棵二叉树：根的值为x，以left和right为左右子树。BreakTree(x,left,right):拆分二叉树为三部分：x为根的值，left和right分别为原树的左、右子树南京邮电大学计算机学院陈慧南2006年9月PreOrder(Visit):使用函数Visit访问结点,先序遍历二叉树。InOrder(Visit):使用函数Visit访问结点,中序遍历二叉树。PostOrder(Visit):使用函数Visit访问结点,后序