數(shù)據(jù)結(jié)構(gòu)樹自測(cè)卷解答(參考版)
2025-06-28 07:21本頁(yè)面
【正文】 w={7,19,2,6,32,3,21,10}，按哈夫曼規(guī)則：【[（2,3），6], (7,10)】, ……19, 21, 32 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3 （100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3方案比較：字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率111002003111104111051061111170181101字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率10002001301040115100610171108111方案1的WPL＝2(++)+4(++)+5(+)=++=方案2的WPL＝3(+++++++)=3結(jié)論：哈夫曼編碼優(yōu)于等長(zhǎng)二進(jìn)制編碼13。對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。 //不管孩子是否為空,都入隊(duì)列 } }//while return 1。 else { EnQueue(Q,plchild)。 if(!p) flag=1。 EnQueue(Q,T)。答：int IsFull_Bitree(Bitree T)//判斷二叉樹是否完全二叉樹,是則返回1,否則返回0 { InitQueue(Q)。由于是完全二叉樹，不必?fù)?dān)心中途會(huì)出現(xiàn)孩子為null的情況。答：結(jié)點(diǎn)i的左孩子為2i，右孩子為2i+1。 return。 } else insert_data(x)。 /*從鍵盤采集數(shù)據(jù)，以9999表示輸入結(jié)束*/if(x==9999){ printf(\nNow output data value:\n, level(root))。scanf(%d,amp。 /*千萬別忘了賦初值給root!*/do{printf(please input data%d:,i)。i=1。} /*若右子樹不空，則右子樹進(jìn)隊(duì)*/ }return(0)。} /*若左子樹不空，則左子樹進(jìn)隊(duì)*/ if(prchild){r=(r+1)%max。 /*打印根結(jié)點(diǎn)*/if(plchild){r=(r+1)%max。p=q[f]。q[r]=T。 r=0。 假設(shè)max已知*/{int f,r。else qrchild=s。 else p=prchild。return。 while(p) /*如何接入二叉排序樹的適當(dāng)位置*/ {q=p。 return。srchild=NULL。sdata=x。void insert_data(int x) /*如何生成二叉排序樹？參見教材P43C程序*/{ liuyu *p,*q,*s。int sum=0。}test。完整程序如下（已上機(jī)通過）include include define max 50typedef struct liuyu{int data。 if(prchild) EnQueue(Q,prchild)。 visit(p)。 //建立工作隊(duì)列 EnQueue(Q,T)。} /*若右子樹不空，則右子樹進(jìn)隊(duì)*/ }return(0)。} /*若左子樹不空，則左子樹進(jìn)隊(duì)*/ if(prchild){r=(r+1)%max。 /*打印根結(jié)點(diǎn)*/if(plchild){r=(r+1)%max。p=q[f]。q[r]=T。 r=0。 假設(shè)max已知*/{int f,r。技巧之處：當(dāng)根結(jié)點(diǎn)入隊(duì)后，會(huì)自然使得左、右孩子結(jié)點(diǎn)入隊(duì)，而左孩子出隊(duì)時(shí)又會(huì)立即使得它的左右孩子結(jié)點(diǎn)入隊(duì)，……以此產(chǎn)生了按層次輸出的效果?；颍喊磳哟屋敵龆鏄渲兴薪Y(jié)點(diǎn)；解：思路：既然要求從上到下，從左到右，則利用隊(duì)列存放各子樹結(jié)點(diǎn)的指針是個(gè)好辦法。 return。 } else insert_data(x)。 /*從鍵盤采集數(shù)據(jù)，以9999表示輸入結(jié)束*/if(x==9999){ printf(\nNow output depth value=%d\n, depth (root))。scanf(%d,amp。 /*千萬別忘了賦初值給root!*/do{printf(please input data%d:,i)。i=1。return(p)。if(dp)p=d。if(dp) p=d。if(root==NULL)return(p)。}int depth(liuyu*root) /*統(tǒng)計(jì)層數(shù)*/{int d,p。 }if(xqdata)qlchild=s。}else if(xpdata)p=plchild。if(pdata==x){printf(data already exist! \n)。}p=root。if(!root){root=s。slchild=NULL。s=(test*)malloc(m)。int m=sizeof(test)。liuyu *root。struct liuyu *lchild,*rchild。層數(shù)應(yīng)當(dāng)為4 12 8 17 2 11 16 21 4 9
化學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1