1 /*2  * Huffman树结点定义3  */4 struct Node5 {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  }