// haffman.cpp : 定义控制台应用程序的入口点。

 //

 #include "stdafx.h"

 #include<iostream>

 using namespace std;

 typedef struct hfnode

 {

     char ch;      //存储字符

     int weight;   //存储权值

     int parent;   //双亲结点位置

     int lchild;   //左右孩子结点位置

     int rchild;

 } hfnode,*hfmtree;

 typedef struct node

 {

     char code[];

 } node,*hfcode;

 #define Nsymbols 10

 hfnode *Inithfm(hfnode *tree,int n)  //千万不能用关键字命名。把这些节点作为带权值的二叉树的根节点，左右子树为空

 {

     //tree = new hfnode[n]; //多余了，已经在main函数中声明了。

     for(int i = ;i < n; i++)

     {

         tree[i].ch = '';

         tree[i].weight = ;

         tree[i].lchild = ;

         tree[i].rchild = ;

         tree[i].parent = ;

     }

     cout << "请输入想要编码的字符序列,按照先字符后次数的顺序输入" << endl;

     for(int i = ;i < ; i++)

     {

         cin >> tree[i].ch >>tree[i].weight;

     }

      cout <<endl; 

     for(int i = ;i < ;i++)

         cout << tree[i].ch << " "<<tree[i].weight<<" ";

     cout << endl;

     return tree;

 }

 void select(hfnode *tree,int n,int *p1,int *p2) //选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。

 {

     //找一个作为参考,返回的是结点

     int x,y;

     for(int i = ;i <= n;i++)

     {

         if(tree[i].parent==)

         {

             x = i;

             break;//找到一个参考点即可

         }

     }

     for(int i = ;i <= n;i++)  //找出最小的结点

     {

         if((tree[i].parent==)&&(tree[i].weight!=))

         {

             if(tree[i].weight < tree[x].weight)

                 x = i;

         }

     }

    for(int j = ;j <= n;j++)

     {

         if((tree[j].parent==)&&(j!=x))

         {

             y = j;

             break;//找到一个参考点即可

         }

     }

    for(int j = ;j <= n;j++)   //找出次小的结点

     {

         if((tree[j].parent==)&&(tree[j].weight!=)&&j!=x)

         {

             if(tree[j].weight < tree[y].weight)

                 y = j;

         }

     }

        *p1 = x;

        *p2 = y;

 }

 //对哈弗曼树进行编码。

 void HfCode(hfnode *tree,int n,node *hfmcode,int m)

 {

      int c,f;

      int start = ;

      for(int i=;i<;i++)

      {

          for(c=i,f=tree[c].parent;f!=;c=f,f=tree[c].parent) //追溯法，从叶子节点出发，一路往上追溯。

          {

              if(tree[f].lchild==c)

                  hfmcode[i].code[start++] = '';

              else

                  hfmcode[i].code[start++] = '';

          }

          start = ;

      }

 }

 void Print(node *hfmcode,int m)

 {

     for(int i = ;i < m;i++)

     {

         for(int j = ;j < m;j++)

           cout <<hfmcode[i].code[j];

         cout << endl;

     }

     cout << endl;

 }

 int main()

 {

     int p1=,p2=; //为了接收最小和次小的两个节点

     hfnode tree[Nsymbols]; //当我们不是用指针，这种情况下，已经全部赋值了。不用再一次赋值了。

     Inithfm(tree,Nsymbols); //初始化结构体数组。

     //建立哈弗曼树

     for(int m = ;m < *-;m++) //二叉树性质

     {

         select(tree,m-,&p1,&p2);

         tree[p1].parent = m;

         tree[p2].parent = m;

         tree[m].lchild = p1;

         tree[m].rchild = p2;

         tree[m].weight = tree[p1].weight + tree[p2].weight;

         tree[m].parent =; //其实这句也可以不用，因为初始化时已经初始化为0了。

     }

    node hfmcode[];

 // 初始化，不然打印的时候会出现未知错。

    for(int i = ;i < ;i++)

     {

         for(int j = ;j < ;j++)

          hfmcode[i].code[j]='\0';

     }

    HfCode(tree,Nsymbols,hfmcode,); //编码函数

    Print(hfmcode,);  //打印函数

     return ;

 }