huffman树的C++基本实现(小根堆+二叉树实现)
huffman树是堆的一种重要的应用，huffman树在编码领域也是有着重要的用途。
huffman树的基本实现思路：将所有结点的权值压到堆中，每次从堆中取出权值最小的两个结点(注意要从堆中删除它们)；再新建一个结点，将这两个结点的权值之和作为新结点的权值，并将这两个结点作为新结点的左右子树；再将新结点压入栈中；以此类推，直到堆中只剩一个结点为止，此时这个结点就是所生成的huffman树的树根。
实现程序：
#include <iostream>#include <string>#include <cstdio>#include <memory.h>using namespace std;struct HuffmanNode{int data;HuffmanNode* leftChild,*rightChild,*parent;} huffNode[100];/*********************************堆模块*******************************///下滑操作void siftDown(int start,int end){//将start号结点向下调整直到endint i=start,j=2*i;huffNode[0]=huffNode[i]; //用huffNode[0]来临时保存i结点的值while(j<=end){//有右孩子并且右孩子比左孩子小时将j保存右孩子if(j<end&&huffNode[j].data>huffNode[j+1].data) ++j;//比j号结点小时，不需调整if(huffNode[0].data<=huffNode[j].data) break;else{//向下调整huffNode[i]=huffNode[j];i=j;j=2*j;}}huffNode[i]=huffNode[0];}//向上调整的函数//将结点start调整到根结点1为止void siftUp(int start){int j=start,i=j/2;huffNode[0]=huffNode[j];while(j>0){if(huffNode[i].data<=huffNode[0].data)break;else{//向上调整工作huffNode[j]=huffNode[i];j=i;i=i/2;}}huffNode[j]=huffNode[0];}//插入操作的实现bool insert(int& num,HuffmanNode& temp){if(60000==num) return false;++num;huffNode[num]=temp;siftUp(num);return true;}//删除操作bool removeMin(int& num,HuffmanNode& temp){if(0==num)return false;//将根的信息通过参数返回temp=huffNode[1];huffNode[1]=huffNode[num]; //填补树根--num;siftDown(1,num); //将根结点下滑到尾部return true;}/********************************************************///求huffman树的算法HuffmanNode* HuffmanTree(int& numNode){HuffmanNode* parent,first,second,temp;int num=0; //记录堆中的结点个数//先将输入的结点值都插入堆中for(int i=0;i<numNode;++i){cin>>temp.data;temp.leftChild=0;temp.rightChild=0;temp.parent=0;insert(num,temp);}for(int i=0;i<numNode-1;++i){//取出堆中两个值最小的结点removeMin(num,first);removeMin(num,second);//将这两个结点所在的树以parent为根合成新的树parent=new HuffmanNode;HuffmanNode* pFir=new HuffmanNode;HuffmanNode* pSec=new HuffmanNode;//parent树的形成*pFir=first;*pSec=second;parent->leftChild=pFir;parent->rightChild=pSec;parent->data=pFir->data+pSec->data;pFir->parent=parent;pSec->parent=parent;//将新形成的树插入堆中insert(num,*parent);}return parent;}//中序递归访问二叉树void preOrder(HuffmanNode* r){if(r!=0){cout<<r->data<<" ";preOrder(r->leftChild); preOrder(r->rightChild); }}int main(){int numNode=0;cin>>numNode;HuffmanNode* root=HuffmanTree(numNode);preOrder(root);cout<<endl;}但刚开始的写代码中，成生的huffman树总是有错误，跟踪了下，原来是在将左右两个结点作为parent的左右孩子时，单纯地用parent->leftChild=&first和parent->leftChild=&second，没有考虑到赋给leftChild和rightChild的是地址，当下次removeMin将first和second的值改变时原来地址的内容会随之改变！因此，需要每次都新建空间申请，将first和second的值移到新的空间中，才不会受到下次first和second的值更改的影响。以后用指针还是要多加小心。