首先我们看看基本定义
哈夫曼树的学术定义为,带权路径长度最短的二叉树,即节点具有两个属性:
1、权值,可以看作节点表达出的数值大小,或者变换的表示为概率大小
2、路径,可以看作由根节点到达当前节点的分支数,左分支和右分支具有不同意义
带权路径长度即为权值与路径乘积的累加,所以哈夫曼树首先是一棵二叉树,其次通过调整二叉树节点位置,使得带权路径长度最小。
综上也就是把每个节点合并为根节点的左右节点,且每次选择合并时要使得根节点最小。哈夫曼树是从根部往下走越来越小
A
此图片较好说明了生成步骤可以参考理解
直接上代码
#include<iostream>
#include <vector>
#include<queue>
#include <functional>
using namespace std;
struct node
{
int data;
node*ltree;
node*rtree;
node()
{
ltree = rtree = NULL;
}
node(int data)
{
this->data = data;
ltree = rtree = NULL;
}
};
struct Huffmantree
{
node *root;
Huffmantree(){
root = NULL;
}
Huffmantree(int weight){ root = new node(weight); }
Huffmantree(vector<Huffmantree>&nodes)
{
Huffmantree tmp;
priority_queue<Huffmantree, vector<Huffmantree>, greater<Huffmantree>>q(nodes.begin(), nodes.end());
for (int i = 1; i<nodes.size();i++)
{
tmp.root = new node;
tmp.root->ltree = q.top().root; q.pop();
tmp.root->rtree = q.top().root; q.pop();
tmp.root->data = tmp.root->ltree->data + tmp.root->rtree->data;
q.push(tmp);
}
root = q.top().root;
}
bool operator >(const Huffmantree &t)const{
return this->root->data > t.root->data;
}
void print()
{
rprint(root, 0);
}
void rprint(node *r,int depth)
{
for (int i = 0; i < depth;i++)
{
cout << " ";
}
if (!r)
{
cout << "[/]"<< endl;
}
else
{
cout << r->data << endl;
rprint(r->ltree, depth + 1);
rprint(r->rtree, depth + 1);
}
}
};
void main()
{
int nv, weight;
cin >> nv;
vector<Huffmantree>nodes;
for (int i = 0; i < nv;i++)
{
cin >> weight;
nodes.emplace_back(weight);
}
Huffmantree ht(nodes);
ht.print();
system("pause");
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)