????????????????
????????n???????n?????????????????????????·???????С?????????????????????????????????????(Huffman Tree)??????????????·????????????????????????????
?????????????裺
????1.??????ù???????
????2.??????????????????????????????????
????3.????????????????У?????????
??????????????
????1.???????????ù????????????????????????????????????????????????n?????????????ù????????????н??2n-1?????????????????????????????????????????????±???????0??????????????????????
????2.??????????n-1???????????????????????С??????????????????????????????????????????????????????????С????????????????С?????????????????????????0????????′???????????????????С???????????????????????С??????????????????0??i??.???????n-1????????????????????ù????????????У??n????????????????????????n-1??????2????
????3.?????????????????????????????????????????y????????????????????????????????????????“0”???????“1”??????????棻???????????????????0?????????????????????????????????У???????????????????????
????4???????????????????????????????У?????“0”??????????????????????“1”????????????????????????????????????????0???????????????????????????????????????????????????????????????????????洢??????????????У????????????????????????????????????У???????????????????????
????????????
1 /***************************************
2 ????1.??????????????????????????
3 ??????????????????????????????
4 2.?????????????У?????????????
6 ****************************************/
7 #include<iostream>
8 #define MAX_MA 1000
9 #define MAX_ZF 100
10 using namespace std;
11
12 //???????????????
13 typedef struct
14 {
15     int weight;  //??????
16     int parent?? lchild?? rchild;//????????????????±?
17 }HTNode??*HuffmanTree;  //????????????????????????????
18
19 //?????????????????
20 typedef char **HuffmanCode;//???????????洢??????????
21
22 //??????????????0????С?????±?
23 void Select(HuffmanTree HT?? int n?? int &s1?? int &s2)
24 {
25     /*n????HT????????
26     */
27
28    //?????for????????н??????С????????
29     for (int i = 1; i <= n; i++)
30     {//????for?????????????0????
31         if (HT[i].parent == 0)
32         {
33             s1 = i;//s1??????i
34             break;//??????????????????
35         }
36     }
37     for (int i = 1; i <= n; i++)
38     {/*????for?????????н?????????С?????
39      ???????y???????0*/
40         if (HT[i].weight < HT[s1].weight && HT[i].parent == 0)
41             s1 = i;
42     }
43     //??????for??????н?????????С????????
44     for (int i = 1; i <= n; i++)
45     {//????for?????????????0?????????????s1
46         if (HT[i].parent == 0 && i != s1)
47         {
48             s2 = i;//s2??????i
49             break;//??????????????????
50         }
51     }
52
53     for (int i = 1; i <= n; i++)
54     {/*????for?????????н????????????С???????
55      ?y??????????s1???????0*/
56         if (HT[i].weight < HT[s2].weight && HT[i].parent == 0 && i!= s1)
57             s2 = i;
58     }
59
60 }
61
62 //???????????
63 void CreateHuffmanTree(HuffmanTree &HT?? int n)
64 {
65 /*-----------?????????-------------------------*/
66     if (n <= 1)
67         return;
68     int m = 2 * n - 1;
69     HT = new HTNode[m + 1];
70     for (int i = 1; i <= m; ++i)
71     {//??1~m?????е?????????????????±???????0
72         HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0;
73     }
74     for (int i = 1; i <= n; ++i)
75     {
76         cin >> HT[i].weight;//?????n???????????????
77     }