Huffman树实现文件压缩

【问题描述】给定一个文件，文件由n个字符组成，但他们出现的频度不相同。要求对该文件中的字符集构造哈夫曼树，并计算编码后的文件长度。
【输入形式】

输入的第1行有1个数字n，表示文件中总的字符个数。接下来1行中有n个数字，分别表示n个字符出现的频度。
【输出形式】

输出1行包含1个数字，表示使用哈夫曼编码后该文件的长度。
【样例输入】

5

20 7 10 4 18
【样例输出】

129
【样例说明】

使用哈夫曼编码后，各字符的编码长度分别为2 3 2 3 2，文件长度为2*20+3*7+2*10+3*4+2*18=129

注意事项:

①已经在结构体内部重载了"<",在声明堆(优先队列)时不需要再使用less,greater了

②在堆中取出结点时,注意每次都要new 出一个新的结点,而不是指向堆中的结点,因为堆中的结点的指针在函数执行完毕之后就释放了

错误的Huffman函数:

void Huffman() {
    for(int i = 1; i <= n; i++)
        printf("访问节点%d, value=%d\n", i, Huf[i].value);

    priority_queue <HuffmanNode> heap;

    for(int i = 1; i <= n; i++)
        heap.push(Huf[i]);

    priority_queue<HuffmanNode> tempheap = heap;

    while(tempheap.size()) {
        HuffmanNode t = tempheap.top();
        tempheap.pop();
        printf("heap:访问节点value=%d\n", t.value);
    }

    while(heap.size() > 1) {
        HuffmanNode* h1 = new HuffmanNode(heap.top());
        heap.pop();
        HuffmanNode* h2 = new HuffmanNode(heap.top());
        heap.pop();

        HuffmanNode t;
        t.value = h1->value + h2->value;
        t.LChild = h1;
        t.RChild = h2;
        printf("新构建结点t的左孩子的值为:%d, 右孩子的值为:%d\n", (t.LChild)->value, (t.RChild)->value);
        printf("value:取出的两个结点值为%d和%d, 新构建的结点t的值为%d\n", h1->value, h2->value, t.value);
        heap.push(t);
    }

正确代码:?

#include<iostream>
#include<queue>
using namespace std;
const int N=100;
int n,ans;
struct HuffmanNode
{
	int value,h;
	HuffmanNode* LChild,*RChild;
	bool operator<(const HuffmanNode &H)const
	{
		return value>H.value;
	}
	HuffmanNode():LChild(NULL),RChild(NULL),value(0),h(0) {}
}Huf[N];
void getHeight(HuffmanNode *root, int h) {
    if (root != NULL) {
//        printf("getHeight:访问节点value=%d\n", root->value);

        // 如果有左子树，递归处理左子树
        if (root->LChild != NULL) {
            getHeight(root->LChild, h + 1);
        }

        // 如果有右子树，递归处理右子树
        if (root->RChild != NULL) {
            getHeight(root->RChild, h + 1);
        }

        // 如果是叶子节点，设置深度
        if (root->LChild == NULL && root->RChild == NULL) {
            root->h = h;
            ans+=(root->value)*(root->h);
//            printf("叶子节点value=%d，深度=%d\n", root->value, root->h);
        }
    }
}


void Huffman() {
//    for(int i = 1; i <= n; i++)
//        printf("访问节点%d, value=%d\n", i, Huf[i].value);

    priority_queue <HuffmanNode> heap;

    for(int i = 1; i <= n; i++)
        heap.push(Huf[i]);

//    priority_queue<HuffmanNode> tempheap = heap;
//
//    while(tempheap.size()) {
//        HuffmanNode t = tempheap.top();
//        tempheap.pop();
//        printf("heap:访问节点value=%d\n", t.value);
//    }

    while(heap.size() > 1) {
        HuffmanNode* h1 = new HuffmanNode(heap.top());
        heap.pop();
        HuffmanNode* h2 = new HuffmanNode(heap.top());
        heap.pop();

        HuffmanNode t;
        t.value = h1->value + h2->value;
        t.LChild = h1;
        t.RChild = h2;
//        printf("取出的两个结点值为%d和%d, 新构建的结点t的值为%d\n", (t.LChild)->value, (t.RChild)->value);
        heap.push(t);
    }

    HuffmanNode t = heap.top();
    heap.pop();

    // 这里将 root 指向堆中的对象
    HuffmanNode* root = new HuffmanNode(t);

    getHeight(root, 0);

    // 记得释放动态分配的内存
    delete root;
}
/*
5

20 7 10 4 18
*/
int main()
{
	cin>>n;
		
	for(int i=1;i<=n;i++)
		scanf("%d",&Huf[i].value);
	
	Huffman();
		
	printf("%d\n",ans);
	
	return 0;
}