哈弗曼和最小堆的数据结构知识-公开课件.ppt

CS422S: Operating Systems Organization CS422S: Operating Systems Organization 数据结构补充知识 5.6 Huffman树及其应用 5.6.1 Huffman树 5.6.2 Huffman编码 5.6.1 Huffman树 假设有n个权值分别为w0，w1，…，wn-1(n≥2)的结点，求带权外部路径长度就是要构造一棵具有n个外部结点的扩充二叉树，每一个外部结点ki取wi作为它的权，li表示该外部结点的路径长度，则带权外部路径长度可记作 其中带权外部路径长度最小的二叉树称为Huffman树 5.6.1 Huffman树 例如，图5.18中表示了三棵具有4个外部结点的二叉树，各外部结点的权值 分别为6，2，3，4。 它们的带权外部路径长度分别为： (a) 6×2 + 2×2 + 3×2 + 4×2 = 30 (b) 6×2 + 2×3 + 3×3 + 4×1 = 31 (c) 6×1 + 2×3 + 3×3 + 4×2 = 29 其中，5.18(c)中所示的二叉树外部带权路径长度最小。可以验证， 它就是一棵Huffman树，也就是说，这棵树在所有的具有6，2，3， 4权值的叶结点的二叉树中带权外部路径长度最小。 5.6.1 Huffman树 建立Huffman编码树： (1) 对于给定的n个权值w0，w1，…，wn-1(n≥2)，构成n棵二叉树的集合T = { T0，T1，T2，…，Tn－1}，使得每一棵扩充二叉树只具有一个带权为wi的根结点。 (2) 构造一棵新的扩充二叉树，在集合T中找出两个权值最小的树作为新树根结点的左右子树，把新树根结点的权值赋为其左右子树根结点的和。 (3) 在集合T中删除这两棵树，并把得到的新扩充二叉树加入到集合中。 (4) 重复步骤(2)、(3)的操作，直到集合T中只含有一棵树为止。 5.6.1 Huffman树 图5.19 Huffman树的构造过程 5.6.1 Huffman树 【代码5.12】 Huffman树的类定义 templateclass T class HuffmanTree { private: HuffmanTreeNodeT *root; // Huffman树的根结点 void MergeTree ( HuffmanTreeNodeT ht1, HuffmanTreeNodeT ht2, HuffmanTreeNodeT *parent); // 把以ht1和ht2为根的两棵Huffman树合并成一棵以parent为根的二叉树 void DeleteTree(HuffmanTreeNodeT *root); // 删除Huffman树或其子树 public: HuffmanTree(T weight[],int n); // 构造Huffman树，参数weight为权值数组，n为数组长度 virtual ~HuffmanTree(){DeleteTree(root);}; // 析构函数 }; 5.6.1 Huffman树 templateclass T HuffmanTreeT::HuffmanTree(T weight[], int n) { MinHeap HuffmanTreeNodeT heap(n); // 最小值堆 HuffmanTreeNodeT *parent, firstchild, secondchild; HuffmanTreeNodeT *NodeList = new HuffmanTreeNodeT[n]; for (int i = 0;i n;i++) { // 初始化 NodeList[i].info = weight[i]; NodeList[i].parent = NodeList[i].left = NodeList[i].right = NULL; heap.Insert(NodeList[i]); // 向堆中添加元素 } for (i = 0;i n-1;i++) { // 通过n-1次合并建立Huffman树 5.6.1 Huffman树 parent = new HuffmanTreeNodeT; // 申请一个分支结点 firstchild = heap.RemoveMin(); // 选择权值最小的结点 secondchild