Huffman树

/*
* Huffman树结点定义
*/
struct Node
{
ElementType weight; // 结点的权值
struct Node *leftChild; // 结点的左指针
struct Node *rightChild; // 结点的右指针
};

/*
* 输出内存申请失败的消息
*/
void showFailureMessage()
{
printf("Memory allocate failure!\n");
exit(-);
} /*
* 根据数组获取数组的长度
*/
int getArrayLength(ElementType weights[])
{
} /*
* 对程序运行中申请的内存空间做事后处理
*/
void destroy(struct Node **)
{
} /*
* 为给定权值数组创建一个Huffman树，返回根结点指针
*/
Node * createHuffmanTree(ElementType weights[])
{
/* 根据传入的数组初始化 */
int arrayLength = getArrayLength(weights);
struct Node **nodePointerArray = (struct Node **)malloc(sizeof(struct Node *) * arrayLength);
if(nodePointerArray == NULL)
showFailureMessage();
for(int index = ; index < arrayLength; ++index) { // 初始化指针数组nodePointerArray，每个指针指向一个二叉树结点
nodePointerArray[index] = (struct Node *)malloc(sizeof(struct Node));
if(nodePointerArray[index] == NULL)
showFailureMessage();
nodePointerArray[index]->weight = weights[index]; // 是树中各结点权值与传入的数组weights中元素一一对应
nodePointerArray[index]->leftChild = nodePointerArray[index]->rightChild = NULL;
} /* 在初始化基础上进行(数组长度-1)次操作构造Huffman树 */
struct Node * rootNode = NULL;
for(int index = ; index < arrayLength; ++index) {
/* 找到自index后的最小值和次小值索引 */
int lowestIndex = index;
int lowSecondIndex = index + ;
for(int innerIndex = lowSecondIndex; innerIndex < arrayLength; ++innerIndex) {
if(nodePointerArray[innerIndex]->weight < nodePointerArray[lowestIndex]->weight) {
lowSecondIndex = lowestIndex;
lowestIndex = innerIndex;
} else if(nodePointerArray[innerIndex]->weight < nodePointerArray[lowSecondIndex]->weight) {
lowSecondIndex = innerIndex;
}
} /* 将最小值和次小值所对应的结点(或子树的根结点)生成一颗二叉树 */
rootNode = (struct Node *)malloc(sizeof(struct Node));
if(rootNode == NULL)
showFailureMessage();
rootNode->weight = nodePointerArray[lowestIndex]->weight + nodePointerArray[lowSecondIndex]->weight;
rootNode->leftChild = nodePointerArray[lowestIndex];
rootNode->rightChild = nodePointerArray[lowSecondIndex]; /* 此次生成二叉树后，对本次循环的索引值、最小值的索引值、次小值的索引值
* 所对应的结点做事后处理(此处巧用最小值和次小值所在结点需要移除) */
nodePointerArray[lowestIndex] = rootNode;
nodePointerArray[lowSecondIndex] = nodePointerArray[index];
nodePointerArray[index] = NULL;
}
destroy(nodePointerArray); return rootNode;
}

/**
* 由给定的编码Huffman树求得树中各字符编码的算法，并分析器复杂度
**/
void HuffmanCode(Node *root, int index)
{
static int code[SIZE]; // code存放字符编码，其长度等于树的深度
if(root != NULL) {
if(root->leftChild == NULL && root->rightChild == NULL) {
cout << "Weight：" << root->data << " coding：";
for(int in = ; in < SIZE; ++in) // 输出叶子结点的编码
cout << code[in];
count << endl;
} else {
code[index] = ;
HuffmanCode(root->leftChild, (index + )); // 对左子树搜索
code[index] = ;
HuffmanCode(root->rightChild, (index + )); // 对右子树搜索
}
}
}