單元7練習(xí)參考答案

單元練習(xí)7一．判斷題（下列各題，對(duì)的的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打√；錯(cuò)誤的打╳）（√）（1）樹構(gòu)造中每個(gè)結(jié)點(diǎn)最多只有一種直接前驅(qū)。（ㄨ）（2）完全二叉樹一定是滿二查樹。（ㄨ）（3）在中序線索二叉樹中，右線索若不為空，則一定指向其雙親。（√）（4）一棵二叉樹中序遍歷序列的最終一種結(jié)點(diǎn)，必然是該二叉樹前序遍歷的最終一種結(jié)點(diǎn)。（√）（5）二叉樹的前序遍歷中，任意一種結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面。（√）（6）由二叉樹的前序遍歷序列和中序遍歷序列，可以推導(dǎo)出后序遍歷的序列。（√）（7）在完全二叉樹中，若一種結(jié)點(diǎn)沒有左孩子，則它必然是葉子結(jié)點(diǎn)。二．填空題在樹中，一種結(jié)點(diǎn)所擁有的子樹數(shù)稱為該結(jié)點(diǎn)的度。度為零的結(jié)點(diǎn)稱為葉（或葉子，或終端）結(jié)點(diǎn)。樹中結(jié)點(diǎn)的最大層次稱為樹的深度（或高度）。對(duì)于二叉樹來說，第i層上至多有2i-1個(gè)結(jié)點(diǎn)。深度為h的二叉樹至多有2h-1個(gè)結(jié)點(diǎn)。由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹。有20個(gè)結(jié)點(diǎn)的完全二叉樹，編號(hào)為10的結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)是5。由二叉樹的后序和中序遍歷序列，可以唯一確定一棵二叉樹。某二叉樹的中序遍歷序列為:DEBAC，后序遍歷序列為：EBCAD。則前序遍歷序列為：DABEC。設(shè)一棵二叉樹結(jié)點(diǎn)的先序遍歷序歷為：ABDECFGH，中序遍歷序歷為：DEBAFCHG，則二叉樹中葉結(jié)點(diǎn)是：E、F、H。已知完全二叉樹的第8層有8個(gè)結(jié)點(diǎn)，則其葉結(jié)點(diǎn)數(shù)是68。采用二叉鏈表存儲(chǔ)的n個(gè)結(jié)點(diǎn)的二叉樹，一共有2n個(gè)指針域。采用二叉鏈表存儲(chǔ)的n個(gè)結(jié)點(diǎn)的二叉樹，共有空指針n+1個(gè)。前序?yàn)锳，B，C且后序?yàn)镃，B，A的二叉樹共有4種。AACBABCABCACB（18）將一棵完全二叉樹按層次編號(hào)，對(duì)于任意一種編號(hào)為i的結(jié)點(diǎn)，其左孩子結(jié)點(diǎn)的編號(hào)為：2*i。（19）給定如下圖所示的二叉樹，其前序遍歷序列為：ABEFHCG。AABFGHDCE（20）給定如下圖所示的二叉樹，其層次遍歷序列為：ABCEFGH。AABFGHDCE三．選擇題（1）樹最適合用來表達(dá)（D）。A．有序數(shù)據(jù)元素B．無序數(shù)據(jù)元素C．元素之間無聯(lián)絡(luò)的數(shù)據(jù)D．元素之間有分支的層次關(guān)系（2）前序?yàn)锳，B，C的二叉樹共有（D）種。A．2 B．3 C．4 D（3）根據(jù)二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有（C）種樹型。A．3 B．4 C．5 D．6（4）在一棵具有五層的滿二叉樹中，結(jié)點(diǎn)的總數(shù)為（B）A．16B．31C．32D．33（5）具有64個(gè)結(jié)點(diǎn)的完全二叉樹的深度為（C）A．5 B．6 C．7 D．8（6）任何一棵二叉樹的葉結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對(duì)次序（A）。A．不發(fā)生變化B．發(fā)生變化C．不能確定D．以上都不對(duì)（7）A，B為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，A在B前的條件是（C）。A．A在B右方B．A是B祖先C．A在B左方D．A是B子孫（8）下列4棵樹中，（B）不是完全二叉樹。A．B．C．D．ABECABECDABCDABEFCDABEGFDCD（9）如右圖所示的二叉樹，后序遍歷的序列是（D）ABADECFGHIA．A、B、C、D、ABADECFGHIB．A、B、D、H、I、E、C、F、GC．H、D、I、B、E、A、F、C、GD．H、I、D、E、B、F、G、C、A（10）對(duì)于下邊的二叉樹，其中序序列為（A）A．DBEHAFCGB．DBHEAFCGC．ABDEHCFGD．ABCDEFGH（11）某二叉樹的后序遍歷序列為：DABEC，中序遍歷序列為:DEBAC，則前序遍歷序列為（D）。A．ACBED B．DECAB C．DEABCD．CEDBA（12）具有n（n>1）個(gè)結(jié)點(diǎn)的完全二叉樹中，結(jié)點(diǎn)i（2i>n）的左孩子結(jié)點(diǎn)是（D）。A．2i B．2i+1 C．2i-1 D．不存在（若2i<=n，則答案為A）（13）把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（A）。A．唯一的B．有多種C．有多種，但根結(jié)點(diǎn)都沒有左孩子D．有多種，但根結(jié)點(diǎn)都沒有右孩子（14）將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為45的結(jié)點(diǎn)的左孩子編號(hào)為（B）。A．46 B．47 C．90 D（15）將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的右孩子編號(hào)為（B）。A．98 B．99 C．50 D．100（17）下列陳說對(duì)的的是（D）。A．二叉樹是度為2的有序樹 B．二叉樹中結(jié)點(diǎn)只有一種孩子時(shí)無左右之分C．二叉樹中必有度為2的結(jié)點(diǎn) D．二叉樹中最多只有兩棵子樹，且有左右子樹之分（20）二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)比度為2的結(jié)點(diǎn)的個(gè)數(shù)（C）。A．無關(guān) B．相等 C．多一種 D．少一種五.應(yīng)用題1．已知一棵二叉樹的后序遍歷和中序遍歷的序列分別為：A，C，D，B，G，I，H，F(xiàn)，E和A，B，C，D，E，F(xiàn)，G，H，I。請(qǐng)畫出該二叉樹，并寫出它的前序遍歷的序列。BCHDDBCHDDFGEIA其前序遍歷的序列為：EBADCFHGI2．已知一棵二叉樹的前序遍歷和中序遍歷的序列分別為：A，B，D，G，H，C，E，F(xiàn)，I和G，D，H，B，A，E，C，I，F(xiàn)。請(qǐng)畫出此二叉樹，并寫出它的后序遍歷的序列。。GHAGHABDCEFI其后序遍歷的序列為：GHDBEIFCA3．已知一棵樹的層次遍歷的序列為：ABCDEFGHIJ，中序遍歷的序列為：DBGEHJACIF，請(qǐng)畫出該二叉樹，并寫出它的后序遍歷的序列。ABABCHDDFGEIJ后序遍歷的序列：DGJHEBIFCA7．某二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用次序存儲(chǔ)，其構(gòu)造如下：1234567891011121314151617181920EAFDHCGIB（1）畫出該二叉樹（3分）（2）寫出按層次遍歷的結(jié)點(diǎn)序列（2分）解：ADADHFGECBI（2）層次遍歷的結(jié)點(diǎn)序列：EAFDHCGIB8．某二叉樹的存儲(chǔ)如下：12345678910lchild00237580101dataJHFDBACEGIrchild0009400000 其中根結(jié)點(diǎn)的指針為6，lchild、rchild分別為結(jié)點(diǎn)的左、右孩子的指針域，data為數(shù)據(jù)域。（1）畫出該二叉樹（3分）（2）寫出該樹的前序遍歷的結(jié)點(diǎn)序列（2分）解：BDBDJHGACFEIABCEDFHGIJ六．算法設(shè)計(jì)題以二叉鏈表為存儲(chǔ)構(gòu)造，設(shè)二叉樹BT構(gòu)造為：typedefstructBT{ chardata; BT*lchild; BT*rchild;}BT;1．求二叉樹中的度數(shù)為2的結(jié)點(diǎn)。2．求二叉樹中值為最大的元素。3．將二叉樹各結(jié)點(diǎn)存儲(chǔ)到一維數(shù)組中。4．前序輸出二叉樹中各結(jié)點(diǎn)及其結(jié)點(diǎn)所在的層號(hào)。5．求二叉樹的寬度6．互換二叉樹各結(jié)點(diǎn)的左右子樹。7．寫出在二叉樹中查找值為x的結(jié)點(diǎn)在樹中層數(shù)的算法。解：求二叉樹中的度數(shù)為2的結(jié)點(diǎn)。voidcount(BTt){if(t){if(t->lchild&&t->rchild)k++;count(t->lchild);count(t->rchild);}}求二叉樹中值為最大的元素。intmaxnode(BTt,intmax){if(t){if(t->data>max)max=t->data;max=maxnode(t->lchild,max);max=maxnode(t->rchild,max);}}3．將二叉樹各結(jié)點(diǎn)存儲(chǔ)到一維數(shù)組中。voidcreate(BTt,inta[],inti){if(t){a[i]=t->data;create(t->lchild,a,2*i);create(t->rchild,a,2*i+1);}}4．前序輸出二叉樹中各結(jié)點(diǎn)及其結(jié)點(diǎn)所在的層號(hào)。voidpreorderlevel(BTt,inth)//t的層數(shù)為h{if(t!=NULL){printf(“%d,%d”,t->data,h);preorderlevel(t->lchild,h+1);preorderlevel(t->rchild,h+1);}}求二叉樹的寬度思想：按層遍歷二叉樹，采用一種隊(duì)列q，讓根結(jié)點(diǎn)入隊(duì)列，最終出隊(duì)列，若有左右子樹，則左右子樹根結(jié)點(diǎn)入隊(duì)列，如此反復(fù)，直到隊(duì)列為空。intWidth(BT*T){intfront=-1,rear=-1;//隊(duì)列初始化intflag=0,count=0,p;//p用于指向樹中層的最右邊的結(jié)點(diǎn)，標(biāo)志flag記錄層中結(jié)點(diǎn)數(shù)的最大值if(T!=NULL){rear++;q[rear]=T;flag=1;p=rear;}while(front<p){front++;T=q[front];if(T->lchild!=NULL){rear++;q[rear]=T->lchild;count++;}if(T->rchild!=NULL){rear++;q[rear]=T->rchild;count++;}if(front==p) //目前層已遍歷完畢{if(flag<count)flag=count;count=0;p=rear; //p指向下一層最右邊的結(jié)點(diǎn)}} //endwhilereturn(flag);}6．解：借助棧來進(jìn)行對(duì)換。Swap(BinTree*T){BinTree*stack[100],*temp;inttop=-1;root=T;if(T!=NULL){top++;stack[top]=T;while(top>-1){T=stack[top];top--;if(T->child!=NULL||T->rchild!=NULL){//互換結(jié)點(diǎn)的左右指針temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;}if(T->lchild!=NULL){top++;stack[top]=T->lchild;}if(T->rchild!=NULL){top++;stack[top]=T->rchild;}}}}main(){intI,j,k,l;printf(“\n”);root=CreateBinTree();Inorder(root);i=CountNode(root);j=CountLeafs(root);k=Depth(