算法如下
(1)找到队列里权值最小的两个节点，最小的为左儿子，次小的为右儿子。
(2)新建节点，将左右儿子赋值后，将其权值赋值为左右之和。
(3)将节点加入队列
(4)若队列为空，则退出循环，建立完毕。
挑选最小的两个可以交给优先队列判断。
定义：
typedef struct BiTnode
{
TElemType data;
struct BiTnode * lchild, * rchild;
bool type = false;
int val;
} * BiTree;
struct cmp{
bool operator()(BiTnode *&a, BiTnode *&b) const
{
return a->data>b->data;
}
};
代码实现
void Huffmantree(int cnt, BiTree &T)
{
int Num[30];string s;
memset(Num,0,sizeof(Num));
srand((int)time(nullptr));
for(int i=0;i<cnt;i++) s+=(char)('a'+rand()%26);//随机生成串
for(char i : s) Num[i-'a']++;
for(int i=0;i<26;i++) cout<<Num[i]<<' ';
cout<<endl<<s<<endl;
priority_queue<BiTree,vector<BiTree>,cmp>que;//建立优先队列
for(int i=0;i<26;i++)
{
auto tmp = (BiTree)malloc(sizeof(BiTnode));//建立叶子节点
tmp -> data = Num[i];tmp->type = true;//依照出现的次数为权值
tmp -> val = i;
tmp->lchild = nullptr; tmp->rchild = nullptr;
if(tmp->data) que.push(tmp);//如果出现了，则加入队列
}
cout<<"====================="<<endl;
auto now = (BiTree)malloc(sizeof(BiTnode));//新建头节点
while(!que.empty())
{
BiTree q1 = que.top();que.pop();if(que.empty()){break;}//特判如果是最后一个节点，退出
BiTree q2 = que.top();que.pop();
now->lchild = q1; now->rchild = q2; now->data = q1->data+q2->data;
que.push(now); T = now;
now = (BiTree)malloc(sizeof(BiTnode));
}
struct no
{
BiTree node;
string way;
};
queue<no>Q; Q.push((no){T,""});//解码
while(!Q.empty())
{
no tmp = Q.front();Q.pop();
if(tmp.node->lchild)
{
Q.push((no){tmp.node->lchild,tmp.way+"0"});//左儿子路径加入0，????儿子路径加入1
Q.push((no){tmp.node->rchild,tmp.way+"1"});
}
else
cout<<tmp.way<<' '<<(char)(tmp.node->val+'a')<<endl;
}
}