构造n棵只有根结点的二叉树-Read.PPT

第7章 树和二叉树 T=（D，R） DF = D1∪D2∪…∪Dm （1≤i,j≤m, Di∩Dj=￠） R={Root, ri, i=1,2,…,n-1} 4.树的存储结构 树的结点之间的逻辑关系主要有双亲-孩子关系，兄弟关系。因此，从结点之间的逻辑关系分，树的存储结构主要有：双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法四种组合。 指针有常规指针和仿真指针 1.二叉树的定义 二、满二叉树：在一棵二叉树中，如果所有分支结点都存在左 子树和右子树，并且所有叶子结点都在同一层上，这样的 二叉树称为满二叉树。 三、完全二叉树：如果一棵深度为k，有n个结点的二叉树中各 结点能够与深度为k的顺序编号的满二叉树从1到n标号的 结点相对应的二叉树称为完全二叉树。如下图所示 2.二叉树抽象数据类型 3.二叉树的性质 7.3二叉树的设计和实现 7.3.1二叉树的存储结构 二叉树的存储结构主要有三种：顺序存储结构、链式存储结 构和仿真指针存储结构。 1. 二叉树的顺序存储结构 完全二叉树的结点可按从上至下和从左至右的次序存储在一维数组中，其结点之间的关系可由公式计算得到，这就是二叉树的顺序存储结构。下面两棵树在数组中的存储结构分别为： 一旦建立了某种方式的线索二叉树后，用户程序就可以像操作双向链表一样操作该线索二叉树。 例如，一旦建立了中序线索二叉树后，用户程序就可以设计一个正向循环结构遍历该二叉树的所有结点，循环初始定位在中序线索二叉树的第一个结点位置，每次循环使指针指向当前结点的中序遍历的后继结点位置，当指针指向中序线索二叉树的最后一个结点位置后循环过程结束；或者用户程序可以设计一个反向循环结构遍历该二叉树的所有结点，循环初始定位在中序线索二叉树的最后一个结点位置，每次循环使指针指向当前结点的中序遍历的前驱结点位置，当指针指向中序线索二叉树的第一个结点位置前循环过程结束。 这种算法设计要求分别设计三个函数： First()：定位在第一个结点位置； Next()：移动到下一个结点位置； End()：是否已经到最后下一个结点位置； 当然，还需要一个根据二叉树构造线索二叉树的函数。 例：设有字符集{A, B, C, D}，各字符在电文中出现的次数集为{1, 3, 5, 7}，则哈夫曼树构造过程如下图所示： 下标 weight leftChild rightChild parent flag 0 1 -1 -1 -1 0 1 3 -1 -1 -1 0 2 5 -1 -1 -1 0 3 7 -1 -1 -1 0 4 0 -1 -1 -1 0 5 0 -1 -1 -1 0 6 0 -1 -1 -1 0 （a） 下标 weight leftChild rightChild parent flag 0 1 -1 -1 4 1 1 3 -1 -1 4 1 2 5 -1 -1 -1 0 3 7 -1 -1 -1 0 4 4 0 1 -1 0 5 0 -1 -1 -1 0 6 0 -1 -1 -1 0 （b）第一步的结果 下标 weight leftChild rightChild parent flag 0 1 -1 -1 4 1 1 3 -1 -1 4 1 2 5 -1 -1 5 1 3 7 -1 -1 -1 0 4 4 0 1 5 1 5 9 4 2 -1 0 6 0 -1 -1 -1 0 （c）第二步的结果 下标 weight leftChild rightChild parent flag 0 1 -1 -1 4 1 1 3 -1 -1 4 1 2 5 -1 -1 5 1 3 7 -1 -1 6 1 4 4 0 1 5 1 5 9 4 2 6 1 6 16 3 5 -1 0 （d）哈夫曼树构造结果 0 1 2 3 bit start weight （e）哈夫曼编码结果 ? 1 0 0 1 1 ? 1 0 1 1 3 ? ? 1 1 2 5 ? ? ? 0 3 7 例7-5 设有字符集{A, B, C, D}，各字符在电文中出现的次数集为{1, 3, 5, 7}，设计各字符的哈夫曼编码。 #include stdio.h #include stdlib.h #define MaxValue 10000 #define MaxBit 4 #define M