Huffman树

1 /*
2  * Huffman树结点定义
3  */
4 struct Node
5 {
6     ElementType weight;         // 结点的权值
7     struct Node *leftChild;     // 结点的左指针
8     struct Node *rightChild;    // 结点的右指针
9 };

 1 /*
 2  * 输出内存申请失败的消息
 3  */
 4 void showFailureMessage()
 5 {
 6     printf("Memory allocate failure!\n");
 7     exit(-1);
 8 }
 9 
10 /*
11  * 根据数组获取数组的长度
12  */
13 int getArrayLength(ElementType weights[])
14 {
15 }
16 
17 /*
18  * 对程序运行中申请的内存空间做事后处理
19  */
20 void destroy(struct Node **)
21 {
22 }
23 
24 /*
25  * 为给定权值数组创建一个Huffman树，返回根结点指针
26  */
27 Node * createHuffmanTree(ElementType weights[])
28 {
29     /* 根据传入的数组初始化 */
30     int arrayLength = getArrayLength(weights);
31     struct Node **nodePointerArray = (struct Node **)malloc(sizeof(struct Node *) * arrayLength);
32     if(nodePointerArray == NULL)
33         showFailureMessage();
34     for(int index = 0; index < arrayLength; ++index) {    // 初始化指针数组nodePointerArray，每个指针指向一个二叉树结点
35         nodePointerArray[index] = (struct Node *)malloc(sizeof(struct Node));
36         if(nodePointerArray[index] == NULL) 
37             showFailureMessage();
38         nodePointerArray[index]->weight = weights[index]; // 是树中各结点权值与传入的数组weights中元素一一对应
39         nodePointerArray[index]->leftChild = nodePointerArray[index]->rightChild = NULL;
40     }
41 
42     /* 在初始化基础上进行(数组长度-1)次操作构造Huffman树 */
43     struct Node * rootNode = NULL;
44     for(int index = 0; index < arrayLength; ++index) {
45         /* 找到自index后的最小值和次小值索引 */
46         int lowestIndex = index;
47         int lowSecondIndex = index + 1;
48         for(int innerIndex = lowSecondIndex; innerIndex < arrayLength; ++innerIndex) {
49             if(nodePointerArray[innerIndex]->weight < nodePointerArray[lowestIndex]->weight) {
50                 lowSecondIndex = lowestIndex;
51                 lowestIndex = innerIndex;
52             } else if(nodePointerArray[innerIndex]->weight < nodePointerArray[lowSecondIndex]->weight) {
53                 lowSecondIndex = innerIndex;
54             }
55         }
56         
57         /* 将最小值和次小值所对应的结点(或子树的根结点)生成一颗二叉树 */
58         rootNode = (struct Node *)malloc(sizeof(struct Node));
59         if(rootNode == NULL)
60             showFailureMessage();
61         rootNode->weight = nodePointerArray[lowestIndex]->weight + nodePointerArray[lowSecondIndex]->weight;
62         rootNode->leftChild = nodePointerArray[lowestIndex];
63         rootNode->rightChild = nodePointerArray[lowSecondIndex];
64 
65         /* 此次生成二叉树后，对本次循环的索引值、最小值的索引值、次小值的索引值
66          * 所对应的结点做事后处理(此处巧用最小值和次小值所在结点需要移除) */
67         nodePointerArray[lowestIndex] = rootNode;
68         nodePointerArray[lowSecondIndex] = nodePointerArray[index];
69         nodePointerArray[index] = NULL;
70     }
71     destroy(nodePointerArray);
72 
73     return rootNode;
74 }

 1 /**
 2  * 由给定的编码Huffman树求得树中各字符编码的算法，并分析器复杂度
 3  **/
 4  void HuffmanCode(Node *root, int index)
 5  {
 6     static int code[SIZE];                                          // code存放字符编码，其长度等于树的深度
 7     if(root != NULL) {
 8         if(root->leftChild == NULL && root->rightChild == NULL) {
 9             cout << "Weight：" << root->data << " coding：";
10             for(int in = 0; in < SIZE; ++in)                        // 输出叶子结点的编码
11                 cout << code[in];
12             count << endl;
13         } else {
14             code[index] = 0;
15             HuffmanCode(root->leftChild, (index + 1));              // 对左子树搜索
16             code[index] = 1;
17             HuffmanCode(root->rightChild, (index + 1));             // 对右子树搜索
18         }
19     }
20  }