数据结构-二叉树（6）哈夫曼树（Huffman树）/最优二叉树

树的路径长度是从树根到每一个结点的路径长度（经过的边数）之和。

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;

}