第6章 树和二叉树-100-3.pptVIP

第6章 树和二叉树 张成文 北京邮电大学计算机学院 满二叉树 在一个二叉树中，若第i层的结点数为2i-1，则称此层的结点数是满的，当树中的每一层都是满的，则称此二叉树为满二叉树。 即如果一个二叉树中，除最下一层的各结点度数为0以外，其它各层结点的度数均等于2，则此二叉树为满二叉树。 满二叉树的第一层有一个结点（即根结点），第二层有两个结点，依此类推。每一层的结点数都是上一层结点数的二倍。所以，在满二叉树的第i层共有2i-1个结点（i≥1），一个深度为h的满二叉树的结点总数为2h-1。 完全二叉树 如果一个二叉树各层都是“满”的，只是最下面一层从右边起连续缺n个结点，这种二叉树叫做完全二叉树。 例如上图的满二叉树，如果缺少从第11号至第15号结点，就是一个完全二叉树。 设完全二叉树的结点数为n，它与树的深度之间的关系为： 2h-1-1n≤ 2h-1 即n值大于深度为h-1的满二叉树的结点数，但小于或等于深度为h的满二叉树的结点数。 对于完全二叉树，对其结点采用“按层编号”比较方便，即从根结点开始由上而下逐层给结点编号，同一层的结点由左向右编号。 对于完全二叉树中任一个编号为i的结点(1≤i≤n)，它的父结点和左、右儿子结点的编号与i值有如下的关系： 1) 如果i=1，则它是整个树的根结点，无父结点；若i1，则其父结点编号为 。 2) 如果2i≤n，则其左儿子结点编号为2i；若2in，则无左儿子结点。 3) 如果（2i+1）≤n，则其右儿子结点编号为（2i+1）；反之，则无右儿子结点。 利用遍历结果确定二叉树问题 树的存储结构 [多重链表表示法] 结点结构 data child1 child2 … childm 数据域 指针域 (m: 树的度) 结点结构 fch data nsib fch: 指向该结点的第一个孩子结点 nsib: 指向该结点的下一个兄弟结点 6.9 哈夫曼树与 哈夫曼编码 [例] 有4个结点，权值分别为7，5，2，4，构造有4个 叶子结点的二叉树。 [例] w={5, 29, 7, 8, 14, 23, 3, 11} [例] { } 第一步： 第二步： 第三步： 第四步： [哈夫曼树] 哈夫曼树的应用 哈夫曼编码：用于通信和数据传送中字符的二进制编码，可以使电文编码总长度最短。 [例] 对time tries truth哈夫曼编码,并写出编码表 字符集 D={t, i, m, e, r, s, u, h} 出现频次 W={4, 2, 1, 2, 2, 1, 1, 1} 哈夫曼编码是不等长编码 哈夫曼编码是前缀编码，即任一字符的编码都不是另一字符编码的前缀 哈夫曼编码树中没有度为1的结点。若叶子结点的个数为n，则哈夫曼编码树的结点总数为 2n-1 发送过程：根据由哈夫曼树得到的编码表送出字符数据 接收过程：按左0、右1的规定，从根结点走到一个叶结点，完成一个字符的译码。反复此过程，直到接收数据结束 9 5 2 7 16 6 7 13 29 0 0 0 0 1 1 1 1 00 b 01 e 10 d 110 a 111 c 编码: 右分支:1 左分支:0 得到各叶结 点的编码表 叶结点代表电文的字符集(a,b,c,d,e), 权值分别为(5,6,2,9,7),代表它们在电文中出现的频度;电文: dadebedbca…的码文:10110100100011000111110…。 最优前缀编码不等长但译码时不会错电文总长最短。 利用哈夫曼树,求编码表时需要走一条从叶子结点到根结点的路径,译码时需要走一条从根结点到叶子结点的路径。 所以哈夫曼树的每个结点需要知道双亲和孩子的信息,故采用带双亲的孩子链表。 由于哈夫曼树中没有度数为 1的结点(称为正则的或严格的二叉树), 则有n个叶子结点的哈夫曼树共有m=2n-1个结点,可用有m个元素的数组来存储,其链接关系用下标来表示。 typedef struct { unsigned int weight; unsigned int parent, lchild, rchild; }HTNode, *HuffmanTree; //动态分配存储空间 HuffmanTree HT; u h t i e r