數(shù)據(jù)結(jié)構(gòu) C語言版 第二版嚴(yán)蔚敏 樹和二叉樹 答案

1、第5章 樹和二叉樹1選擇題（1）把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（ ）。 A唯一的 有多種C有多種，但根結(jié)點(diǎn)都沒有左孩子 有多種，但根結(jié)點(diǎn)都沒有右孩子答案：A 解釋：因?yàn)槎鏄溆凶蠛⒆?、右孩子之分，故一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是唯一的。（2）由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（ ）A2 B3 C4 D5 答案：D解釋：五種情況如下： （3）一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ ）。A250 B 500 C254 D501 答案：D解釋：設(shè)度為0結(jié)點(diǎn)（葉子結(jié)點(diǎn)）個(gè)數(shù)為A，度為1的結(jié)點(diǎn)個(gè)數(shù)為B，度為2的結(jié)點(diǎn)個(gè)數(shù)為C，有A=C+1，A+B+C=1001

2、，可得2C+B=1000，由完全二叉樹的性質(zhì)可得B=0或1，又因?yàn)镃為整數(shù)，所以B=0，C=500，A=501，即有501個(gè)葉子結(jié)點(diǎn)。（4）一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（ ）。A11 B10 C11至1025之間 D10至1024之間答案：C解釋：若每層僅有一個(gè)結(jié)點(diǎn)，則樹高h(yuǎn)為1025；且其最小樹高為log21025+1=11，即h在11至1025之間。（5）深度為h的滿m叉樹的第k層有（ ）個(gè)結(jié)點(diǎn)。(1=k=lchild=NULL&T-rchild=NULL)return 1; /判斷結(jié)點(diǎn)是否是葉子結(jié)點(diǎn)（左孩子右孩子都為空），若是則返回1elsereturn LeafNodeCou

3、nt(T-lchild)+LeafNodeCount(T-rchild);（2）判別兩棵樹是否相等。題目分析先判斷當(dāng)前節(jié)點(diǎn)是否相等(需要處理為空、是否都為空、是否相等)，如果當(dāng)前節(jié)點(diǎn)不相等，直接返回兩棵樹不相等;如果當(dāng)前節(jié)點(diǎn)相等，那么就遞歸的判斷他們的左右孩子是否相等。算法描述int compareTree(TreeNode* tree1, TreeNode* tree2)/用分治的方法做，比較當(dāng)前根，然后比較左子樹和右子樹bool tree1IsNull = (tree1=NULL);bool tree2IsNull = (tree2=NULL);if(tree1IsNull != tree

4、2IsNull)return 1;if(tree1IsNull & tree2IsNull)/如果兩個(gè)都是NULL，則相等return 0;/如果根節(jié)點(diǎn)不相等，直接返回不相等，否則的話，看看他們孩子相等不相等if(tree1-c != tree2-c)return 1;return (compareTree(tree1-left,tree2-left)&compareTree(tree1-right,tree2-right) (compareTree(tree1-left,tree2-right)&compareTree(tree1-right,tree2-left);/算法結(jié)束（3）交換二叉

5、樹每個(gè)結(jié)點(diǎn)的左孩子和右孩子。題目分析如果某結(jié)點(diǎn)左右子樹為空，返回，否則交換該結(jié)點(diǎn)左右孩子，然后遞歸交換左右子樹。算法描述void ChangeLR(BiTree &T)BiTree temp;if(T-lchild=NULL&T-rchild=NULL)return;elsetemp = T-lchild;T-lchild = T-rchild;T-rchild = temp;/交換左右孩子ChangeLR(T-lchild); /遞歸交換左子樹ChangeLR(T-rchild); /遞歸交換右子樹（4）設(shè)計(jì)二叉樹的雙序遍歷算法（雙序遍歷是指對(duì)于二叉樹的每一個(gè)結(jié)點(diǎn)來說，先訪問這個(gè)結(jié)點(diǎn)，再按雙

6、序遍歷它的左子樹，然后再一次訪問這個(gè)結(jié)點(diǎn)，接下來按雙序遍歷它的右子樹）。題目分析若樹為空，返回；若某結(jié)點(diǎn)為葉子結(jié)點(diǎn)，則僅輸出該結(jié)點(diǎn)；否則先輸出該結(jié)點(diǎn)，遞歸遍歷其左子樹，再輸出該結(jié)點(diǎn)，遞歸遍歷其右子樹。算法描述void DoubleTraverse(BiTree T)if(T = NULL)return;else if(T-lchild=NULL&T-rchild=NULL)coutdata; /葉子結(jié)點(diǎn)輸出elsecoutdata;DoubleTraverse(T-lchild); /遞歸遍歷左子樹coutdata; DoubleTraverse(T-rchild); /遞歸遍歷右子樹（5）計(jì)

7、算二叉樹最大的寬度（二叉樹的最大寬度是指二叉樹所有層中結(jié)點(diǎn)個(gè)數(shù)的最大值）。題目分析 求二叉樹高度的算法見上題。求最大寬度可采用層次遍歷的方法，記下各層結(jié)點(diǎn)數(shù)，每層遍歷完畢，若結(jié)點(diǎn)數(shù)大于原先最大寬度，則修改最大寬度。算法描述int Width(BiTree bt)/求二叉樹bt的最大寬度if (bt=null) return (0); /空二叉樹寬度為0else BiTree Q;/Q是隊(duì)列，元素為二叉樹結(jié)點(diǎn)指針，容量足夠大front=1;rear=1;last=1;/front隊(duì)頭指針,rear隊(duì)尾指針,last同層最右結(jié)點(diǎn)在隊(duì)列中的位置temp=0; maxw=0; /temp記局部寬度,

8、maxw記最大寬度Qrear=bt; /根結(jié)點(diǎn)入隊(duì)列while(frontlchild!=null) Q+rear=p-lchild; /左子女入隊(duì)if (p-rchild!=null) Q+rear=p-rchild; /右子女入隊(duì)if (frontlast) /一層結(jié)束， last=rear;if(tempmaxw) maxw=temp;/last指向下層最右元素, 更新當(dāng)前最大寬度 temp=0; /if /whilereturn (maxw);/結(jié)束width（6）用按層次順序遍歷二叉樹的方法，統(tǒng)計(jì)樹中具有度為1的結(jié)點(diǎn)數(shù)目。題目分析若某個(gè)結(jié)點(diǎn)左子樹空右子樹非空或者右子樹空左子樹非空，則

9、該結(jié)點(diǎn)為度為1的結(jié)點(diǎn)算法描述int Level(BiTree bt) /層次遍歷二叉樹，并統(tǒng)計(jì)度為1的結(jié)點(diǎn)的個(gè)數(shù)int num=0; /num統(tǒng)計(jì)度為1的結(jié)點(diǎn)的個(gè)數(shù) if(bt)QueueInit(Q); QueueIn(Q,bt);/Q是以二叉樹結(jié)點(diǎn)指針為元素的隊(duì)列while(!QueueEmpty(Q)p=QueueOut(Q); coutdata; /出隊(duì),訪問結(jié)點(diǎn)if(p-lchild & !p-rchild |!p-lchild & p-rchild)num+;/度為1的結(jié)點(diǎn)if(p-lchild) QueueIn(Q,p-lchild); /非空左子女入隊(duì)if(p-rchild)

10、QueueIn(Q,p-rchild); /非空右子女入隊(duì) / while(!QueueEmpty(Q)/if(bt) return(num); /返回度為1的結(jié)點(diǎn)的個(gè)數(shù) （7）求任意二叉樹中第一條最長的路徑長度，并輸出此路徑上各結(jié)點(diǎn)的值。題目分析因?yàn)楹笮虮闅v棧中保留當(dāng)前結(jié)點(diǎn)的祖先的信息，用一變量保存棧的最高棧頂指針，每當(dāng)退棧時(shí)，棧頂指針高于保存最高棧頂指針的值時(shí)，則將該棧倒入輔助棧中，輔助棧始終保存最長路徑長度上的結(jié)點(diǎn)，直至后序遍歷完畢，則輔助棧中內(nèi)容即為所求。算法描述void LongestPath(BiTree bt)/求二叉樹中的第一條最長路徑長度BiTree p=bt,l,s; /l

11、, s是棧，元素是二叉樹結(jié)點(diǎn)指針，l中保留當(dāng)前最長路徑中的結(jié)點(diǎn)int i，top=0,tag,longest=0;while(p | top0)while(p) s+top=p；tagtop=0; p=p-Lc; /沿左分枝向下if(tagtop=1) /當(dāng)前結(jié)點(diǎn)的右分枝已遍歷if(!stop-Lc & !stop-Rc) /只有到葉子結(jié)點(diǎn)時(shí)，才查看路徑長度if(toplongest) for(i=1;i0) tagtop=1; p=stop.Rc; /沿右子分枝向下/while(p!=null|top0)/結(jié)束LongestPath（8）輸出二叉樹中從每個(gè)葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。題目分析采用先序遍歷的遞歸方法，當(dāng)找到葉子結(jié)點(diǎn)*b時(shí)，由于*b葉子結(jié)點(diǎn)尚未添加到path中，因此在輸出路徑時(shí)還需輸出b-data值。算法描述void AllPath(BTNode *b,ElemType path,int pathlen)int i; if (b!=NULL)if (b-lchild=NULL & b-rchild=NULL) /*b為葉子結(jié)點(diǎn)cout data 到根結(jié)點(diǎn)路徑: data;