程序二叉樹習題(answer)-wenkub
2023-04-09 06:41:02 本頁面
【正文】 序法，即按L N R次序）。答：當k=1(單叉樹)時應該最深，深度＝n（層）；當k=n1（n1叉樹）時應該最淺，深度＝2（層），但不包括n=0或1時的特例情況。答：最快方法：用葉子數(shù)＝[n/2]＝350 5. 設一棵完全二叉樹具有1000個結點，則此完全二叉樹有 500 個葉子結點，有 499 個度為2的結點，有 1 個結點只有非空左子樹，有 0 個結點只有非空右子樹。 log2(n) 2. 一棵深度為6的滿二叉樹有 n1+n2=0+ n2= n01=31 個分支結點和 261 =32 個葉子。由于二叉樹中，除根結點外，每一個結點有且僅有一個雙親，所以只有n1個結點的鏈域存放指向非空子女結點的指針，還有n+1個空指針。 （ ）.對于一棵非空二叉樹，它的根結點作為第一層，則它的第i層上最多能有2i—1個結點。 （ ）.二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹。一、下面是有關二叉樹的敘述，請判斷正誤（）（ ）. 若二叉樹用二叉鏈表作存貯結構，則在n個結點的二叉樹鏈表中只有n—1個非空指針域。 （ ）二叉樹中每個結點的關鍵字值大于其左非空子樹（若存在的話）所有結點的關鍵字值，且小于其右非空子樹（若存在的話）所有結點的關鍵字值。（應2i1）（ ）用二叉鏈表法（linkrlink）存儲包含n個結點的二叉樹，結點的2n個指針區(qū)域中有n+1個為空指針。）即有后繼鏈接的指針僅n1個。注：滿二叉樹沒有度為1的結點，所以分支結點數(shù)就是二度結點數(shù)。+1= 235。答：最快方法：用葉子數(shù)＝[n/2]＝500 ，n2=n01=499。教材答案是“完全k叉樹”，未定量。這三種方法相互之間有關聯(lián)。例如，前序遍歷BEFCGDH中，根結點在最前面，是B；則后序遍歷中B一定在最后面。 O(n) 。解：先構造哈夫曼樹，得到各葉子的路徑長度之后便可求出WPL＝（4＋5＋3）2＋（1＋2）3=33 (15)(9) (6) （注：兩個合并值先后不同會導致編碼不同，即哈夫曼編碼不唯一） 4 5 3 (3) （注：合并值應排在葉子值之后）1 2（注：原題為選擇題：Ａ．32 Ｂ．33 Ｃ．34 Ｄ．15）三、單項選擇題（）（ C ）1． 不含任何結點的空樹 。 （Ｄ）既不是樹也不是二叉樹答：以前的標答是B，因為那時樹的定義是n≥1（ C ）2．二叉樹是非線性數(shù)據(jù)結構，所以 。 （Ｄ）順序存儲結構和鏈式存儲結構都不能使用 （ C ）(n0)個結點的完全二叉樹的深度為 。 log2(n)log2(n)+1249。 x log2(n) +1其余的結點分成為m（m≥0）個 B 的集合T1，T2，…，Tm，每個集合又都是樹，此時結點T稱為Ti的父結點，Ti稱為T的子結點（1≤i≤m）。在完全的二叉樹中，若一個結點沒有 B ，則它必定是葉結點。即，在一般樹中若某結點只有一個孩子，就無需區(qū)分其左右次序，而在二叉樹中即使是一個孩子也有左右之分。C算法如下：void traversal(struct node *root){if (root) {printf(“%c”, rootdata)。}}，root為根指針，結點結構為：（lchild,data,rchild）。如C，E，F(xiàn)，G等結點。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問題得解。答：DLR：A B D F J G K C E H I L M LDR: B F J D G K A C H E L I M LRD：J F K G D B H L M I E C A2. （P60 427）把如圖所示的樹轉化成二叉樹。注：當rtag＝1時說明內裝后繼指針，可直接返回，第一句無錯。 直到LTag=1； 應改為：while(!rLtag)r=rLchild。 //應改為 while(!rLtag) r=rLchild。答：注意根右邊的子樹肯定是森林，而孩子結點的右子樹均為兄弟。amp。 DLR(rootrchild)。amp。① 打印葉子結點值（并求總數(shù)）思路：先建樹，再從遍歷過程中打印結點值并統(tǒng)計。}test。void insert_data(int x) /*如何生成二叉排序樹？參見教材P43C程序*/{ liuyu *p,*q,*s。srchild=NULL。 while(p) /*如何接入二叉排序樹的適當位置*/ {q=p。 else p=prchild。amp。 DLR(rootrchild)。 root=NULL。x)。 } else insert_data(x)。，先定義二叉樹的抽象數(shù)據(jù)類型。 int depth(liuyu*root) /*統(tǒng)計層數(shù)*/{int d,p。if(dp) p=d。return(p)。 if(Trchild) Get_Sub_Depth(Trchild,x)。 return (mn?m:n)+1。struct liuyu *lchild,*rchild。int m=sizeof(test)。slchild=NULL。}p=root。}else if(xpdata)p=plchild。}int depth(liuyu*root) /*統(tǒng)計層數(shù)*/{int d,p。if(dp) p=d。return(p)。 /*千萬別忘了賦初值給root!*/do{printf(please input data%d:,i)。 /*從鍵盤采集數(shù)據(jù)，以9999表示輸入結束*/if(x==9999){ printf(\nNow output depth value=%d\n, depth (root)
醫(yī)療健康相關推薦
鄂ICP備17016276號-1