程序二叉樹習(xí)題(answer)-閱讀頁
2025-04-09 06:41本頁面
【正文】 =depth(rootlchild)。 /*向上回朔時，要挑出左右子樹中的相對大的那個深度值*/d=depth(rootrchild)。}p=p+1。}法二：int Get_Sub_Depth(Bitree T,int x)//求二叉樹中以值為x的結(jié)點(diǎn)為根的子樹深度 { if(Tdata==x) { printf(%d\n,Get_Depth(T))。 } } else { if(Tlchild) Get_Sub_Depth(Tlchild,x)。 //在左右子樹中繼續(xù)尋找 } }//Get_Sub_Depth int Get_Depth(Bitree T)//求子樹深度的遞歸算法 { if(!T) return 0。 n=Get_Depth(Trchild)。 } }//Get_Depth 附：上機(jī)調(diào)試過程步驟1 鍵盤輸入序列12，8，17，11，16，2，13，9，21，4，構(gòu)成一棵二叉排序樹。完整程序如下：include include typedef struct liuyu{int data。}test。int sum=0。void insert_data(int x) /*如何生成二叉排序樹？參見教材P43C程序*/{ liuyu *p,*q,*s。sdata=x。srchild=NULL。 return。 while(p) /*如何接入二叉排序樹的適當(dāng)位置*/ {q=p。return。 else p=prchild。else qrchild=s。 /*注意每一層的局部變量d,p都是各自獨(dú)立的*/p=0。 /*找到葉子之后才開始統(tǒng)計*/else{ d=depth(rootlchild)。 /*向上回朔時，要挑出左右子樹中的相對大的那個深度值*/d=depth(rootrchild)。}p=p+1。}void main() /*先生成二叉排序樹，再調(diào)用深度遍歷遞歸函數(shù)進(jìn)行統(tǒng)計并輸出*/{int i,x。 root=NULL。i++。x)。 return。} /*調(diào)用插入數(shù)據(jù)元素的函數(shù)*/while(x!=9999)。}執(zhí)行結(jié)果：（同一層自左至右）遍歷二叉樹的算法。這是一個循環(huán)算法，用while語句不斷循環(huán)，直到隊(duì)空之后自然退出該函數(shù)。level(liuyu*T)/* liuyu *T,*p,*q[100]。f=0。 /*置空隊(duì)*/r=(r+1)%max。 /*根結(jié)點(diǎn)進(jìn)隊(duì)*/while(f!=r) /*隊(duì)列不空*/{f=(f+1%max)。 /*出隊(duì)*/printf(%d,pdata)。 q[r]=plchild。 q[r]=prchild。}法二：void LayerOrder(Bitree T)//層序遍歷二叉樹 { InitQueue(Q)。 while(!QueueEmpty(Q)) { DeQueue(Q,p)。 if(plchild) EnQueue(Q,plchild)。 } }//LayerOrder 可以用前面的函數(shù)建樹，然后調(diào)用這個函數(shù)來輸出。struct liuyu *lchild,*rchild。liuyu *root,*p,*q[max]。int m=sizeof(test)。s=(test*)malloc(m)。slchild=NULL。if(!root){root=s。}p=root。if(pdata==x){printf(data already exist! \n)。}else if(xpdata)p=plchild。 }if(xqdata)qlchild=s。}level(liuyu*T)/* liuyu *T,*p,*q[100]。f=0。 /*置空隊(duì)*/r=(r+1)%max。 /*根結(jié)點(diǎn)進(jìn)隊(duì)*/while(f!=r) /*隊(duì)列不空*/{f=(f+1%max)。 /*出隊(duì)*/printf(%d,pdata)。 q[r]=plchild。 q[r]=prchild。}void main() /*先生成二叉排序樹，再調(diào)用深度遍歷遞歸函數(shù)進(jìn)行統(tǒng)計并輸出*/{int i,x。 root=NULL。i++。x)。 return。} /*調(diào)用插入數(shù)據(jù)元素的函數(shù)*/while(x!=9999)。}4. 已知一棵具有n個結(jié)點(diǎn)的完全二叉樹被順序存儲于一維數(shù)組A中，試編寫一個算法打印出編號為i的結(jié)點(diǎn)的雙親和所有的孩子。其次分析：結(jié)點(diǎn)i的左孩子為2i，右孩子為2i+1。Printf(“Left_child=”, %d, v[2*i].data。)。若i為奇數(shù)，則應(yīng)當(dāng)先i ，然后再除以2。Printf(“Parents=”, %d, v[i/2].data。 flag=0。 //建立工作隊(duì)列 while(!QueueEmpty(Q)) { { DeQueue(Q,p)。 else if(flag) return 0。 EnQueue(Q,prchild)。 }//IsFull_Bitree 分析:,作了一個修改,不管當(dāng)前結(jié)點(diǎn) 是否有左右孩子,遍歷時得到是一個連續(xù)的不包含空 ,則序列中會含有空指針. 6. 假設(shè)用于通信的電文僅由8個字母組成。使用0～7的二進(jìn)制表示形式是另一種編碼方案。解：方案1；哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1