基本概念

給定n個權值作為n的[葉子]結點浩销，構造一棵二叉樹膘侮，若帶權路徑長度達到最小适瓦，稱這樣的二叉樹為最優(yōu)二叉樹玄渗，也稱為哈夫曼樹(Huffman Tree)妻顶。哈夫曼樹是帶權路徑長度最短的樹条霜，權值較大的結點離根較近蛾绎。

思路
將輸入的每一個葉子節(jié)點權值存入數(shù)組arr[]中宋光，并將每一個葉子節(jié)點建成一顆樹情连，存入數(shù)組tree[]中叽粹，因為有n個葉子節(jié)點，所以建立最優(yōu)二叉樹需要n-1步却舀，每次在arr[]數(shù)組中找到最小的兩個值虫几，建立一個新的節(jié)點，存入tree[]中挽拔，將新節(jié)點的權值存入arr[]中辆脸，最終建成一顆最優(yōu)二叉樹。

定義節(jié)點

struct treenode {
    int data;      
    treenode *lch;    //左孩子
    treenode *rch;   //右孩子
};

建立最優(yōu)二叉樹

treenode *huffmanTree(int n) {  //n為葉子個數(shù)
    int index = 0;        
    for (int i = 0; i < n; ++i) {  //將每一個葉子節(jié)點建成一棵樹螃诅，放入數(shù)組tree[]中
        treenode *p = new treenode;
        p->data = arr[i];   //arr[]中放著葉子節(jié)點的權值
        p->lch = NULL;
        p->rch = NULL;
        tree[index++] = p;
    }
    treenode *root = NULL;   //定義最優(yōu)二叉樹的根
    for (int i = 0; i < n - 1; ++i) { //每次取arr[]中未使用的最小兩個值
        sort(arr + i, arr + n);
        treenode *ch1 = NULL, *ch2 = NULL;
        for (int j = 0; j < index; ++j) {//在數(shù)組tree[]中找到這兩個值啡氢，建立新的節(jié)點
            if(tree[j]->data == arr[i])
                ch1 = tree[j];
            if(tree[j]->data == arr[i + 1])
                ch2 = tree[j];
            if(ch1 && ch2) break;
        }
        treenode *p = new treenode;//建立新的節(jié)點，存入數(shù)組tree[]中
        p->data = ch1->data + ch2->data;
        p->lch = ch1;
        p->rch = ch2;
        root = p;//更新根术裸，直到建立完成
        tree[index++] = p;
        arr[i + 1] = p->data;//并將這個節(jié)點的權值傳入數(shù)組arr[]中
    }
    return root;
}

計算權值WPL

結點的權及帶權路徑長度
若將樹中結點賦給一個有著某種含義的數(shù)值倘是，則這個數(shù)值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積袭艺。
樹的帶權路徑長度
樹的帶權路徑長度規(guī)定為所有葉子結點的帶權路徑長度之和搀崭，記為WPL。

void weight(treenode *root, int n) {//n為樹當前的層數(shù)猾编，root為最優(yōu)二叉樹的根
    treenode *p = root;
    if(p != NULL) {
        if((p->lch) == NULL && (p->rch) == NULL) {//即當p為葉子節(jié)點時
            //cout << p->data << endl;
            w += n * (p->data);//w為最優(yōu)二叉樹的權值
        }
        weight(p->lch, n + 1);
        weight(p->rch, n + 1);
    }
}

C++代碼

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_N = 1e6;
int arr[MAX_N];
int w = 0;

struct treenode {
    int data;
    treenode *lch;
    treenode *rch;
};

treenode *tree[MAX_N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    treenode *root = NULL;
    root = huffmanTree(n);
    weight(root, 0);//注意0
    cout << w << endl;
    return 0;
}