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

第5章樹和二叉樹A．Ｂ．C．有多種，但根結(jié)點(diǎn)都沒有左孩子Ｄ．有多種，但根結(jié)點(diǎn)都沒有右孩子答案：A解釋：因?yàn)槎鏄溆凶蠛⒆?、右孩子之分，故?個結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（）A．2B．3C．4D．5答案：D一棵完全二叉樹上有1001個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個數(shù)是（）A．250B．500C．254D．501答案：D解釋：設(shè)度為0結(jié)點(diǎn)（葉子結(jié)點(diǎn)）個數(shù)為A，度為1的結(jié)點(diǎn)個數(shù)為B，度為2的結(jié)點(diǎn)個數(shù)為C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉樹的性質(zhì)可得B=0或1，又因?yàn)镃為整數(shù)，所以B=0，C=500，A=501，即有501個葉子結(jié)點(diǎn)。一個具有1025個結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（）A．11B．10C．11至1025之間D．10至1024之間答案：C解釋：若每層僅有一個結(jié)點(diǎn)，則樹高h(yuǎn)為1025；且其最小樹高為

log21025

+

1=11，即h在11至1025之間。深度為h的滿m叉樹的第k層有（）個結(jié)點(diǎn)。(1=<k=<h)A．mk-1B．mk-1C．mh-1D．mh-1答案：A解釋：深度為h的滿m叉樹共有mh-1個結(jié)點(diǎn)，第k層有mk-1個結(jié)點(diǎn)。利用二叉鏈表存儲樹，則根結(jié)點(diǎn)的右指針是（）A．指向最左孩子B．指向最右孩子C．空D．非空答案：C解釋：利用二叉鏈表存儲樹時，右指針指向兄弟結(jié)點(diǎn)，因?yàn)楦?jié)點(diǎn)沒有兄弟結(jié)點(diǎn)，故根節(jié)點(diǎn)的右指針指向空。對二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號，要求每個結(jié)點(diǎn)的編號大于其左、右孩子的編號，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用（）遍歷實(shí)現(xiàn)編號。A．先序B.中序C.后序D.從根開始按層次遍歷答案：C解釋：根據(jù)題意可知按照先左孩子、再右孩子、最后雙親結(jié)點(diǎn)的順序遍歷二叉樹，即后序遍歷二叉樹。若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左、右子樹的位置，利用（）遍歷方法最合適。A．前序B．中序C．后序D．按層次答案：C解釋：后續(xù)遍歷和層次遍歷均可實(shí)現(xiàn)左右子樹的交換，不過層次遍歷的實(shí)現(xiàn)消耗比后續(xù)大，后序遍歷方法最合適。在下列存儲形式中，（）不是樹的存儲形式？A．雙親表示法B．孩子鏈表表示法C．孩子兄弟表示法D．順序存儲表示法答案：D解釋：樹的存儲結(jié)構(gòu)有三種：雙親表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵樹都能通過孩子兄弟表示法轉(zhuǎn)換為二叉樹進(jìn)行存儲。一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（）A．所有的結(jié)點(diǎn)均無左孩子B．所有的結(jié)點(diǎn)均無右孩子C．只有一個葉子結(jié)點(diǎn)D．是任意一棵二叉樹答案：C解釋：因?yàn)橄刃虮闅v結(jié)果是“中左右”，后序遍歷結(jié)果是“左右中”，當(dāng)沒有左子樹時，就是“中右”和“右中”；當(dāng)沒有右子樹時，就是“中左”和“左中”。則所有的結(jié)點(diǎn)均無左孩子或所有的結(jié)點(diǎn)均無右孩子均可，所以A、B不能選，又所有的結(jié)點(diǎn)均無左孩子與所有的結(jié)點(diǎn)均無右孩子時，均只有一個葉子結(jié)點(diǎn)，故選C。（11）設(shè)哈夫曼樹中有199個結(jié)點(diǎn)，則該哈夫曼樹中有（）個葉子結(jié)點(diǎn)。A．99 B．100C．101 D．102答案：B解釋：在哈夫曼樹中沒有度為1的結(jié)點(diǎn)，只有度為0（葉子結(jié)點(diǎn)）和度為2的結(jié)點(diǎn)。設(shè)葉子結(jié)點(diǎn)的個數(shù)為n0，度為2的結(jié)點(diǎn)的個數(shù)為n2，由二叉樹的性質(zhì)n0=n2+1，則總結(jié)點(diǎn)數(shù)n=n0+n2=2*n0-1，得到n0=100。若X是二叉中序線索樹中一個有左孩子的結(jié)點(diǎn)，且X不為根，則X的前驅(qū)為（）A．X的雙親B．X的右子樹中最左的結(jié)點(diǎn)C．X的左子樹中最右結(jié)點(diǎn)D．X的左子樹中最右葉結(jié)點(diǎn)答案：C引入二叉線索樹的目的是（）A．加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B．為了能在二叉樹中方便的進(jìn)行插入與刪除C．為了能方便的找到雙親D．使二叉樹的遍歷結(jié)果唯一答案：A（14）設(shè)F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（）個。A．n?1 B．n C．n+1 D．n+2答案：C（15）n（n≥2）個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯誤的是（

）。A．該樹一定是一棵完全二叉樹B．樹中一定沒有度為1的結(jié)點(diǎn)C．樹中兩個權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)D．樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值答案：A解釋：哈夫曼樹的構(gòu)造過程是每次都選取權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，所以樹中一定沒有度為1的結(jié)點(diǎn)、兩個權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)、任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值。2．應(yīng)用題1試找出滿足下列條件的二叉樹=1\*GB3①先序序列與后序序列相同=2\*GB3②中序序列與后序序列相同=3\*GB3③先序序列與中序序列相同=4\*GB3④中序序列與層次遍歷序列相同先序遍歷二叉樹的順序是“根—左子樹—右子樹”，中序遍歷“左子樹—根—右子樹”，后序遍歷順序是：“左子樹—右子樹―根＂，根據(jù)以上原則有=1\*GB3①或?yàn)榭諛洌驗(yàn)橹挥懈Y(jié)點(diǎn)的二叉樹=2\*GB3②

或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有左子樹的二叉樹．=3\*GB3③

或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹．=4\*GB3④或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹2設(shè)一棵二叉樹的先序序列：ABDFCEGH，中序序列：BFDAGEHC=1\*GB3①畫出這棵二叉樹。=2\*GB3②畫出這棵二叉樹的后序線索樹。=3\*GB3③將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹（或森林）。答案：ABABFD③CEHG=1\*GB3①=2\*GB3②3假設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。=1\*GB3①試為這8個字母設(shè)計(jì)赫夫曼編碼。=2\*GB3②試設(shè)計(jì)另一種由二進(jìn)制表示的等長編碼方案。=3\*GB3③對于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。答案：方案1；哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹。w={7,19,2,6,32,3,21,10}，按哈夫曼規(guī)則：【[（2,3），6],(7,10)】,……19,21,32（100）（40）（60）（28）（17）（11）7106（5）2301010101213210101106123方案比較：字母編號對應(yīng)編碼字母編號對應(yīng)編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10字母編號對應(yīng)編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10方案1的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結(jié)論：哈夫曼編碼優(yōu)于等長二進(jìn)制編碼

4已知下列字符A、B、C、D、E、F、G的權(quán)值分別為3、12、7、4、2、8，11，試填寫出其對應(yīng)哈夫曼樹HT的存儲結(jié)構(gòu)的初態(tài)和終態(tài)。答案：初態(tài):

weightparentlchildrchild13000212000370004400052000680007110008

0009

00010

00011

00012

00013

000終態(tài)：

weightparentlchildrchild138002121200371000449005280068100071111008595199114810151236112013971227132101347011123．算法設(shè)計(jì)題編寫以下算法：（1）統(tǒng)計(jì)二叉樹的葉結(jié)點(diǎn)個數(shù)。[題目分析]如果二叉樹為空，返回0，如果二叉樹不為空且左右子樹為空，返回1，如果二叉樹不為空，且左右子樹不同時為空，返回左子樹中葉子節(jié)點(diǎn)個數(shù)加上右子樹中葉子節(jié)點(diǎn)個數(shù)。[算法描述]intLeafNodeCount(BiTreeT){ if(T==NULL) return0;//如果是空樹，則葉子結(jié)點(diǎn)個數(shù)為0 elseif(T->lchild==NULL&&T->rchild==NULL) return1;//判斷結(jié)點(diǎn)是否是葉子結(jié)點(diǎn)（左孩子右孩子都為空），若是則返回1 else returnLeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);}（2）判別兩棵樹是否相等。[題目分析]先判斷當(dāng)前節(jié)點(diǎn)是否相等(需要處理為空、是否都為空、是否相等)，如果當(dāng)前節(jié)點(diǎn)不相等，直接返回兩棵樹不相等;如果當(dāng)前節(jié)點(diǎn)相等，那么就遞歸的判斷他們的左右孩子是否相等。[算法描述]intpareTree(TreeNode*tree1,TreeNode*tree2)//用分治的方法做，比較當(dāng)前根，然后比較左子樹和右子樹{booltree1IsNull=(tree1==NULL);booltree2IsNull=(tree2==NULL);if(tree1IsNull!=tree2IsNull){return1;}if(tree1IsNull&&tree2IsNull){//如果兩個都是NULL，則相等return0;}//如果根節(jié)點(diǎn)不相等，直接返回不相等，否則的話，看看他們孩子相等不相等if(tree1->c!=tree2->c){return1;}return(pareTree(tree1->left,tree2->left)&pareTree(tree1->right,tree2->right))(pareTree(tree1->left,tree2->right)&pareTree(tree1->right,tree2->left));}//算法結(jié)束3交換二叉樹每個結(jié)點(diǎn)的左孩子和右孩子。[題目分析]如果某結(jié)點(diǎn)左右子樹為空，返回，否則交換該結(jié)點(diǎn)左右孩子，然后遞歸交換左右子樹。[算法描述]voidChangeLR(BiTree&T){ BiTreetemp; if(T->lchild==NULL&&T->rchild==NULL) return; else { temp=T->lchild; T->lchild=T->rchild; T->rchild=temp; }//交換左右孩子 ChangeLR(T->lchild);//遞歸交換左子樹 ChangeLR(T->rchild);//遞歸交換右子樹}4設(shè)計(jì)二叉樹的雙序遍歷算法（雙序遍歷是指對于二叉樹的每一個結(jié)點(diǎn)來說，先訪問這個結(jié)點(diǎn)，再按雙序遍歷它的左子樹，然后再一次訪問這個結(jié)點(diǎn)，接下來按雙序遍歷它的右子樹）。[題目分析]若樹為空，返回；若某結(jié)點(diǎn)為葉子結(jié)點(diǎn)，則僅輸出該結(jié)點(diǎn)；否則先輸出該結(jié)點(diǎn)，遞歸遍歷其左子樹，再輸出該結(jié)點(diǎn)，遞歸遍歷其右子樹。[算法描述]voidDoubleTraverse(BiTreeT){ if(T==NULL) return; elseif(T->lchild==NULL&&T->rchild==NULL) cout<<T->data;//葉子結(jié)點(diǎn)輸出 else { cout<<T->data; DoubleTraverse(T->lchild);//遞歸遍歷左子樹 cout<<T->data; DoubleTraverse(T->rchild);//遞歸遍歷右子樹 }}5計(jì)算二叉樹最大的寬度（二叉樹的最大寬度是指二叉樹所有層中結(jié)點(diǎn)個數(shù)的最大值）。[題目分析]求二叉樹高度的算法見上題。求最大寬度可采用層次遍歷的方法，記下各層結(jié)點(diǎn)數(shù)，每層遍歷完畢，若結(jié)點(diǎn)數(shù)大于原先最大寬度，則修改最大寬度。[算法描述]intWidth(BiTreebt)//求二叉樹bt的最大寬度{if(bt==null)return(0);//空二叉樹寬度為0else{BiTreeQ[];//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記局部寬度,maxw記最大寬度Q[rear]=bt;//根結(jié)點(diǎn)入隊(duì)列while(front<=last) {p=Q[front++];temp++;//同層元素數(shù)加1if(p->lchild!=null)Q[++rear]=p->lchild;//左子女入隊(duì)if(p->rchild!=null)Q[++rear]=p->rchild;//右子女入隊(duì)if(front>last)//一層結(jié)束， {last=rear;if(temp>maxw)maxw=temp;//last指向下層最右元素,更新當(dāng)前最大寬度 temp=0;}//if}//whilereturn(maxw);}//結(jié)束width6用按層次順序遍歷二叉樹的方法，統(tǒng)計(jì)樹中具有度為1的結(jié)點(diǎn)數(shù)目。[題目分析]若某個結(jié)點(diǎn)左子樹空右子樹非空或者右子樹空左子樹非空，則該結(jié)點(diǎn)為度為1的結(jié)點(diǎn)[算法描述]intLevel(BiTreebt)//層次遍歷二叉樹，并統(tǒng)計(jì)度為1的結(jié)點(diǎn)的個數(shù){intnum=0;//num統(tǒng)計(jì)度為1的結(jié)點(diǎn)的個數(shù)if(bt){QueueInit(Q);QueueIn(Q,bt);//Q是以二叉樹結(jié)點(diǎn)指針為元素的隊(duì)列while(!QueueEmpty(Q)){p=QueueOut(Q);cout<<p->data;//出隊(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)QueueIn(Q,p->rchild);//非空右子女入隊(duì)}//while(!QueueEmpty(Q))}//if(bt)return(num);}//返回度為1的結(jié)點(diǎn)的個數(shù)7求任意二叉樹中第一條最長的路徑長度，并輸出此路徑上各結(jié)點(diǎn)的值。[題目分析]因?yàn)楹笮虮闅v棧中保留當(dāng)前結(jié)點(diǎn)的祖先的信息，用一變量保存棧的最高棧頂指針，每當(dāng)退棧時，棧頂指針高于保存最高棧頂指針的值時，則將該棧倒入輔助棧中，輔助棧始終保存最長路徑長度上的結(jié)點(diǎn)，直至后序遍歷完畢，則輔助棧中內(nèi)容即為所求。[算法描述]voidLongestPath(BiTreebt)//求二叉樹中的第一條最長路徑長度{BiTreep=bt,l[],s[];//l,s是棧，元素是二叉樹結(jié)點(diǎn)指針，l中保留當(dāng)前最長路徑中的結(jié)點(diǎn)inti，top=0,tag[],longest=0;while(p||top>0){while(p){s[++top]=p；tag[top]=0;p=p->Lc;}//沿左分枝向下if(tag[top]==1)//當(dāng)前結(jié)點(diǎn)的右分枝已遍歷{if(!s[top]->Lc&&!s[top]->Rc)//只有到葉子結(jié)點(diǎn)時，才查看路徑長度if(