| 最优二叉树 | 您所在的位置：网站首页 › 前缀码概念 › 最优二叉树 |
最优二叉树
|
1.最优二叉树的定义
最优二叉树又称哈夫曼树，是一种带权路径长最短的树。树的路径长度是从树根到每一个叶子之间的路径长度之和。节点的带树路径长度为从该节点到树根之间的路径长度与该节点权（比如字符在某串中的使用频率）的乘积。 2.构造哈夫曼树 2.1贪心算法贪心算法（又称贪婪算法）是指，在对 问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部 最优解。 在构建哈夫曼树的过程中，即每次选出两个权值最小的数据，构成左右子树。 2.2构建哈夫曼树的过程有一堆数据0，1，2，3，4该如何构建哈夫曼树呢？ 按照贪心算法每次找权值最小（即值最小）的两个数，构成孩子结点，并将这两个数据排除出这一堆数据之外 由于哈弗曼树的数据全在叶子结点，所以把上述权值最小的两个数据构成父结点，然后再将父结点的权值放回上述数据，返回第一步，重复上述过程，直到所有的数据都变成哈夫曼树的叶子结点 1>从构建哈夫曼树的过程我们可以看到每次要选出两个最小的数据，为了提高效率，我们将数据的结点建堆,由于要取权值最小的，所以建小堆，这样能避免因为用数据建堆可能造成重复创建结点 构建堆的代码： [cpp] view plain copy print ? #include template struct Greater { bool operator()(const T& left, const T& right) const { return left > right; } }; template class Heap { public: Heap() {} Heap(T* a, size_t n) { //减少多次开辟容量的代价 v.reserve(n); for (size_t i = 0; i = 0; i–) { AdjustDown(i); } } //从哪个结点开始调整 void AdjustDown(int parent) { Compare com; int Size = v.size(); int child = parent * 2 + 1; while (child = 0) { //if (v[child] > v[parent]) if (com(v[child], v[parent])) { swap(v[child], v[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } void Push(const T& x) { v.push_back(x); AdjustUp(v.size() - 1); } void Pop() { swap(v[0], v[v.size() - 1]); v.pop_back(); AdjustDown(0); } T& Top() { assert(v.size() > 0); return v[0]; } size_t Size() { return v.size(); } protected: vector v; };
2> 每次取出堆顶的最小的数据之后，将堆中的存放结点删除，重复两次，再将权值相加，创建一个新的结点，并将三个结点链接，将它存放到堆中，在堆中每次删除和增加数据时，记得将堆调整为小堆，直到堆中只剩下一个结点时，哈夫曼树就构建成功了 构建哈夫曼树代码： [cpp] view plain copy print ? #include “Heap.hpp” template struct HuffmanNode { HuffmanNode* _lchild; HuffmanNode* _rchild; HuffmanNode* _parent; W _w; HuffmanNode(const W &w) :_lchild(NULL) , _rchild(NULL) , _w(w) , _parent(NULL) {} }; template class HuffmanTree { typedef HuffmanNode Node; public: HuffmanTree() :_root(NULL) {} HuffmanTree(W* a, size_t n,W &invalid) { //堆中存放的是结点,而比较大小的时候我们希望比较的是权值 struct NodeCompare { bool operator()(const Node* left, const Node* right) const { return left->_w _w; } }; Heap minHeap; for (size_t i = 0; i 1) { Node* left = minHeap.Top(); minHeap.Pop(); Node* right = minHeap.Top(); minHeap.Pop(); Node* cur = new Node(left->_w + right->_w); minHeap.Push(cur); parent = cur; parent->_lchild = left; parent->_rchild = right; left->_parent = parent; right->_parent = parent; } _root = parent; } Node* GetRoot() { return _root; } protected: Node* _root; };
3.哈夫曼编码
3.1前缀编码
在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀（最左子串）。 例： 比如一组编码01，010，001，100，110就不是前缀编码，因为01是010的前缀，如果去掉01和010就是前缀编码了。好比人名张三和张三章就不是前缀编码。 3.2哈夫曼编码（最优前缀编码）对于一棵具有叶子结点的哈弗曼树，若对树中的每个左支赋予0，右支赋予1（也可以左1右0），则从根到每个叶子结点的通路上，各分支的赋值构成一个二进制串，该二进制串称为哈夫曼编码。 统计字符出现的个数 构建哈夫曼树 生成哈夫曼编码 构建哈夫曼编码的代码： 测试用例：aaaabbbccd [cpp] view plain copy print ? #include “Huffman.hpp” #include //字符串每个结点的信息 typedef size_t LongType; struct CharInfo { char ch; //字符 LongType count; // 字符出现个数 string code; //比较字符串出现的个数是否相等 bool operator!=(const CharInfo &x) const { return this->count != x.count; } CharInfo operator+(const CharInfo &x) const { CharInfo ret; ret.count = this->count + x.count; return ret; } bool operatorcount _lchild == NULL) { Node* cur = root; Node* parent = NULL; string s; while (cur->_parent != NULL) { parent = cur->_parent; if (parent->_lchild == cur) s.push_back(’1’); else s.push_back(’0’); cur = parent; } //stl中提供的算法逆置,只需提供一段迭代器区间即可 reverse(s.begin(), s.end()); root->_w.code = s; //输出霍夫曼编码 cout |
从叶节点往根扫描，若为左子树则标记为0，为右子树则标记为1。如上图6的编码即为：00，5的编码100，等等。【本文地址】