Huffman树、二叉排序树汇编.ppt

Hu Junfeng Hu Junfeng Huffman树、二叉排序树 胡俊峰 2016/04/8 * 今天的内容 Huffman树 二叉排序树简介 * 建立n个元素的堆？ 从0开始，不断插入堆：O nlogn * 有没有更好（高效率）的方法？ 0 1 2 3 4 5 6 7 8 9 10 11 * 哈夫曼树及其应用 哈夫曼树 哈夫曼算法 哈夫曼编码 * Huffman树与最优编码 信息与编码 扩充二叉树与最优编码 Huffman树 * 扩充二叉树的概念 把原二叉树的结点都变为度数为2的分支结点 如果原结点的度数为2，则不变 度数为1，则增加一个分支， 度数为0（树叶），则增加两个分支。 空二叉树的扩充二叉树规定为只有一个外部结点组成的二叉树。 德 智 5 体 7 70 18 内部节点 Y N Y Y N N 100 * 概率加权、前缀编码、加权平衡二叉树 wi是第i个外部结点的权值 li为从根到第i个外部结点的路径长度 m为外部结点的个数。 WPL 1 x 5 + 2 x 70 + 3 x 18 + 3 x 7 5 + 140 + 54 + 21 220 德 智 5 体 7 70 18 内部节点 Y N Y Y N N 100 外部路径 1 0 0 0 1 1 * 外部路径与加权外部路径 “外部路径长度” E:在扩充的二叉树里从根到每个外部结点的路径长度之和。 其中，li为从根到第i个外部结点的路径长度，m为外部结点的个数。 设扩充二叉树具有m个带权值的外部结点，那么从根结点到各个外部结点的路径长度与相应结点权值的乘积的和，叫做扩充二叉树的带权的外部路径长度。 其中，wi是第i个外部结点的权值，li为从根到第i个外部结点的路径长度，m为外部结点的个数。 * 哈夫曼树： 对于一组非负实数｛w1 , w2 , w3 ,…, wm｝，存在一棵以wi（i 1,2,…，m）为权的m个外部结点的扩充的二叉树，使得带权的外部路径长度WPL最小。这棵二叉树就称为哈夫曼树或最优二叉树。 WPL 1 x 70 + 2 x 18 + 3 x 5 + 3 x 7 70 + 36 + 15 +21 142 智 体 70 德 7 18 5 内部节点 Y N Y Y N N 100 * 哈夫曼树（构建算法） 给定m个权值 w1 , w2 ,…, wm （叶子） 构造由m棵二叉树组成的树林F T1,T2,…,Tm ，其中每棵树Ti 只有一个根结点，且根结点的权值为wi； 在树林中选取两棵根结点权值最小的和次小的二叉树作为左右子树构造一棵新的二叉树，其根结点的权值为左右子树根结点权值之和。 将新的二叉树加入到树林F中，去除原两棵权值最小的树； 重复2、3步骤，直至F中只剩一棵树为止。 * 给定权值 7，5，2，4 ，构造哈夫曼树 a b c d 7 5 2 4 a 6 7 5 c d b 11 b 5 7 c d c 6 a 7 11 c d b 5 6 2 4 d 18 * 信息量： * 哈夫曼编码：在概率意义上平均码长最短 互不为子串 145 220 80 100 50 65 50 0 1 1 0 1 hot,50 , warm,65 , mild,120 , cold,80 , very cold,50 120 1 0 365 0 hot 111 warm 01 mild 10 cold 00 very cold 110 * 哈夫曼树的存储实现 存储结构可以有多种，如二叉链表、三叉链表等。下面给出一种顺序结构 一维数组），结点结构： ww: 以该结点为根的子树中所有外部结点的加权和。 parent: 父结点在数组中的存储位置（下标），根无父，设为-1。 llink: 左孩子存储位置，对于外部结点，无孩子，设为-1。 rlink: 右孩子存储位置，对于外部结点，无孩子，设为-1。 ww parent llink rlink * 在线性结构上实现哈夫曼树 struct HtNode //* 哈夫曼树结点的结构 int ww; int parent, llink, rlink; ; 哈夫曼树可定义为： struct HtTree struct HtNode ht[MAXNODE]; int root；/* 树根在数组中的下标*/ ;typedef struct HtTree *PHtTree; * 哈夫曼算法（初始化） * 哈夫曼算法（构造树） 思考：如果用堆结构实现huffman算法有没有问题？ * 使用 优先 队列 * 二叉排序树（又称二叉搜索树） 以关键码值为结点的二叉树 如果任一结点的左子树非空，则左子树中的所有结点的关键码都小