首页 > 代码库 > 哈夫曼树(Huffman)

哈夫曼树(Huffman)

2024-07-25 07:42:57   223人阅读

在数据结构书中，讲解树内容的时候，都会介绍哈夫曼树（Huffman）和哈夫曼编码（哈夫曼树的一种应用）。关于哈夫曼树的定义，在这里就不讨论了，接下来贴出LZ实现哈夫曼树的一种方案。

构建哈夫曼树：

  • 1.首先将所有的节点构成独立的二叉树，这些二叉树构成的一个森林，将这些二叉树构建成一个最小堆；
  • 2.选择最小堆中两个最小树，构建成一颗新的树，将新树插入到最小堆中，删除被选出的两颗最小树；
  • 3.如果最小堆节点数大于1，重复2。
  • 4.最小堆中最后一个节点，这棵树就是哈夫曼树。

本文中二叉树的实现类似二叉排序树，最小堆的实现如数据结构—堆。构建哈夫曼树的实现如下：

 1 #define  MaxSize 100 2 template<typename Type>  3 void Huffman(Type *elements, int n, BinaryTree<Type> &tree){ 4     BinaryTree<Type> first, second; 5     BinaryTree<Type> node[MaxSize]; 6     for (int i=0; i<n; i++){ 7         node[i].m_proot = new BinTreeNode<Type>(elements[i]); 8     } 9     MinHeap<BinaryTree<Type> > heap(node, n);10 11     for (int i=0; i<n-1; i++){12         frist=heap.DeleteMin();13         second=heap.DeleteMin();16         if (first.m_proot->GetData() == second.m_proot->GetData()){17             tree = *(new BinaryTree<Type>(second, first));18         }19         else {20             tree = *(new BinaryTree<Type>(first, second));21         }22 23         heap.Insert(tree);24     }25 }

 

哈夫曼树(Huffman)


联系
我们