數(shù)據(jù)結(jié)構(gòu)樹(shù)自測(cè)卷解答(編輯修改稿)
2024-07-22 07:21 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ld。 //應(yīng)改為r=q；if(!rrtag) while(!rrtag)r=rrchild。 // 應(yīng)改為 while(!rLtag) r=rLchild。return r。 //應(yīng)改為return rrchild；}//ISucc3.【③】閱讀下列算法，若有錯(cuò)，改正之。4.【②】畫出和下列二叉樹(shù)相應(yīng)的森林。答案：注意根右邊的子樹(shù)肯定是森林，而孩子結(jié)點(diǎn)的右子樹(shù)均為兄弟。六、算法設(shè)計(jì)題（前5題中任選2題，第6題必做，每題8分，共24分）1.【③】編寫遞歸算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。解：思路：輸出葉子結(jié)點(diǎn)比較簡(jiǎn)單，用任何一種遍歷遞歸算法，凡是左右指針均空者，則為葉子，將其打印出來(lái)。可作為實(shí)驗(yàn)二內(nèi)容。核心部分為：DLR(liuyu *root) /*中序遍歷 遞歸函數(shù)*/{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)//求二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目 { if(!T) return 0。 //空樹(shù)沒(méi)有葉子 else if(!Tlchildamp。amp。!Trchild) return 1。 //葉子結(jié)點(diǎn) else return Leaf_Count(Tlchild)+Leaf_Count(Trchild)。//左子樹(shù)的葉子數(shù)加 上右子樹(shù)的葉子數(shù) }//LeafCount_BiTree 但上機(jī)時(shí)要先建樹(shù)！① 打印葉子結(jié)點(diǎn)值（并求總數(shù)）思路：先建樹(shù)，再?gòu)谋闅v過(guò)程中打印結(jié)點(diǎn)值并統(tǒng)計(jì)。步驟1 鍵盤輸入序列12，8，17，11，16，2，13，9，21，4，構(gòu)成一棵二叉排序樹(shù)。葉子結(jié)點(diǎn)值應(yīng)該是4，9,13,21,總數(shù)應(yīng)該是4. 127 17 2 11 16 21 4 9 13編程： 生成二叉樹(shù)排序樹(shù)之后，再中序遍歷排序查找結(jié)點(diǎn)的完整程序如下： 說(shuō)明部分為：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) /*如何生成二叉排序樹(shù)？參見(jiàn)教材P43C程序*/{ liuyu *p,*q,*s。s=(test*)malloc(m)。sdata=x。slchild=NULL。srchild=NULL。if(!root){root=s。 return。}p=root。 while(p) /*如何接入二叉排序樹(shù)的適當(dāng)位置*/ {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) /*中序遍歷 遞歸函數(shù)*/{if(root!=NULL) {if((rootlchild==NULL)amp。amp。(rootrchild==NULL)){sum++。 printf(%d\n,rootdata)。} DLR(rootlchild)。 DLR(rootrchild)。 } return(0)。} main() /*先生成二叉排序樹(shù)，再調(diào)用中序遍歷遞歸函數(shù)進(jìn)行排序輸出*/{int i,x。i=1。 root=NULL。 /*千萬(wàn)別忘了賦初值給root!*/do{printf(please input data%d:,i)。i++。scanf(%d,amp。x)。 /*從鍵盤采集數(shù)據(jù)，以9999表示輸入結(jié)束*/if(x==9999){ DLR(root)。 printf(\nNow output count value:%d\n,sum)。 return(0)。 } else insert_data(x)。} /*調(diào)用插入數(shù)據(jù)元素的函數(shù)*/while(x!=9999)。 return(0)。}執(zhí)行結(jié)果：若一開(kāi)始運(yùn)行就輸入9999，則無(wú)葉子輸出，sum=0。2.【全國(guó)專升本統(tǒng)考題】寫出求二叉樹(shù)深度的算法，先定義二叉樹(shù)的抽象數(shù)據(jù)類型。 （10分）或【④】編寫遞歸算法，求二叉樹(shù)中以元素值為x的結(jié)點(diǎn)為根的子樹(shù)的深度。答；設(shè)計(jì)思路：只查后繼鏈表指針，若左或右孩子的左或右指針?lè)强?，則層次數(shù)加1；否則函數(shù)返回。但注意，遞歸時(shí)應(yīng)當(dāng)從葉子開(kāi)始向上計(jì)數(shù)，否則不易確定層數(shù)。 int depth(liuyu*root) /*統(tǒng)計(jì)層數(shù)*/{int d,p。 /*注意每一層的局部變量d,p都是各自獨(dú)立的*/p=0。if(root==NULL)return(p)。 /*找到葉子之后才開(kāi)始統(tǒng)計(jì)*/else{ d=depth(rootlchild)。if(dp) p=d。 /*向上回朔時(shí)，要挑出左右子樹(shù)中的相對(duì)大的那個(gè)深度值*/d=depth(rootrchild)。if(dp)p=d。}p=p+1。return(p)。}法二：int Get_Sub_Depth(Bi
化學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1