静态链表实现：
#include<iostream> #include<vector> #include<string> using namespace std; const int maxWeight = 32767; struct HTNode { char data; int weight; int parent,lchild,rchild; }; struct HFTree { vector<HTNode>elem; int root; int num; // huffman树外结点个数 }; void createHFTree(HFTree &HT,string value,vector<int>fr) {//输入数据value[n]和 相应权值fr[n],构造用三叉链表表示的Huffman树HT int min1,min2; HT.elem.resize(value.length()*2-1); //huffman是一颗正则二叉树，有2*n-1个结点 for(int i = 0; i < value.length(); i++) { HT.elem[i].data = value[i]; HT.elem[i].weight = fr[i]; } for(int i = 0; i < 2*value.length()-1; i++) { HT.elem[i].parent = HT.elem[i].lchild = HT.elem[i].rchild = -1; } int s1,s2; for(int i = value.length(); i < 2*value.length() - 1 ; i++) //循环n-1次,因为还有 { //n-1个结点要添加 min1 = min2 = maxWeight; s1 = s2 = 0; for(int k = 0;k < i; k++) { if(HT.elem[k].parent == -1) { if(HT.elem[k].weight < min1 ) //最小 { min2 = min1; s2 = s1; min1 = HT.elem[k].weight; s1 = k; } else if(HT.elem[k].weight < min2) //次小 { min2 = HT.elem[k].weight; s2 = k; } } } HT.elem[s1].parent = HT.elem[s2].parent = i; HT.elem[i].lchild = s1; HT.elem[i].rchild = s2; HT.elem[i].weight = HT.elem[s1].weight + HT.elem[s2].weight; } HT.num = value.length(); HT.root = 2*value.length() - 2; } int main() { string values = "ABCDE"; vector<int> fr = {7,5,2,4,6}; HFTree HF; createHFTree(HF,values,fr); for(int i = 0; i < HF.elem.size(); i++) { cout<<HF.elem[i].data<<" parent is "<<HF.elem[i].parent<<" lchild is "<<HF.elem[i].lchild<<" rchild is "<<HF.elem[i].rchild <<" weight is "<<HF.elem[i].weight<<endl; } return 0; }二叉链表实现：
#include<iostream> #include<vector> #include<string> #include<queue> using namespace std; struct Node { char data; double weight; Node *lchild,*rchild; Node(char _data,double _weight) { data = _data; weight = _weight; lchild = rchild = NULL; } }; class cmp { public: bool operator()(const Node *n1,const Node *n2) const { return n1->weight > n2->weight; } }; void createHuffmanTree(Node *&root,string values,vector<double>weights) { if(values.length() <= 0) { root = NULL; return ; } priority_queue<Node*,vector<Node*>,cmp> q; //优先队列 for(int i = 0; i < values.length(); i++) { Node *newNode = new Node(values[i],weights[i]); q.push(newNode); } for(int i = 0; i < values.length() - 1; i++) //循环n-1次，加n-1个结点 {//因为huffman树是正则二叉树(只有度为2和0的结点),所以共2n-个结点,所以再加n-1个结点就够了 Node *x = q.top(); q.pop(); Node *y = q.top(); q.pop(); Node* cur = new Node('#',x->weight + y->weight); cur->lchild = x; cur->rchild = y; q.push(cur); } root = q.top(); } void printHuffmanCode(const Node *root,string code) { if(root->lchild == NULL && root->rchild == NULL) { cout<<root->data<<": huffman code is "<<code<<endl; } else { printHuffmanCode(root->lchild,code+"0"); printHuffmanCode(root->rchild,code+"1"); } } void printHuffmanTree(Node *root,int k) //这里是先打印水平打印，先打印的右子树再打左子树 { if(root != NULL) { printHuffmanTree(root->rchild,k+5); for(int i = 0; i < k; i++) { cout<<" "; } cout<<root->data<<endl; printHuffmanTree(root->lchild,k+5); } } int main() { string values = "abcde"; vector<double>weights = {0.05,0.20,0.35,0.30,0.10}; Node *root = NULL; createHuffmanTree(root,values,weights); printHuffmanCode(root,""); printHuffmanTree(root,0); return 0; }(注：huffman编码树的形态不一定是一样的，因为同一层左右子女位置可以交换，这里实现的weight小的在左边，大的在右边。
===========================================================
