程序二叉樹習題(answer)(編輯修改稿)
2025-04-21 06:41 本頁面
【文章內容簡介】 while(!rrtag)r=rrchild。 //應改為 while(!rLtag) r=rLchild。return r。 //應改為return rrchild；}//ISucc，若有錯，改正之。答：注意根右邊的子樹肯定是森林，而孩子結點的右子樹均為兄弟。六、算法設計題（），計算二叉樹中葉子結點的數目。解：思路：輸出葉子結點比較簡單，用任何一種遍歷遞歸算法，凡是左右指針均空者，則為葉子，將其打印出來。法一：核心部分為：DLR(liuyu *root) /*中序遍歷 遞歸函數*/{if(root!=NULL) {if((rootlchild==NULL)amp。amp。(rootrchild==NULL)){sum++。 printf(%d\n,rootdata)。} DLR(rootlchild)。 DLR(rootrchild)。 } return(0)。}法二：int LeafCount_BiTree(Bitree T)//求二叉樹中葉子結點的數目 { if(!T) return 0。 //空樹沒有葉子 else if(!Tlchildamp。amp。!Trchild) return 1。 //葉子結點 else return Leaf_Count(Tlchild)+Leaf_Count(Trchild)。//左子樹的葉子數加 上右子樹的葉子數 }//LeafCount_BiTree 注：上機時要先建樹！例如實驗二的方案一。① 打印葉子結點值（并求總數）思路：先建樹，再從遍歷過程中打印結點值并統(tǒng)計。步驟1 鍵盤輸入序列12，8，17，11，16，2，13，9，21，4，構成一棵二叉排序樹。葉子結點值應該是4，9, 13, 21, 總數應該是4. 127 17 2 11 16 21 4 9 13編程： 生成二叉樹排序樹之后，再中序遍歷排序查找結點的完整程序如下： 說明部分為：include include typedef struct liuyu{int data。struct liuyu *lchild,*rchild。}test。liuyu *root。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。}DLR(liuyu *root) /*中序遍歷 遞歸函數*/{if(root!=NULL) {if((rootlchild==NULL)amp。amp。(rootrchild==NULL)){sum++。 printf(%d\n,rootdata)。} DLR(rootlchild)。 DLR(rootrchild)。 } return(0)。} 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){ DLR(root)。 printf(\nNow output count value:%d\n,sum)。 return(0)。 } else insert_data(x)。} /*調用插入數據元素的函數*/while(x!=9999)。 return(0)。}執(zhí)行結果：若一開始運行就輸入9999，則無葉子輸出，sum=0。，先定義二叉樹的抽象數據類型。 （）編寫遞歸算法，求二叉樹中以元素值為x的結點為根的子樹的深度。答；設計思路：只查后繼鏈表指針，若左或右孩子的左或右指針非空，則層次數加1；否則函數返回。但注意，遞歸時應當從葉子開始向上計數，否則不易確定層數。 int depth(liuyu*root) /*統(tǒng)計層數*/{int d,p。 /*注意每一層的局部變量d,p都是各自獨立的*/p=0。if(root==NULL)return(p)。 /*找到葉子之后才開始統(tǒng)計*/else{ d=depth(rootlchild)。if(dp) p=d。 /*向上回朔時，要挑出左右子樹中的相對大的那個深度值*/d=depth(rootrchild)。if(dp)p=d。}p=p+1。return(p)。}法二：int Get_Sub_Depth(Bitree T,int x)//求二叉樹中以值為x的結點為根的子樹深度 { if(Tdata==x) { printf(%d\n,Get_Depth(T))。 //找到了值為x的結點,求其深度 exit 1。 }
醫(yī)療健康相關推薦
鄂ICP備17016276號-1