实验一最优二叉树及其应用
1．程序设计简介
本实验程序用于验证最优二叉树的算法。树的存储采用带孩子的双亲顺序存储方法。2．源程序
//最优二叉树
#include
#include
using namespace std;
//定义结点类型
template
struct hufnode
{
T wei;//权值
int prt;//指向父结点的指针域（结点元素的下标）
int lch;//左指针域（结点元素的下标）
int rch;//右指针域（结点元素的下标）
};
//由于数组下标一般是非负数整数，因此可以用-1作为空指针值
template
class huffman_BT
{
int nn;//叶子结点的个数
hufnode*BT;//最优二叉树顺序存储空间的首地址
public:
huffman_BT(){BT=NULL;}//构造函数，对最优二叉树进行初始化
void creat_hufm_BT(int n,T w[]);//生成最优二叉树
void select(hufnode*p,int k,int *i,int *j);
void prt_hufm_BT();//输出最优二叉树存储空间状、
};
//生成最优二叉树
template
void huffman_BT::creat_hufm_BT(int n,T w[])
{//n是叶子结点的个数，w是叶子结点的权值数组
hufnode *p;
int k,i,j,m;
nn=n;
m=n*2-1;
BT=new hufnode[m];//申请最优二叉树存储空间
p=BT;
for(k=0;k{//设置初始状态，所有结点的指针为空
(p+k)->prt=-1;
(p+k)->lch=-1;
(p+k)->rch=-1;
}
for(k=0;k{//前n个结点的权值分别为个结点的权值
(p+k)->wei=w[k];
}
for(k=n;k{//构造最优二叉树
select(p,k,&i,&j);//在前K-1个结点中选择权值最小的两个根结点i和j
(p+i)->prt=k;
(p+j)->prt=k;//合并构成新的二叉树
(p+k)->lch=i;
(p+k)->rch=j;
(p+k)->wei=(p+i)->wei+(p+j)->wei;
}
}
template
void huffman_BT::select(hufnode*p,int k,int *i,int *j)
{//在前K-1个结点中选择权值最小的两个根结点i和j
T w;
int n=0;
while(nprt!=-1) n++;//寻找指向父结点指针为空的起始结点
w=(p+n)->wei;
*i=n;
while(n{
if((((p+n)->wei)prt==-1))
{*i=n;
w=(p+n)->wei;
}n++;
}
n=0;
while((nprt!=-1)||(n==(*i))) n++;
w=(p+n)->wei;
*j=n;
while(n{
if(((p+n)->weiprt==-1))
{
*j=n;
w=(p+n)->wei;
}
n++;
}
if((*i)>(*j))
{
n=(*i);
*i=*j;
*j=n;
}
}
template
void huffman_BT::prt_hufm_BT()
{
hufnode *p;
int k;
p=BT;
cout<<"k"<<for(k=0;k<2*nn-1;k++)
{cout<wei<prt
<lch<rch<void main()
{
int *w;
int op;
int i;
huffman_BT b;
do
{
cout<<"1-输入结点权值"<cout<<"2-生成最优二叉树"<cout<<"3-退出程序"<cout<<"请选择操作：[ ]";
cout<<"\b\b";
cin>>op;
switch(op)
{
case 1:
cout<<"请输入结点的个数：";
int sum;
cin>>sum;
w=new int[sum];
cout<<"请依次输入权值："<for(i=0;i
