-
编程语言
站-
热门城市 全国站>
-
其他省市
-
-
400-636-0069
Vivian
2018-06-19
来源 ：
阅读 690
评论 0
摘要：本文主要向大家介绍了如何使用C++语言模板实现哈夫曼树，通过具体的内容向大家展现，希望对大家学习C++语言有所帮助。
本文主要向大家介绍了如何使用C++语言模板实现哈夫曼树，通过具体的内容向大家展现，希望对大家学习C++语言有所帮助。
C++模板实现哈夫曼树
哈夫曼树（霍夫曼树）又称为最优树.
1、路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长
度为L-1。
2、结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
3、树的带权路径长度
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
BinTreeNode.h
[cpp] view plain copy print?
1. template<typename Type> class BinaryTree;
2.
3. template<typename Type> void Huffman(Type *, int, BinaryTree<Type> &);
4.
5. template<typename Type> class BinTreeNode{
6. public:
7. friend class BinaryTree<Type>;
8. friend void Huffman<Type>(Type *, int, BinaryTree<Type> &);
9. BinTreeNode():m_pleft(NULL),m_pright(NULL){}
10. BinTreeNode(Type item,BinTreeNode<Type> *left=NULL,BinTreeNode<Type> *right=NULL)
11. :m_data(item),m_pleft(left),m_pright(right){}
12. void Destroy(){ //destroy the tree with the root of the node
13. if(this!=NULL){
14. this->m_pleft->Destroy();
15. this->m_pright->Destroy();
16. delete this;
17. }
18. }
19. Type GetData(){
20. return m_data;
21. }
22. BinTreeNode<Type> *Copy(const BinTreeNode<Type> *copy); //copy the node
23.
24. private:
25. BinTreeNode<Type> *m_pleft,*m_pright;
26. Type m_data;
27. };
28.
29. template<typename Type> BinTreeNode<Type>* BinTreeNode<Type>::Copy(const BinTreeNode<Type> *copy){
30. if(copy==NULL){
31. return NULL;
32. }
33.
34. BinTreeNode<Type> *temp=new BinTreeNode<Type>(copy->m_data);
35. temp->m_pleft=Copy(copy->m_pleft);
36. temp->m_pright=Copy(copy->m_pright);
37. return temp;
38. }BinaryTree.h
[cpp] view plain copy print?
1. #include "BinTreeNode.h"
2.
3. template<typename Type> void Huffman(Type *, int, BinaryTree<Type> &);
4.
5. template<typename Type> class BinaryTree{
6. public:
7.
8. BinaryTree(BinaryTree<Type> &bt1, BinaryTree<Type> &bt2){
9. m_proot = new BinTreeNode<Type>(bt1.m_proot->m_data
10. + bt2.m_proot->m_data, bt1.m_proot, bt2.m_proot);
11. }
12. BinaryTree(Type item){
13. m_proot = new BinTreeNode<Type>(item);
14. }
15. BinaryTree(const BinaryTree<Type> ©){
16. this->m_proot = copy.m_proot;
17. }
18. BinaryTree(){
19. m_proot = NULL;
20. }
21. void Destroy(){
22. m_proot->Destroy();
23. }
24. ~BinaryTree(){
25. // m_proot->Destroy();
26. }
27.
28. BinaryTree<Type>& operator=(BinaryTree<Type> copy); //evaluate node
29. friend void Huffman<Type>(Type *, int, BinaryTree<Type> &);
30. friend bool operator < <Type>(BinaryTree<Type> &l, BinaryTree<Type> & r);
31. friend bool operator > <Type>(BinaryTree<Type> &l, BinaryTree<Type> & r);
32. friend bool operator <= <Type>(BinaryTree<Type> &l, BinaryTree<Type> & r);
33. friend ostream& operator<< <Type>(ostream& ,BinaryTree<Type>&); //output the data
34. private:
35. BinTreeNode<Type> *m_proot;
36. void Print(BinTreeNode<Type> *start,int n=0); //print the tree with the root of start
37. };
38.
39. template<typename Type> bool operator <(BinaryTree<Type> &l, BinaryTree<Type> &r){
40. return l.m_proot->GetData() < r.m_proot->GetData();
41. }
42.
43. template<typename Type> bool operator >(BinaryTree<Type> &l, BinaryTree<Type> &r){
44. return l.m_proot->GetData() > r.m_proot->GetData();
45. }
46.
47. template<typename Type> bool operator <=(BinaryTree<Type> &l, BinaryTree<Type> &r){
48. return l.m_proot->GetData() <= r.m_proot->GetData();
49. }
50.
51.
52. template<typename Type> void BinaryTree<Type>::Print(BinTreeNode<Type> *start, int n){
53. if(start==NULL){
54. for(int i=0;i<n;i++){
55. cout<<" ";
56. }
57. cout<<"NULL"<<endl;
58. return;
59. }
60. Print(start->m_pright,n+1); //print the right subtree
61. for(int i=0;i<n;i++){ //print blanks with the height of the node
62. cout<<" ";
63. }
64. if(n>=0){
65. cout<<start->m_data<<"--->"<<endl;//print the node
66. }
67. Print(start->m_pleft,n+1); //print the left subtree
68. }
69.
70. template<typename Type> ostream& operator<<(ostream& os,BinaryTree<Type>& out){
71. out.Print(out.m_proot);
72. return os;
73. }
74.
75. template<typename Type> BinaryTree<Type>& BinaryTree<Type>::operator=(BinaryTree<Type> copy){
76. m_proot=m_proot->Copy(copy.m_proot);
77. return *this;
78. }MinHeap.h
[cpp] view plain copy print?
1. template<typename Type> class MinHeap{
2. public:
3. MinHeap(Type heap[],int n); //initialize heap by a array
4. ~MinHeap(){
5. delete[] m_pheap;
6. }
7.
8. public:
9. bool Insert(const Type item);
10. bool DeleteMin(Type &first);
11.
12. private:
13. void Adjust(const int start, const int end); //adjust the elements from start to end
14.
15.
16. private:
17. const int m_nMaxSize;
18. Type *m_pheap;
19. int m_ncurrentsize;
20. };
21.
22. template<typename Type> void MinHeap<Type>::Adjust(const int start, const int end){
23. int i = start,j = i*2+1;
24. Type temp=m_pheap[i];
25. while(j <= end){
26. if(j<end && m_pheap[j]>m_pheap[j+1]){
27. j++;
28. }
29. if(temp <= m_pheap[j]){
30. break;
31. }
32. else{
33. m_pheap[i] = m_pheap[j];
34. i = j;
35. j = 2*i+1;
36. }
37. }
38. m_pheap[i] = temp;
39. }
40.
41. template<typename Type> MinHeap<Type>::MinHeap(Type heap[], int n):m_nMaxSize(n){
42. m_pheap = new Type[m_nMaxSize];
43. for(int i=0; i<n; i++){
44. m_pheap[i] = heap[i];
45. }
46. m_ncurrentsize = n;
47. int pos=(n-2)/2; //Find the last tree which has more than one element;
48. while(pos>=0){
49. Adjust(pos, n-1);
50. pos--;
51. }
52. }
53.
54. template<typename Type> bool MinHeap<Type>::DeleteMin(Type &first){
55. first = m_pheap[0];
56. m_pheap[0] = m_pheap[m_ncurrentsize-1];
57. m_ncurrentsize--;
58. Adjust(0, m_ncurrentsize-1);
59. return 1;
60. }
61.
62. template<typename Type> bool MinHeap<Type>::Insert(const Type item){
63. if(m_ncurrentsize == m_nMaxSize){
64. cerr<<"Heap Full!"<<endl;
65. return 0;
66. }
67. m_pheap[m_ncurrentsize] = item;
68. int j = m_ncurrentsize, i = (j-1)/2;
69. Type temp = m_pheap[j];
70. while(j > 0){
71. if(m_pheap[i] <= temp){
72. break;
73. }
74. else{
75. m_pheap[j] = m_pheap[i];
76. j = i;
77. i = (j-1)/2;
78. }
79. }
80. m_pheap[j] = temp;
81. m_ncurrentsize++;
82. return 1;
83. }Huffman.h
[cpp] view plain copy print?
1. #include "BinaryTree.h"
2. #include "MinHeap.h"
3.
4. template<typename Type> void Huffman(Type *elements, int n, BinaryTree<Type> &tree){
5. BinaryTree<Type> first, second;
6. BinaryTree<Type> node[20];
7. for (int i=0; i<n; i++){
8. node[i].m_proot = new BinTreeNode<Type>(elements[i]);
9. }
10. MinHeap<BinaryTree<Type> > heap(node, n);
11.
12. for (int i=0; i<n-1; i++){
13. heap.DeleteMin(first);
14. heap.DeleteMin(second);
15.
16. //using the first and the second minimize element create new tree
17. if (first.m_proot->GetData() == second.m_proot->GetData()){
18. tree = *(new BinaryTree<Type>(second, first));
19. }
20. else {
21. tree = *(new BinaryTree<Type>(first, second));
22. }
23.
24. heap.Insert(tree);
25. }
26. }Main.cpp
[cpp] view plain copy print?
1. #include <iostream>
2.
3. using namespace std;
4.
5. #include "Huffman.h"
6.
7. int main(){
8. BinaryTree<int> tree;
9. int init[10]={3,6,0,2,8,4,9,1,5,7};
10. Huffman(init,10,tree);
11. cout << tree;
12. tree.Destroy();
13. return 0;
14. }以上就介绍了C/C+的相关知识，希望对C/C+有兴趣的朋友有所帮助。了解更多内容，请关注职坐标编程语言C/C+频道！
喜欢 | 1
不喜欢 | 0
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了，明天再试试吧！
我们会在第一时间安排职业规划师联系您！
您也可以联系我们的职业规划师咨询：
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com，All Rights Reserved.
沪公网安备 31011502005948号
索取资料
答疑解惑
技术交流
职业测评
面试技巧
高薪秘笈
