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