树的路径长度是从树根到每一个结点的路径长度（经过的边数）之和。
n个结点的一般二叉树，为完全二叉树时取最小路径长度PL=0+1+1+2+2+2+2+…
带权路径长度=根结点到任意结点的路径长度*该结点的权。树的带权路径长度是所有叶结点的带权路径长度和。
带权路径长度WPL最小的扩充二叉树则不一定是完全二叉树，而是权值大的外结点离根结点最近的扩充二叉树。
构造Huffman树需要使用最小堆，组织森林并从中选出根结点权值最小的两棵树，组成新结点（权值等于两棵树根结点权值之和）。
假如构造的不是扩充二叉树而是扩充n叉树，则需要补充若干权值为0的结点，使得外部结点个数=内部结点个数*(n-1)+1。
最优二进制编码问题可以通过构造Huffman树解决。每个出现的字符都是一个独立的结点，权值为出现的频率或次数。最终可以得到哈夫曼编码，它是一种前缀编码（没有一个编码是另一个编码的前缀）。得到的WPL可以看成最终编码得到的二进制编码的长度。
得到的哈夫曼树不唯一（因为0代表坐子树还是右子树无规定）但带权路径相同且最优。
#include "heap.h"
const int DefaultSize=;
stract HuffmanNode{
float data;
HuffmanNode *leftChild,*rightChild,*parent;
HuffmanNode():leftChild(NULL),rightChild(NULl),parent(NULL){}
HuffmanNode(float elem,HuffmanNode *left=NULL,HuffmanNode *right=NULL,HuffmanNode *pr=NULL):data(elem),leftChild(left),rightChild(right),parent(pr){}
bool operator<=(HuffmanNode& R){return data<=R.data;}
bool operator>(HuffmanNode& R){return data>R.data;}
} class HuffmanTree{
public:
HuffmanTree(folat w[],int n);
~HuffmanTree(){deleteTree(root);}
protected:
HuffmanNode *root;
void deleteTree(HuffmanNode *t);
void mergeTree(HuffmanNode& ht1, HuffmanNode& ht2, HuffmanNode* &parent);
} HuffmanTree::HuffmanTree(folat w[],int n){
//给出n个权限w[0]~w[n-1],构造Huffman树
minHeap hp; //使用最小堆存放森林
HuffmanNode* parent,first,second,work;
for(int i=;i<n;i++){ //森林各棵树初始化
work.data=w[i];
work.leftChild=NULL;
work.rightChild=NULL;
hp.Insert(work);
}
for(int i=;i<n-;i++){ //执行n-1次mergeTree操作形成Huffman树
hp.RemoveMin(first);
hp.RemoveMin(second);
mergeTree(first,second,parent);
hp.Insert(parent);
}
root=parent;
} void HuffmanTree::mergeTree(HuffmanNode *bt1,HuffmanNode *bt2,HuffmanNode& *parent){
parent=new HuffmanNode;
parent->leftChild=bt1;
parent->rightChild=bt2;
parent->data=bt1->data+bt2->data;
bt1->parent=bt2->parent=parent;
}