数据结构—最优二叉树及其应用

《数据结构—最优二叉树及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验最优二叉树及其应用1.程序设计简介本实验程序用于验证最优二叉树的算法。树的存储采用带孩子的双亲顺序存储方法。2.源程序//最优二叉树#include#includeusingnamespacestd;//定义结点类型templatestructhufnode{Twei;//权值intprt;//指昀父结点的指针域(结点元素的下标)intlch;//左指针域(结点元素的下标)intrch;//右指针域(结点元素的下标)};//由于数组下标一般是非负数整数，因此4

2、以用-1作为空指针值templateclasshuffman_BT{intnn;//叶子结点的个数hufnode*p,intk,int*i,int*j);voidprt_hufm_BT();//输出最优二叉树存储空间状、};//生成最优二义树te

3、mplatevoidhuffman_BT::creat_hufm_BT(intn,Tw[J){//n是叶子结点的个数，w是叶子结点的权值数组hufnode*p;intnn=n;m=n*2-l;BT=newhufnodelch=-l;(p+k)-〉rch=，1;}for(k=0;k

4、权值(p+k)->wei=w[k];}for(k=n;kprt=k;(p+j)-〉prt=k;//合并构成新的二叉树(p+k)-〉lch=i;(p+k)->rch=j;(p+k)-〉wei=(p+i)-〉wei+(p+j)-〉wei;}}templatevoidhuffman_BT::select(hufnode*p,intk，int*i，int*j){/

5、/在前K-l个结点中选择权值最小的两个根结点i和jTw;intn=0;while(nwei;*i=n;while(nwei)prt==-1)){*i=n;w=(p+n)->wei;}n++;}n=0;while((nprt!=-l)

6、

7、(n==(*i)))n++;w=(p+n)->wei;*j=n；while(n

8、)->weiprt==-1))*j=n;w=(p+n)-〉wei;n++;}{n=(*i);*i=•*j=n;}}templatevoidhuffman_BT::prt_hufm_BT(){hufnode*p;intk;P=BT;cout«,'k,,«setw(7)«HWEr,«setw(7)«',PRTn«setw(7)«',LCH"«setw(7)«"RCH"«endl;for(k=0;k<2*nn-l;k++){cout«k«setw(

9、7)«(p+k)->wei«setw(7)«(p+k)->prt<lch«setw(7)«(p+k)->rch«endl;}}voidmain(){int*w;intop;inti;huffman_BTb;do{cout«"l-输入结点权值•’《endl;COUt«n2-生成最优二叉cout«"3-退出程序”《endl;cout«”请选择操作：[]";cout«nbbH;cin»op;switch(op){case1:c0Ut«”请输入结点的个数：intsum;cin»

10、sum;w=newintfsum];cout«"请依次输入权值：M«endl;for(i=0;i