chapter0006 树与二叉树.pptVIP

数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~;数 据 结 构;数 据 结 构;A;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;例如:;root;A;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;A;void preorder(JD *bt) { if(bt!=NULL) { printf(%d\t,bt-data); preorder(bt-lchild); preorder(bt-rchild); } };遍历算法应用 按先序遍历序列建立二叉树的二叉链表，已知先序序列为： A B C ? ? D E ? G ? ? F ? ? ?;数 据 结 构;A;数 据 结 构;A;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;A;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;G;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;G;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;等长编码;不等长编码;前缀编码;具体构造方法：;假设某系统通信联络中只可能出现8种字符 ,其 出现概率为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11, 试设计哈夫曼编码。;哈夫曼编码的算法实现;9;哈夫曼编码的算法实现;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;数 据 结 构;哈夫曼树;路径：从一个结点到另一个结点之间的分支 序列。;带权路径长度：在树形结构中，我们把从树根到某一结点的路径长度与该结点权的乘积，称做该结点的带权路径长度。;例如下图所示的三棵二叉树;什么样的树的带权路径长度WPL最小？; 在各种形态的含有 n个叶子结点的 二 叉树中, 必存在一棵(几棵)其带权路径长度值WPL 最小的树，被称为“最优二叉树” 。 ;二、如何构造最优树（哈夫曼算法）;例如:;假设用于通讯的电文仅有8个字母组成，字母在电文中出现的频率分别是： （0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,） 请为这8个字母设计哈夫曼编码，同时画出相对应的哈夫曼树； 计算出这颗哈夫曼树的带权路径WPL。;哈夫曼算法的实现;静态三叉链表结构定义;2、哈夫曼算法;哈夫曼树的算法实现;哈夫曼树的算法实现; i;;;4. Huffman算法实现—选择函数; 哈夫曼树最典型的应用是在编码，利用哈夫曼树，可以得到平均长度最短的编码。;2、哈夫曼编码:;7;结论一：哈夫曼编码是前缀码。;假设某系统通信联络中只可能出现8种字符 ,其出现概率为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。;4、哈夫曼编码算法;;【试题】（北京邮电大学）假设用于通信的电文由字符集{a, b, c, d, e, f, g}中的字母构成。它们在电文中出现的幅度分别为{0.31, 0.16, 0.10, 0.08, 0.11, 0.20, 0.04}。（1）为这7个字母设计哈夫曼编码。（2）为这7个字母进行等长编码，至少需要几位二进制数？哈夫曼编码比等长编码使电文总长压缩多少？