數據結構樹自測卷解答-資料下載頁
2025-06-25 07:21本頁面
【正文】 e(Q,prchild)。 } }//LayerOrder 可以用前面的函數建樹，然后調用這個函數來輸出。完整程序如下（已上機通過）include include define max 50typedef struct liuyu{int data。struct liuyu *lchild,*rchild。}test。liuyu *root,*p,*q[max]。int sum=0。int m=sizeof(test)。void insert_data(int x) /*如何生成二叉排序樹？參見教材P43C程序*/{ liuyu *p,*q,*s。s=(test*)malloc(m)。sdata=x。slchild=NULL。srchild=NULL。if(!root){root=s。 return。}p=root。 while(p) /*如何接入二叉排序樹的適當位置*/ {q=p。if(pdata==x){printf(data already exist! \n)。return。}else if(xpdata)p=plchild。 else p=prchild。 }if(xqdata)qlchild=s。else qrchild=s。}level(liuyu*T)/* liuyu *T,*p,*q[100]。 假設max已知*/{int f,r。f=0。 r=0。 /*置空隊*/r=(r+1)%max。q[r]=T。 /*根結點進隊*/while(f!=r) /*隊列不空*/{f=(f+1%max)。p=q[f]。 /*出隊*/printf(%d,pdata)。 /*打印根結點*/if(plchild){r=(r+1)%max。 q[r]=plchild。} /*若左子樹不空，則左子樹進隊*/ if(prchild){r=(r+1)%max。 q[r]=prchild。} /*若右子樹不空，則右子樹進隊*/ }return(0)。}void main() /*先生成二叉排序樹，再調用深度遍歷遞歸函數進行統計并輸出*/{int i,x。i=1。 root=NULL。 /*千萬別忘了賦初值給root!*/do{printf(please input data%d:,i)。i++。scanf(%d,amp。x)。 /*從鍵盤采集數據，以9999表示輸入結束*/if(x==9999){ printf(\nNow output data value:\n, level(root))。 return。 } else insert_data(x)。} /*調用插入數據元素的函數*/while(x!=9999)。 return。}4. （P60 425）已知一棵具有n個結點的完全二叉樹被順序存儲于一維數組A中，試編寫一個算法打印出編號為i的結點的雙親和所有的孩子。答：結點i的左孩子為2i，右孩子為2i+1。 用循環(huán)算法打印即可。由于是完全二叉樹，不必擔心中途會出現孩子為null的情況。5.【④】編寫算法判別給定二叉樹是否為完全二叉樹。答：int IsFull_Bitree(Bitree T)//判斷二叉樹是否完全二叉樹,是則返回1,否則返回0 { InitQueue(Q)。 flag=0。 EnQueue(Q,T)。 //建立工作隊列 while(!QueueEmpty(Q)) { { DeQueue(Q,p)。 if(!p) flag=1。 else if(flag) return 0。 else { EnQueue(Q,plchild)。 EnQueue(Q,prchild)。 //不管孩子是否為空,都入隊列 } }//while return 1。 }//IsFull_Bitree 分析:,作了一個修改,不管當前結點 是否有左右孩子,遍歷時得到是一個連續(xù)的不包含空 ,則序列中會含有空指針. 6. 【③】假設用于通信的電文僅由8個字母組成，，，。試為這8個字母設計哈夫曼編碼。使用0～7的二進制表示形式是另一種編碼方案。對于上述實例，比較兩種方案的優(yōu)缺點。解：方案1；哈夫曼編碼先將概率放大100倍，以方便構造哈夫曼樹。 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方案比較：字母編號對應編碼出現頻率111002003111104111051061111170181101字母編號對應編碼出現頻率10002001301040115100610171108111方案1的WPL＝2(++)+4(++)+5(+)=++=方案2的WPL＝3(+++++++)=3結論：哈夫曼編碼優(yōu)于等長二進制編碼13
化學相關推薦
鄂ICP備17016276號-1