程序二叉樹習(xí)題(answer)(已改無錯(cuò)字)
2023-04-25 06:41:02 本頁面
【正文】 } else { if(Tlchild) Get_Sub_Depth(Tlchild,x)。 if(Trchild) Get_Sub_Depth(Trchild,x)。 //在左右子樹中繼續(xù)尋找 } }//Get_Sub_Depth int Get_Depth(Bitree T)//求子樹深度的遞歸算法 { if(!T) return 0。 else { m=Get_Depth(Tlchild)。 n=Get_Depth(Trchild)。 return (mn?m:n)+1。 } }//Get_Depth 附：上機(jī)調(diào)試過程步驟1 鍵盤輸入序列12，8，17，11，16，2，13，9，21，4，構(gòu)成一棵二叉排序樹。層數(shù)應(yīng)當(dāng)為4 12 8 17 2 11 16 21 4 9 13 步驟2： 執(zhí)行求深度的函數(shù)，并打印統(tǒng)計(jì)出來的深度值。完整程序如下：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。}int depth(liuyu*root) /*統(tǒng)計(jì)層數(shù)*/{int d,p。 /*注意每一層的局部變量d,p都是各自獨(dú)立的*/p=0。if(root==NULL)return(p)。 /*找到葉子之后才開始統(tǒng)計(jì)*/else{ d=depth(rootlchild)。if(dp) p=d。 /*向上回朔時(shí)，要挑出左右子樹中的相對(duì)大的那個(gè)深度值*/d=depth(rootrchild)。if(dp)p=d。}p=p+1。return(p)。}void main() /*先生成二叉排序樹，再調(diào)用深度遍歷遞歸函數(shù)進(jìn)行統(tǒng)計(jì)并輸出*/{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){ printf(\nNow output depth value=%d\n, depth (root))。 return。 } else insert_data(x)。} /*調(diào)用插入數(shù)據(jù)元素的函數(shù)*/while(x!=9999)。 return。}執(zhí)行結(jié)果：（同一層自左至右）遍歷二叉樹的算法?；颍喊磳哟屋敵龆鏄渲兴薪Y(jié)點(diǎn)；解：思路：既然要求從上到下，從左到右，則利用隊(duì)列存放各子樹結(jié)點(diǎn)的指針是個(gè)好辦法。這是一個(gè)循環(huán)算法，用while語句不斷循環(huán)，直到隊(duì)空之后自然退出該函數(shù)。技巧之處：當(dāng)根結(jié)點(diǎn)入隊(duì)后，會(huì)自然使得左、右孩子結(jié)點(diǎn)入隊(duì)，而左孩子出隊(duì)時(shí)又會(huì)立即使得它的左右孩子結(jié)點(diǎn)入隊(duì)，……以此產(chǎn)生了按層次輸出的效果。level(liuyu*T)/* liuyu *T,*p,*q[100]。 假設(shè)max已知*/{int f,r。f=0。 r=0。 /*置空隊(duì)*/r=(r+1)%max。q[r]=T。 /*根結(jié)點(diǎn)進(jìn)隊(duì)*/while(f!=r) /*隊(duì)列不空*/{f=(f+1%max)。p=q[f]。 /*出隊(duì)*/printf(%d,pdata)。 /*打印根結(jié)點(diǎn)*/if(plchild){r=(r+1)%max。 q[r]=plchild。} /*若左子樹不空，則左子樹進(jìn)隊(duì)*/ if(prchild){r=(r+1)%max。 q[r]=prchild。} /*若右子樹不空，則右子樹進(jìn)隊(duì)*/ }return(0)。}法二：void LayerOrder(Bitree T)//層序遍歷二叉樹 { InitQueue(Q)。 //建立工作隊(duì)列 EnQueue(Q,T)。 while(!QueueEmpty(Q)) { DeQueue(Q,p)。 visit(p)。 if(plchild) EnQueue(Q,plchild)。 if(prchild) EnQueue(Q,prchild)。 } }//LayerOrder 可以用前面的函數(shù)建樹，然后調(diào)用這個(gè)函數(shù)來輸出。完整程序如下（已上機(jī)通過）include include define max 50typedef struct liuyu{i
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1