1 //最优二叉树  2 #include <iostream>  3 #include <iomanip>  4 using namespace std;  5   6 //定义结点类型  7 //【weight | lchid | rchild | parent】   8 //为了判定一个结点是否已加入到要建立的哈夫曼树中  9 //可通过parent域的值来确定. 10 //初始时parent = -1，当结点加入到树中时，该结点parent的值 11 //为其父亲结点在数组Huffman中的序号.  12 template<typename T> 13 struct HuffNode { 14     T weight;             //权值 15     int parent;           //指向父节点的指针域(结点元素的下标) 16     int lch;              //左指针域 17     int rch;              //右指针域  18 };  19  20 //哈夫曼树的构造算法  21 template<typename T> 22 HuffNode<T> *HuffmanTree(int n, const T& sign)     //生成最优二叉树 23 { 24     const int MAX_VALUE = http://www.mamicode.com/100000; 25     int i, j, min1, min2, x1, x2;                  //min1为最小值, min2为次小值, x1位最小值下标, x2位次小值下标  26     HuffNode<T> *ht = new HuffNode<T>[2 * n - 1];  //一个含有n个叶子结点的最优二叉树，总共有2*n-1个结点 27     HuffNode<T> *huffNode = ht; 28     for (i = 0; i < 2 * n - 1; i++)                //最优二叉树结点数组初始化  29     { 30         huffNode[i].weight = 0;         //权值都设为0 31         huffNode[i].parent = -1;        //父节点，左右孩子结点  32         huffNode[i].lch = -1; 33         huffNode[i].rch = -1;           //都设置为-1,-1代表空  34     }  35     for (i = 0; i < n; i++)             //依次输入n个叶子结点的权值  36         cin >> huffNode[i].weight; 37      38     for (i = 0; i < n - 1; i++) 39     {  40         min1 = min2 = MAX_VALUE;      41         // x1, x2 用来保存找到的两个最小结点在数组中的位置  42         x1 = x2 = 0;   43         for (j = 0; j < n + i; j++) //因为外循环每循环一次，实际结点个数增加到n+i个  44         { 45             if (huffNode[j].weight < min1 && huffNode[j].parent == -1) 46             { 47                 min2 = min1;                    //存在权值小于min1, 则min1赋值给次小值  48                 x2 = x1;                        //次小值下标改变  49                  min1 = huffNode[j].weight;      //当前权值赋值给最小值  50                 x1 = j;                         //并保存最小值下标  51             } 52             else if (huffNode[j].weight < min2 && huffNode[j].parent == -1) 53             { 54                 min2 = huffNode[j].weight;      //当前值赋值给次小值  55                 x2 = j;                         //保存次小值下标  56             } 57         } 58         //将找出的两个子树合并成一颗子树 59         //对找到的两个最小结点的父指针域进行赋值  60         huffNode[x1].parent = n + i;     61         huffNode[x2].parent = n + i; 62         //新合成树位置上的权值  63         huffNode[n + i].weight = huffNode[x1].weight + huffNode[x2].weight;  64         //两个最小结点的父结点的左右孩子域进行操作  65         huffNode[n + i].lch = x1; 66         huffNode[n + i].rch = x2;         67     } 68     return ht; 69 }  70  71 template<typename T> 72 void ShowHTree(HuffNode<T> *HT, int nodeNum) 73 { 74     HuffNode<T> *p = HT; 75     int k;     76     cout << "k" << "\t\t" << "Weight" << "\t\t" << "Parent"  77          << "\t\t" << "Lchild" << "\t\t" << "Rchild" << endl; 78     for (k = 0; k < 2 * nodeNum - 1; k++) 79     { 80         cout << k << "\t\t" << (p + k)->weight << "\t\t" 81              << (p + k)->parent << "\t\t"  82              << (p + k)->lch << "\t\t" << (p + k)->rch << endl; 83     } 84 }  85  86 /*************************编码*******************************/ 87  88 const int MAXBIT = 50;     //定义Huffman编码的最大长度  89  90 //对于第i个字符，它的Huffman编码存放在Huffman[i].bit中的 从 Huffman[i].start 到 n 的分量中  91 struct HCodeType { 92     int bit[MAXBIT];         //用来保存字符 的 Huffman编码 93     int start;               //start表示该编码在bit中的开始位置 94 }; 95   96 void HuffmanCode(int n) 97 { 98     const int MAXODE = 50, MAXLEAF = 50;      //最大编码长度，最多叶子数         99     HuffNode<int> *huffNode;                  //用于 生成Huffman 编码100     HCodeType *huffCode, cd;      101     int i, j, c, par, sign = 0;102     103     huffNode = HuffmanTree(n, sign);          //建立Huffman树 104     105     huffCode = new HCodeType[n];              //初始化HuffCode 106     for (int k = 0; k < n; k++) 107         huffCode[k].bit[i] = 0;108     109     ShowHTree(huffNode, n);110     111     /**********************编码过程*************************/112     for (i = 0; i < n; i++)                   //n--是叶结点数，不是全部结点数 113     {114         cd.start = n - 1;                     //从叶结点开始 115         c = i;                                //c为 i的工作指针，以防误操作修改了 i 116         par = huffNode[c].parent;              117         while (par != -1)                     //由叶结点向上直到树根 118         {119             if (huffNode[par].lch == c)       //右子树编号 == c ==> 右是0标志 120                 cd.bit[cd.start] = 0;         121             else                              //左是 1 标志 122                 cd.bit[cd.start] = 1; 123             cd.start--;                      //开始位置向前    124             c = par;                         //得到父亲结点的下标 125             par = huffNode[c].parent;        //由叶结点向上直到树根 -- 得到父级点的父亲结点 126         }127         for (j = cd.start + 1; j < n; j++)   //保存求出的每个叶结点的哈夫曼编码和编码的起始位 128         {129             huffCode[i].bit[j] = cd.bit[j]; 130         }       131         huffCode[i].start = cd.start;        //设置编码的开始位置 132     }133     134     //输出 135     for (i = 0 ; i < n; i++)                 //输出每个叶子结点的哈夫曼编码 136     {137         for (j = huffCode[i].start + 1; j < n; j++) {138             cout << huffCode[i].bit[j] ;139         }140         cout << endl;141     }    142 }143 144 int main()145 {146     int n;147 148     cout << "请输入叶子结点个数: " << endl;149     cin >> n;150 151     HuffmanCode(n);152     153     system("pause");154     155     return 0;156 }