Huffman算法实现最优二叉树（C++）

r囧r小猫 2022-06-10 10:09 114阅读 0赞

template<class Type> class node{
    	public:
    	    node():left(0),right(0){}
    	    ~node(){}
    	    void setorder(int q=0):order(q){}
    	    void setdata(Type x,int first=0,int second=0)
       	    {
    		   data=x;
    		   left=first;
    	 	   right=second;
    	    }
    	    friend int oprator>(node<Type>x,node<Type>y){return x.data>y.data;}
    	    friend int oprator>=(node<Type>x,node<Type>y){return x.data>=y.data;}
    	    friend int oprator==(node<Type>x,node<Type>y){return x.data==y.data;}
    	    friend int oprator<(node<Type>x,node<Type>y){return x.data<y.data;}
    	private:
    		int order;//叶结点从1开始的序号，用于标志本结点 
    		Type data;//保存本结点的权值
    		int left,right;//保存本结点的左、右儿子的下标地址
    		 
    	
    };
    
    template<class Type>
    void BestBinaryTree(Type weight[],int n,node<Type>BestBinaryTree[],int m){
    	//weight[1]~weight[n]保存权值，weight[0]不用。BestBinaryTree[1]到BestBinaryTree[2n-1] 
    	//保存最优二叉树，BestBinaryTree[0]不用，m应为2n-1
    	node<Type> *minptr=new node<Type>;//暂存最小值用。
    	MinHeap<node<Type> >MinHp(n);//建立最小化堆，容量为n个单元，0号单元不用
    	int i,j=m;
    	for(j=1;j<=n;j++)
    	{
    		minptr->setdata(weight[j]);
    		minptr->setorder(j);
    		MinHp.Insert(*minptr);
    	} 
    	
    	for(j=n+1;j<=m;j++)
    	{
    		MinHp.Delete(*minptr);BestBinaryTree[k]=*minptr;
    		MinHp.Delete(*minptr);BestBinaryTree[k-1]=*minptr;
    		minptr->setdata(BestBinaryTree[k].data+BestBinaryTree[k-1].data,k,k-1);
    		minptr->setorder();
    		k-=2;
    		MinHp.Insert(*minptr);//内部结点bj插入最小化堆 
    	}
    	
    	MinHp.DeleteMin(*minptr);BestBinaryTree[1]=*minptr;//插入根结点 
    }