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 = 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 }
