描述
构造一个具有n个外部节点的扩充二叉树，每个外部节点Ki有一个Wi对应，作为该外部节点的权。使得这个扩充二叉树的叶节点带权外部路径长度总和最小：
Min( W1 * L1 + W2 * L2 + W3 * L3 + „ + Wn * Ln) Wi:每个节点的权值。
Li:根节点到第i个外部叶子节点的距离。 编程计算最小外部路径长度总和。
输入
对于每组测试数据，第一行输入一个整数n，外部节点的个数。第二行输入n个整数，代表各个外部节点的权值。 2<=N<=100
输出
输出最小外部路径长度总和。
总时间限制: 1000ms内存限制: 65535kB
样例输入
3
1 2 3 
4
1 1 3 5
样例输出
9
17
提示
仅考查huffman树的建立，数据范围小，可以不需要使用堆结构. 不过鼓励使用第一题实现的堆来寻找最小和次小元素。

C语言代码：

#include <stdio.h>
#include <memory.h>
#define MAXINT 0x7FFFFFFF
#define MAX 200
int tt;
struct huffmanNode {
    int leftNode,rightNode,parent;
    int value;
} huffmanNodes[MAX * 2];
int traverseTree(int idx, int depth) {
    int sum = 0;
    int child = 0;
    if (huffmanNodes[idx - 1].leftNode) {
        sum += traverseTree(huffmanNodes[idx - 1].leftNode, depth + 1);
        child++;
    }
    if (huffmanNodes[idx - 1].rightNode) {
        sum += traverseTree(huffmanNodes[idx - 1].rightNode, depth + 1);
        child++;
    }
    if (!child) {
        sum = huffmanNodes[idx - 1].value * depth;
    }
    return sum;
}
int main () {
    int num;
    int result = 0;
    while (scanf("%d",&tt) != EOF) {
        memset(huffmanNodes,0,sizeof(huffmanNodes));
        for (int t = 0; t < tt; t++) {
            scanf("%d",&num);
            huffmanNodes[t].value = num;
        }
        for (int i = tt; i < tt * 2 - 1; i++) {
            int min1 = MAXINT, min2 = MAXINT;
            int minIdx1 = -1, minIdx2 = -1;
            for (int j = 0; j < i; j++) {
                if (huffmanNodes[j].parent)
                    continue;
                if (huffmanNodes[j].value < min1) {
                    min2 = min1;
                    minIdx2 = minIdx1;
                    min1 = huffmanNodes[j].value;
                    minIdx1 = j;
                } else if (huffmanNodes[j].value < min2) {
                    min2 = huffmanNodes[j].value;
                    minIdx2 = j;
                }
            }
            huffmanNodes[minIdx1].parent = i;
            huffmanNodes[minIdx2].parent = i;
            huffmanNodes[i].value = min1 + min2;
            huffmanNodes[i].leftNode = minIdx1 + 1;
            huffmanNodes[i].rightNode = minIdx2 + 1;
        }
        for (int i = 0; i < tt * 2 - 1; i++) {
            if (!huffmanNodes[i].parent) {
                result = traverseTree(i + 1,0);
                break;
            }
        }
        printf("%d\n",result);
    }
    return 0;
}

 

本文链接：http://bookshadow.com/weblog/2014/04/27/huffman-tree-weighted-path-length/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码