霍夫曼树程序.doc.doc

《霍夫曼树程序.doc.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

//演示程序二十六：“霍夫曼”树#include#includeconstintDefaultSize=20;/*声明“扩充二叉树”的类*/templateclassExtBinTree;//定义“扩充二叉树”的结点templateclassElement{friendclassExtBinTree;//友元类private:Typedata;/*数据域指针域*/Element*leftChild,*rightChild;public://构造函数：一个叶子结点，数据域空Element():leftChild(NULL),rightChild(NULL){}//构造函数：一个非叶子结点，数据域赋值Element(Typeitem,Element*left=NULL,Element*right=NULL):data(item),leftChild(left),rightChild(right){}//修改结点数据域的值voidSetData(constType&item){data=item;}//修改结点的左孩子指针voidSetLeft(Element*L){leftChild=L;}//修改结点的右孩子指针voidSetRight(Element*R){rightChild=R;}//返回结点数据域的值TypeGetData(){returndata;}};//定义“扩充二叉树”的类templateclassExtBinTree{private:Element*root;//二叉树的根指针public://无参构造函数ExtBinTree(){root=newElement;} //构造函数：把两棵扩充二叉树合并成//一棵扩充二叉树。根的数据域为两棵子//树的数据域之和。左右指针分别指向//两棵子树。ExtBinTree(ExtBinTreebt1,ExtBinTreebt2){root=newElement(bt1.GetRootData()+bt2.GetRootData(),bt1.root,bt2.root);}//成员函数：给根结点赋值voidSetRootData(Typex,Element*left,Element*right){root->SetData(x);root->SetLeft(left);root->SetRight(right);}//返回根结点数据域值TypeGetRootData(){returnroot->GetData();}//返回根结点地址Element*Getroot(){returnroot;}//前序遍历递归输出二叉树voidPreOrder(Element*p)const{if(p!=NULL){//输出根结点数据域cout<data<<'';//递归输出p的左子树PreOrder(p->leftChild);//递归输出p的右子树PreOrder(p->rightChild);}}//中序遍历递归输出二叉树voidInOrder(Element*p)const{ if(p!=NULL){InOrder(p->leftChild);cout<data<<'';InOrder(p->rightChild);}}};/**********定义“最小堆”********/templateclassMinHeap{private:Type*heap;//存放最小堆元素的数组intCurrentSize;//堆当前元素个数intHeapMaxSize;//堆元素个数上限//私有成员函数：只能由公有成员函数调用voidFilterDown(inti,intm);//从i到m自顶向下进行调整成为最小堆voidFilterUp(inti);//从i到0自底向上进行调整成为最小堆public:MinHeap(){}//无参构造函数//构造函数：建立最小堆MinHeap(Typearr[],intn);~MinHeap(){delete[]heap;}//删除堆顶元素boolRemoveMin(Type&x);//向最小堆插入一个元素boolInsert(constTypex);boolIsEmpty()const//判堆空否{returnCurrentSize==0;}};//构造函数：建立最小堆templateMinHeap::MinHeap(Typearr[],intn){//根据给定数组中的数据和大小,建立堆对象HeapMaxSize=DefaultSize=0){//对子树进行自顶向下调整，形成子堆。FilterDown(currentPos,CurrentSize-1);//从currentPos开始,到数组末尾止,调整currentPos--;}}//对以序号start为根结点的子树进行//自顶向下的调整，使其成为最小堆。//参数EndOfHeap是子树里最后一个结点序号templatevoidMinHeap::FilterDown(intstart,intEndOfHeap){inti=start;intj=2*i+1;//j是i的左孩子Typetemp=heap[i];//暂存子树的根while(j<=EndOfHeap){//调整完？if(jheap[j+1].GetRootData())j++;//让j指向左右孩子中最小者if(temp.GetRootData()<=heap[j].GetRootData())break;//根结点不大于最小者，不调整else{heap[i]=heap[j];//上浮调整i=j;//向下滑动一层j=2*i+1;//j是i的左孩子}}heap[i]=temp;//根结点归位}//删除堆顶元素算法templateboolMinHeap::RemoveMin(Type&x){if(IsEmpty()){cout<<"堆已空"<boolMinHeap::Insert(constTypex){if(CurrentSize==HeapMaxSize){//堆满cerr<<"堆已满"<voidMinHeap::FilterUp(intstart){intj=start,i=(j-1)/2;//i是j的双亲Typetemp=heap[j];//暂存起点元素while(j>0){//调整到栈顶if(heap[i].GetRootData()<=temp.GetRootData())break;//不用调了else{//向上调整heap[j]=heap[i];j=i;i=(i-1)/2;}}heap[j]=temp;//起点元素归位}//**函数模板：建立霍夫曼树的算法**//templateExtBinTreeHuffmanTree(Type*fr,intn) /*频率数组数组长度*/{if(n>DefaultSize){cerr<<"大小n"<first,second;//first和second的合并树ExtBinTree*newtree;//具有n棵扩充二叉树的森林ExtBinTreeNode[DefaultSize];//每棵扩充二叉树Node[i]只有一个带权值//fr[i]的根结点,其左、右子树均为空。for(inti=0;i>hp(Node,n);//建立存储扩充二叉树森林的最小堆//hp.MinHeap(Node,n);//重复n-1趟,逐步形成霍夫曼树for(i=0;i(first,second);//重新插入到最小堆中hp.Insert(*newtree);}return*newtree;}//主函数voidmain(){//叶子结点的频率（权重）表intf[4]={2,7,4,5};intn=4;//叶子结点数目//生成霍夫曼树ExtBinTreeH=HuffmanTree(f,n);//前序、中序遍历霍夫曼树。根据输出就//可以画出霍夫曼树，进而手工给出编码。H.PreOrder(H.Getroot()); cout<<' ';H.InOrder(H.Getroot());//你也可以编写成员函数，//自动打印霍夫曼编码。想要一份//体面的工作，就try一下吧。}