Haffman树

算法如下

(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;
  }
}

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据