最优⼆叉树--哈夫曼树和最优前缀编码--哈夫曼编码
1.最优⼆叉树的定义
最优⼆叉树⼜称哈夫曼树，是⼀种带权路径长最短的树。树的路径长度是从树根到每⼀个叶⼦之间的路径长度之和。节点的带树路径长度为从该节点到树根之间的路径长度与该节点权（⽐如字符在某串中的使⽤频率）的乘积。 2.构造哈夫曼树
2.1贪⼼算法
贪⼼算法（⼜称贪婪算法）是指，在对 问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部 最优解。 在构建哈夫曼树的过程中，即每次选出两个权值最⼩的数据，构成左右⼦树。 2.2构建哈夫曼树的过程
有⼀堆数据0，1，2，3，4该如何构建哈夫曼树呢？
1. 按照贪⼼算法每次权值最⼩（即值最⼩）的两个数，构成孩⼦结点，并将这两个数据排除出这⼀堆数据之外 2. 由于哈弗曼树的数据全在叶⼦结点，所以把上述权值最⼩的两个数据构成⽗结点，然后再将⽗结点的权值放回上述数据，返回第⼀
步，重复上述过程，直到所有的数据都变成哈夫曼树的叶⼦结点
2.3⽤代码实现哈夫曼树
1>从构建哈夫曼树的过程我们可以看到每次要选出两个最⼩的数据，为了提⾼效率，我们将数据的结点建堆，由于要取权值最⼩的，所以建⼩堆，这样能避免因为⽤数据建堆可能造成重复创建结点
构建堆的代码：
[cpp]
1. #include <vector>
2. template<class T>
3. struct Greater
4. {
5. bool operator()(const T& left, const T& right) const
6. {
7. return left > right;
8. }
9. };
10.
11. template<typename T,class Compare=Greater<T>>功率因数校正
12. class Heap
13. {
14. public:
15. Heap()
16. {}
17. Heap(T* a, size_t n)
18. {
19. //减少多次开辟容量的代价
20. v.reserve(n);
21. for (size_t i = 0; i < n; i++)
22. {
23. v.push_back(a[i]);
24. }
25. //建堆
26. int Size = v.size();
27. for (int i = (Size - 2) / 2; i >= 0; i–)
28. {
29. AdjustDown(i);
滚压头
30. }
北京高校对超期学生发逾期警告
31. }
32.
33. //从哪个结点开始调整
34. void AdjustDown(int parent)
35. {
36. Compare com;
37. int Size = v.size();
38. int child = parent * 2 + 1;
39. while (child < Size)
40. {
41. //if (child + 1 < Size&&v[child + 1] > v[child])
42. if (child + 1 < Size&&com(v[child + 1], v[child]))
43. {
44. child++;
45. }
46. //if (v[child] > v[parent])
47. if (com(v[child],v[parent]))
48. {
49. swap(v[child], v[parent]);
50. parent = child;
培训经理认证
51. child = parent * 2 + 1;
52. }
53. else
54. {
55. break;
索爱m600
56. }
消失的建筑
57. }
58. }
59. void AdjustUp(int child)
60. {
61. Compare com;
62. int parent = (child - 1) / 2;
63. while (parent >= 0)
64. {
65. //if (v[child] > v[parent])
66. if (com(v[child], v[parent]))
67. {
68. swap(v[child], v[parent]);
69. child = parent;
70. parent = (child - 1) / 2;
71. }
72. else
73. {
74. break;
75. }
76. }
77. }
78. void Push(const T& x)
79. {
80. v.push_back(x);
81. AdjustUp(v.size() - 1);
82. }
83. void Pop()
84. {
85. swap(v[0], v[v.size() - 1]);
86. v.pop_back();
87. AdjustDown(0);
88. }
89. T& Top()
90. {
91. assert(v.size() > 0);
92. return v[0];
93. }
94. size_t Size()
95. {
96. return v.size();
97. }
98. protected:
99. vector<T> v;
100. };
2> 每次取出堆顶的最⼩的数据之后，将堆中的存放结点删除，重复两次，再将权值相加，创建⼀个新的结点，并将三个结点链接，将它存放到堆中，在堆中每次删除和增加数据时，记得将堆调整为⼩堆，直到堆中只剩下⼀个结点时，哈夫曼树就构建成功了
构建哈夫曼树代码：
[cpp]
1. #include “Heap.hpp”
2. template<typename W>
3. struct HuffmanNode
4. {
5. HuffmanNode<W>* _lchild;
6. HuffmanNode<W>* _rchild;
7. HuffmanNode<W>* _parent;
8. W _w;
9. HuffmanNode(const W &w)
10. :_lchild(NULL)
11. , _rchild(NULL)
12. , _w(w)
13. , _parent(NULL)
14. {}
15.
16. };
17.
18. template <typename W>
19. class HuffmanTree
20. {
21. typedef HuffmanNode<W> Node;
22. public:
23. HuffmanTree()
24. :_root(NULL)
25. {}
26. HuffmanTree(W* a, size_t n,W &invalid)
27. {
28. //堆中存放的是结点,⽽⽐较⼤⼩的时候我们希望⽐较的是权值
29. struct NodeCompare
29. struct NodeCompare
30. {
31. bool operator()(const Node* left, const Node* right) const
32. {
33. return left->_w < right->_w;
34. }
35. };
36. Heap<Node*, NodeCompare> minHeap;
37.
38. for (size_t i = 0; i < n; i++)
39. {
40. //此处需要重载
41. if (a[i] != invalid)
42. {
43. Node* cur = new Node(a[i]);
44. minHeap.Push(cur);
45. }
46. }
47. Node* parent = NULL;
48. //根据权值⽣成⼩堆，选⼩堆中最⼩的两个数据⽣成⽗节点
49. while (minHeap.Size()>1)
50. {
51. Node* left = minHeap.Top();
52. minHeap.Pop();
53. Node* right = minHeap.Top();
54. minHeap.Pop();
55. Node* cur = new Node(left->_w + right->_w);
56. minHeap.Push(cur);
57. parent = cur;
58. parent->_lchild = left;
59. parent->_rchild = right;
60. left->_parent = parent;
61. right->_parent = parent;
62. }
63. _root = parent;
64. }
65.
66. Node* GetRoot()
67. {
68. return _root;
69. }
70. protected:
71. Node* _root;
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议