第5章 树和二叉树
图5.5
是一棵深度为4的满二叉树，每一层上的结点数都达到最大值2i-1(i≥1) 。不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层。
（2）完全二叉树
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
完全二叉树特点：
①在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树是一棵完全二叉树。
②满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。
③在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。
④深度为k的完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。
例如，如图5.6所示的两颗二叉树中
(a)
(b)
1）(a)是满二叉树，也是完全二叉树； (b) 图5.6 是完全二叉树，但不是满二叉树。2）在(a)的最下一层上，从最右边开始连续删去3个结点后得到完全二叉树
6 6
第5章 树和二叉树
(b) 。
3）在完全二叉树(b)中，结点6没有左孩子，也一定没有右孩子，即该结点6是叶结点。
4）(b)是深度为4的完全二叉树，它的前3层是深度为3的满二叉树，一共有23-1=7个结点。
性质4 具有n个结点的完全二叉树的深度为?lgn??1或?lg(n?1)?，其中
?lgn?表示取小于等于lgn的整数部分，?lg(n?1)?表示取大于等于lg(n+1)的整数
部分，lg表示以2为底的对数。
证明：设所求完全二叉树的深度为k。由完全二叉树特点知：深度为k的完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。
由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数n>2k-1-1。
另一方面，由性质2知：深度为k的二叉树至多有2k-1(k≥1)个结点，因此，n≤2k-1，
即：2k-1-l 由此即得：k??lgn??1。 另外，由2k-1-l (1) 顺序存储方式 用一组地址连续的存储单元依次“自上而下、自左至右”存储完全二叉树的数据元素。对于完全二叉树上编号为i的结点元素存储在一维数组的下标值为i-1的分量中，如图所示。对于一般的二叉树，将其每个结点与完全二叉树上的结点相对照，存储在一维数组中，如图所示。 第5章 树和二叉树 (2)链表存储方式，如：设计不同的结点结构可构成不同的链式存储结构。 二叉链表结点。有三个域：一个数据域，两个分别指向左右子结点的指针域，如图6-7(a)所示。 typedef struct BTNode { ElemType data ; struct BTNode *Lchild , *Rchild ; }BTNode ; 4.普通树转换成二叉树：凡是兄弟就用线连起来，然后去掉父亲到儿子的连线，只留下父母到其第一个子女的连线。 5.二叉树的遍历运算（递归定义） (1)先序遍历 访问根；按先序遍历左子树；按先序遍历右子树 算法的递归定义是： 若二叉树为空，则遍历结束；否则 a) 访问根结点 b) 先序遍历左子树(递归调用本算法)； c) 先序遍历右子树(递归调用本算法)。 第5章 树和二叉树 void PreorderTraverse(BTNode *T){ if (T!=NULL) { visit(T->data) ; /* 访问根结点 */ PreorderTraverse(T->Lchild) ; PreorderTraverse(T->Rchild) ; } } (2)中序遍历 按中序遍历左子树；访问根；按中序遍历右子树 void InorderTraverse(BTNode *T){ if (T!=NULL) { InorderTraverse(T->Lchild) ; visit(T->data) ; /* 访问根结点 */ InorderTraverse(T->Rchild) ; } } (3)后序遍历 按后序遍历左子树；按后序遍历右子树；访问根 void PostorderTraverse(BTNode *T){ if (T!=NULL) { PostorderTraverse(T->Lchild) ; PostorderTraverse(T->Rchild) ; visit(T->data) ; /* 访问根结点 */ } 例1.用顺序存储方式建立一棵有31个结点的满二叉树，并对其进行先序遍历。 例2.用顺序存储方式建立一棵如图所示的二叉树，并对其进行先序遍历。 } 例3 用链表存储方式生成上述二叉树，中序遍历之。 1.将上述二叉树用广义表表示为A(B(D,E(G)),C(F(,H))) 2.根据广义表串（以#结束）生成二叉树。 5.3二叉树的应用 1. 哈夫曼树与哈夫曼码 树的路径长度：一棵树的每一个叶结点到根结点的路径长度的和。 第5章 树和二叉树 带权二叉树：给树的叶结点赋上某个实数值（称叶结点的权）。 带权路径长度：各叶结点的路径长度与其权值的积的总和。 哈夫曼树（最优二叉树）：带权路径长度最小的二叉树。 如何构建哈夫树：（思想是：权越大离跟越近） 哈夫曼码：哈夫曼树的非叶结点到左右孩子的路径分别用0，1 表示，从根到叶的路径序列即为哈夫曼码。 哈夫曼码是不会发生译码多义性的不等长编码，广泛应用实际中。 2.排序二叉树 排序二叉树：每一个参加排列的数据对应二叉树的一个结点，且任一结点如果有左（右）子树，则左（右）子树各结点的数据必须小（大）于该结点的数据。中序遍历排序二叉树即得排序结果。程序如下： 3.堆排序 堆：设有数据元素的集合（R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且有 Ri<=R2i 和Ri<=R2i+1(或>=) 堆的性质：堆的根结点上的元素是堆中的最小元素，且堆的每一条路径上的元素都是有序的。 堆排序的思想是： 1）建初始堆（将结点[n/2],[ n/2]-1,...3,2,1分别调成堆） 2）当未排序完时 输出堆顶元素，删除堆顶元素，将剩余的元素重新建堆。 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库NOIP高中信息技术竞赛资料 - -数据结构(8)在线全文阅读。
相关推荐：