最优二叉树

基本概念

给定n个权值作为n的[叶子]结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

思路
将输入的每一个叶子节点权值存入数组arr[]中，并将每一个叶子节点建成一颗树，存入数组tree[]中，因为有n个叶子节点，所以建立最优二叉树需要n-1步，每次在arr[]数组中找到最小的两个值，建立一个新的节点，存入tree[]中，将新节点的权值存入arr[]中，最终建成一颗最优二叉树。

定义节点

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

建立最优二叉树

treenode *huffmanTree(int n) {  //n为叶子个数
    int index = 0;        
    for (int i = 0; i < n; ++i) {  //将每一个叶子节点建成一棵树，放入数组tree[]中
        treenode *p = new treenode;
        p->data = arr[i];   //arr[]中放着叶子节点的权值
        p->lch = NULL;
        p->rch = NULL;
        tree[index++] = p;
    }
    treenode *root = NULL;   //定义最优二叉树的根
    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) {//在数组tree[]中找到这两个值，建立新的节点
            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;//建立新的节点，存入数组tree[]中
        p->data = ch1->data + ch2->data;
        p->lch = ch1;
        p->rch = ch2;
        root = p;//更新根，直到建立完成
        tree[index++] = p;
        arr[i + 1] = p->data;//并将这个节点的权值传入数组arr[]中
    }
    return root;
}

计算权值WPL

结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

void weight(treenode *root, int n) {//n为树当前的层数，root为最优二叉树的根
    treenode *p = root;
    if(p != NULL) {
        if((p->lch) == NULL && (p->rch) == NULL) {//即当p为叶子节点时
            //cout << p->data << endl;
            w += n * (p->data);//w为最优二叉树的权值
        }
        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;
}