关于哈夫曼树的问题
求构造哈弗曼树的代码，且要每一行都写上注释
[解决办法]
[code=C/C++][/code]
//首先的定义二叉树类BinaryTree、优先权队列类PrioQueue和哈夫曼树类HfmTree,这两个类里具体的函数定义我就不打下来了
template<class T>
class PrioQueue
{
public:
PrioQueue(int mSize);
~PrioQueue(){delete []q;}
void Append(const T& x);
void Serve(T &x);
private:
void AdjustDown(int r,int j);
void AdjustUp(int j);
T* q;
int n, maxSize;
}
template<class T>
class HfmTree:public BinaryTree<T>
{
public:
operator T()const{return weigth;}
T getW(){return weigth;}
void putW(const T& x){weigth=x;}
SetNull(){root=NULL;}
private:
T weigth;
}
//构造哈夫曼树
template<class T>
HfmTree<T> CreatHfmTree(T w[],int n)//数组保存n个元素类型为T的权值，函数返回一颗构造成功的哈夫曼树
{
PrioQueue<HfmTree<T>>pq(n);//定义一个元素类型为HfmTree<T>的优先权队列
HfmTree<T>x, y, zero;
for(int i=0;i<n;i++)
{
z.MakeTree(w[i],x,y);//
z.putW(w[i]);//构造树中只有一个节点的哈夫曼对象
pq.Append(Z);//将哈夫曼树对象进优先权队列
z.SetNull();//将z置成空树
}
for(i=1;i<n;i++)
{
pq.Serve(x); pq.Serve()y;//取出最小和次小权值哈夫曼树对象x和y
z.MakeTree(x.getW()+y.getW(),x,y);//构造一个新哈夫曼树
z.putW(x.getW()+y.getW());
pa.Append(z);//新哈夫曼树对象进优先权队列
z.SetNull();//将z置成空树
}
pq.Serve()z;//从队列中取回构造完毕的哈夫曼树
return z;//返回构造完成的哈夫曼树对象
}
