二叉樹(shù)習(xí)題answer

1、一、下面是有關(guān)二叉樹(shù)的表達(dá),請(qǐng)判斷正誤()().假設(shè)二叉樹(shù)用二叉鏈表作存貯結(jié)構(gòu),那么在n個(gè)結(jié)點(diǎn)的二叉樹(shù)鏈表中只有n1個(gè)非空指針域.().二叉樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)的高度差等于1.().二叉樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)是有序的.().二叉樹(shù)中每個(gè)結(jié)點(diǎn)有兩棵非空子樹(shù)或有兩棵空子樹(shù).()二叉樹(shù)中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹(shù)(假設(shè)存在的話)所有結(jié)點(diǎn)的關(guān)鍵字值,且小于其右 非空子樹(shù)(假設(shè)存在的話)所有結(jié)點(diǎn)的關(guān)鍵字值.(應(yīng)當(dāng)是二叉排序樹(shù)的特點(diǎn))().二叉樹(shù)中所有結(jié)點(diǎn)個(gè)數(shù)是 2k-1-1 ,其中k是樹(shù)的深度.(應(yīng)2i-1 )().二叉樹(shù)中所有結(jié)點(diǎn),如果不存在非空左子樹(shù),那么不存在非空右子樹(shù).().對(duì)于一棵非

2、空二叉樹(shù),它的根結(jié)點(diǎn)作為第一層,那么它的第 i層上最多能有2i 1個(gè)結(jié)點(diǎn).(應(yīng)2i-1 )()用二叉鏈表法(link-rlink )存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù),結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有 n+1個(gè)為空指針.(正確.用二叉鏈表存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù),結(jié)點(diǎn)共有 2n個(gè)鏈域.由于二叉樹(shù)中,除根結(jié)點(diǎn)外,每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親,所以只有n-1個(gè)結(jié)點(diǎn)的鏈域存放指向非空子女結(jié)點(diǎn)的指針,還有n+1個(gè)空指針.)即有后繼鏈接的指針僅 n-1個(gè).(,)10.具有12個(gè)結(jié)點(diǎn)的完全二叉樹(shù)有 5個(gè)度為2的結(jié)點(diǎn).最快方法：用葉子數(shù)= n/2 =6,再求n2=no-1=5二、填空()1 .由3個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹(shù)有5種形態(tài)

3、.2 . 一棵深度為 6的滿二叉樹(shù)有 m+n2=0+ n 2= n o-1=31 個(gè)分支結(jié)點(diǎn)和 26-1 =32 個(gè)葉子.注：滿二叉樹(shù)沒(méi)有度為 1的結(jié)點(diǎn),所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù).3 . 一棵具有2 5 7個(gè)結(jié)點(diǎn)的完全二叉樹(shù),它的深度為9.(注：用 10g 2(n)+1=+1=94 .設(shè)一棵完全二叉樹(shù)有 700個(gè)結(jié)點(diǎn),那么共有 350個(gè)葉子結(jié)點(diǎn).答：最快方法：用葉子數(shù)= n/2 =3505 .設(shè)一棵完全二叉樹(shù)具有1000個(gè)結(jié)點(diǎn),那么此完全二叉樹(shù)有500個(gè)葉子結(jié)點(diǎn),有 499 個(gè)度為2的結(jié)點(diǎn),有 1個(gè)結(jié)點(diǎn)只有非空左子樹(shù),有 0個(gè)結(jié)點(diǎn)只有非空右子樹(shù).答：最快方法：用葉子數(shù)=n/2 =500 ,

4、 n2=n0-1=499.另外,最后一結(jié)點(diǎn)為 2i屬于左葉子,右葉子是空的,所以有1個(gè)非空左子樹(shù).完全二叉樹(shù)的特點(diǎn)決定不可能有左空右不空的情況,所以非空右子樹(shù)數(shù)=0.6 . 一棵含有n個(gè)結(jié)點(diǎn)的k叉樹(shù),可能到達(dá)的最大深度為n ,最小深度為 J o答：當(dāng)k=1單叉樹(shù)時(shí)應(yīng)該最深,深度=n 層；當(dāng)k=n-1 n-1叉樹(shù)時(shí)應(yīng)該最淺,深度= 2 層,但不包n=0或1時(shí)的特例情況.教材答案是“完全k叉樹(shù)",未定量.7 .二叉樹(shù)的根本組成局部是：根N、左子樹(shù)L和右子樹(shù)R.因而二叉樹(shù)的遍歷次序有六種.最常用的是三種：前序法即按 N L R次序,后序法即按 L R N 次序和中序法也稱(chēng)對(duì)稱(chēng)序法,即按L

5、N R次序.這三種方法相互之間有關(guān)聯(lián).假設(shè)一棵二叉樹(shù)的前序序列是 BEFCGDH中序序列是FEBGCHD那么它的后序序列必是 _F E G H D C B.解：法1:先由條件畫(huà)圖,再后序遍歷得到結(jié)果；法2:不畫(huà)圖也能快速得出后序序列,只要找到根的位置特征.由前序先確定root ,由中序先確定左子樹(shù).例如,前序遍歷BEFCGDH3,根結(jié)點(diǎn)在最前面,是 B;那么后序遍歷中B 一定在最后面.法3:遞歸計(jì)算.如 B在前序序列中第一,中序中在中間可知左右子樹(shù)上有哪些元素,那么在后序中必為最后.如法對(duì) B的左右子樹(shù)同樣處理,那么問(wèn)題得解.8 .中序遍歷的遞歸算法平均空間復(fù)雜度為On q答：即遞歸最大嵌套層

6、數(shù),即棧的占用單元數(shù).精確值應(yīng)為樹(shù)的深度k+1,包括葉子的空域也遞歸了一次.9 .用5個(gè)權(quán)值3, 2, 4, 5, 1 構(gòu)造的哈夫曼Huffman樹(shù)的帶權(quán)路徑長(zhǎng)度是33.4 5 3(3)解：先構(gòu)造哈夫曼樹(shù),得到各葉子的路徑長(zhǎng)度之后便可求出WPL= 4+5+3 X 2+ 1+2 X 3=33注：兩個(gè)合并值先后不同會(huì)導(dǎo)致編碼不同,即哈夫曼編碼不唯一 注：合并值應(yīng)排在葉子值之后(注：原題為選擇題：A.32C. 34D. 15)三、單項(xiàng)選擇題()(0)1. 不含任何結(jié)點(diǎn)的空樹(shù) .(A) 是一一棵樹(shù)；(B)是一一棵二叉樹(shù)；(C)是一棵樹(shù)也是一棵二叉樹(shù)；(D)既不是樹(shù)也不是二叉樹(shù)答：以前的標(biāo)答是 B,由于

7、那時(shí)樹(shù)的定義是 n>1(0)2.二叉樹(shù)是非線性數(shù)據(jù)結(jié)構(gòu),所以 .(A)它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)；(B)它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)；(C)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)；(D)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用(0 ) 3.具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 .(A)log 2(n)( B ) log 2(n)( C) log 2(n)+1 ( D)log 2(n)+1注1: x 表示不小于x的最小整數(shù)；x 表示不大于x的最大整數(shù),它們與含義不同！注2：選(A)是錯(cuò)誤的.例如當(dāng) n為2的整數(shù)哥時(shí)就會(huì)少算一層.似乎 log 2(n) +1 是對(duì)的(A ) 4.把一棵樹(shù)轉(zhuǎn)換為

8、二叉樹(shù)后,這棵二叉樹(shù)的形態(tài)是 .(A)唯一的(B)有多種(C)有多種,但根結(jié)點(diǎn)都沒(méi)有左孩子(D)有多種,但根結(jié)點(diǎn)都沒(méi)有右孩子5 .從供選擇的答案中,選出應(yīng)填入下面表達(dá) 內(nèi)的最確切的解答,把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi).樹(shù)是結(jié)點(diǎn)的有PM集合,它 絲 根結(jié)點(diǎn),記為T(mén)o其余的結(jié)點(diǎn)分成為 m (俏0)個(gè)-B的集合T1, T2,Tm每個(gè)集合又都是樹(shù), 此時(shí)結(jié)點(diǎn)T稱(chēng)為T(mén)的父結(jié)點(diǎn),Ti稱(chēng)為T(mén)的子結(jié)點(diǎn)(1<i <m)o一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的0.供選擇的答案A: 有0個(gè)或1個(gè)有0個(gè)或多個(gè)有且只有1個(gè) 有1個(gè)或1個(gè)以上B: 互不相交允許相交允許葉結(jié)點(diǎn)相交允許樹(shù)枝結(jié)點(diǎn)相交C:權(quán)維數(shù)次數(shù)(或度)答案

9、：ABC= 1, 1, 36 .從供選擇的答案中,選出應(yīng)填入下面表達(dá) 內(nèi)的最確切的解答,把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi).二叉樹(shù) A .在完全的二叉樹(shù)中,假設(shè)一個(gè)結(jié)點(diǎn)沒(méi)有b,那么它必定是葉結(jié)點(diǎn).每棵樹(shù)都能惟一地轉(zhuǎn)換成與它對(duì)應(yīng)的二叉樹(shù).由樹(shù)轉(zhuǎn)換成的二叉樹(shù)里,一個(gè)結(jié)點(diǎn)N的左子女是N在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的 C而N的右子女是它在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的D.供選擇的答案A:是特殊的樹(shù)不是樹(shù)的特殊形式是兩棵樹(shù)的總稱(chēng)有是只有二個(gè)根結(jié)點(diǎn)的樹(shù)形結(jié)構(gòu)B: 左子結(jié)點(diǎn)右子結(jié)點(diǎn) 左子結(jié)點(diǎn)或者沒(méi)有右子結(jié)點(diǎn)兄弟CD:最左子結(jié)點(diǎn)最右子結(jié)點(diǎn)最鄰近的右兄弟最鄰近的左兄弟最左的兄弟 最右的兄弟答案：A= B= C= D =答案：ABODE 2,

10、1, 1, 3四、簡(jiǎn)做題()1 . 一棵度為2的樹(shù)與一棵二叉樹(shù)有何區(qū)別答：度為2的樹(shù)從形式上看與二叉樹(shù)很相似,但它的子樹(shù)是無(wú)序的,而二叉樹(shù)是有序的.即,在一般樹(shù)中假設(shè)某結(jié)點(diǎn)只有一個(gè)孩子,就無(wú)需區(qū)分其左右次序,而在二叉樹(shù)中即使是一個(gè)孩子也有左右之分 .2 .設(shè)如以下圖所示的二叉樹(shù)B的存儲(chǔ)結(jié)構(gòu)為二叉鏈表,root為根指針,結(jié)點(diǎn)結(jié)構(gòu)為：(lchild,data,rchild ).其中 Ichild , rchild 分別為指向左右孩子的指針,data為字符型,root為根指針,試答復(fù)以下 問(wèn)題：1 .對(duì)以下二叉樹(shù) B,執(zhí)行以下算法 traversal(root),試指出其輸出結(jié)果；2 .假定二叉樹(shù)B

11、共有n個(gè)結(jié)點(diǎn),試分析算法traversal(root) 的時(shí)C的結(jié)點(diǎn)類(lèi)型定義如下：struct nodechar data;struct node * lchild,)；rchild;C算法如下：void traversal(struct*root)if (root)node間復(fù)雜度.(共8分)解：這是“先根再左再根再右,比前序遍歷多打印各結(jié)點(diǎn)一次,輸出結(jié)果為：A B C C E E B A D F F D GG特點(diǎn)：每個(gè)結(jié)點(diǎn)肯定都會(huì)被打印兩次；但出現(xiàn)的順序不同,其規(guī)律是：但凡有左子樹(shù)的結(jié)點(diǎn),必間隔左子樹(shù)的全部結(jié)點(diǎn)后再重復(fù)出現(xiàn)；如A, B, D等結(jié)點(diǎn).反之馬上就會(huì)重復(fù)出現(xiàn).如C, E, F,

12、G等結(jié)點(diǎn).時(shí)間復(fù)雜度以訪問(wèn)結(jié)點(diǎn)的次數(shù)為主,精確值為2*n ,時(shí)間漸近度為 O(n).3 .給定二叉樹(shù)的兩種遍歷序列,分別是：前序遍歷序列：D,A,C,E,B,H,F,G,I ;中序遍歷序列：D,C,B,E,H,A,G I ,F,試畫(huà)出二叉樹(shù)B,并簡(jiǎn)述由任意二叉樹(shù) B的前序遍歷序列和中序遍歷序列求二叉樹(shù)B的思想方法.解：方法是：由前序先確定 root ,由中序可確定root的左、右子樹(shù).然后由其左子樹(shù)的元素集合和右子樹(shù)的集合對(duì)應(yīng)前序遍歷序列中的元素集合,可繼續(xù)確定root的左右孩子.將他們分別作為新的root ,不斷遞歸,那么所有元素都將被唯一確定,問(wèn)題得解.2840 60 08 544 .給定

13、如下圖二叉樹(shù) T,請(qǐng)畫(huà)出與其對(duì)應(yīng)的中序線索二叉樹(shù).解：要遵循中序遍歷的軌跡來(lái)畫(huà)出每個(gè)前驅(qū)和后繼.中序遍歷序列：55 40 25 60 28 08 33 5428254J “6*0段 5455五、閱讀分析題1.試寫(xiě)出如下圖的二叉樹(shù)分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列.答：DLR A B D F J G K C E H I L MLDR: B F J D G K A C H E L I MLRD J F K G D B H L M I E C A答：注意全部兄弟之間都要連線 包括度為2的兄弟,并注意原有連線結(jié)點(diǎn)一律歸入左子樹(shù),新添連線結(jié)點(diǎn)一律歸入右子樹(shù).%、C產(chǎn)、K、F H D /L G I

14、.M J3 .閱讀以下算法,假設(shè)有錯(cuò),改正之.BiTree InSuccBiTree q/q是指向中序線索二叉樹(shù)上某個(gè)結(jié)點(diǎn)的指針,/本函數(shù)返回指向*q的后繼的指針.r=q->rchild;/ 應(yīng)改為 r=q ;答：這是找結(jié)點(diǎn)后繼的程序.共有3處錯(cuò)誤.注：當(dāng)rtag =1時(shí)說(shuō)明內(nèi)裝后繼指針,可直接返回,第一句無(wú)錯(cuò).當(dāng)rtag =0時(shí)說(shuō)明內(nèi)裝右孩子指針,但孩子擊必是后繼,需要計(jì)算,中序遍歷應(yīng)當(dāng)4 .畫(huà)出和以下二叉樹(shù)相應(yīng)的森林.答：注意根右邊的子樹(shù)肯定是森林,而孩子結(jié)點(diǎn)的右子樹(shù)均為兄弟.六、算法設(shè)計(jì)題()1.編寫(xiě)遞歸算法,計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目.解：思路：輸出葉子結(jié)點(diǎn)比擬簡(jiǎn)單,用任何一種遍

15、歷遞歸算法,但凡左右指針均空者,那么為葉子,將其打印出來(lái).法一：核心局部為：DLR(liuyu *root) /* 中序遍歷遞歸函數(shù)*/if(root!=NULL)if(root->lchild=NULL)&&(root->rchild=NULL)sum+; printf("%dn",root->data);DLR(root->lchild);DLR(root->rchild); return(0);法二：int LeafCount_BiTree(Bitreb T)12編程：生成二叉樹(shù)排序樹(shù)之后,再中序遍歷排序查找結(jié)點(diǎn)的完整程序

16、如下：說(shuō)明局部為：#include <>#include <>typedef struct liuyuint data;struct liuyu *lchild,*rchild;test;liuyu *root;int sum=0;int m=sizeof(test);void insert_data(int x) /*如何生成二叉排序樹(shù)參見(jiàn)教材P43C程序*/ liuyu *p,*q,*s;s=(test*)malloc(m);s->data=x;s->lchild=NULL;s->rchild=NULL;if(!root)root=s; retur

17、n;p=root;while(p)/*如何接入二叉排序樹(shù)的適當(dāng)位置*/q=p;if(p->data=x)printf("data already exist! n");return;else if(x<p->data)p=p->lchild; else p=p->rchild;if(x<q->data)q->lchild=s;else q->rchild=s;DLR(liuyu *root) /*中序遍歷遞歸函數(shù)*/if(root!=NULL)if(root->lchild=NULL)&&(root

18、->rchild=NULL)sum+; printf("%dn",root->data);DLR(root->lchild);DLR(root->rchild); return(0);main() /*先生成二叉排序樹(shù),再調(diào)用中序遍歷遞歸函數(shù)進(jìn)行排序輸出*/int i,x;i=1;root=NULL; /*千萬(wàn)別忘了賦初值給 root!*/doprintf("please input data%d:",i);i+;scanf("%d",&x);/*從鍵盤(pán)采集數(shù)據(jù),以-9999表示輸入結(jié)束*/if(x=-

19、9999)DLR(root);printf("nNow output count value:%dn",sum);return(0); else insert_data(x); /*調(diào)用插入數(shù)據(jù)元素的函數(shù)*/while(x!=-9999);return(0);Iftactlva x)3 1 s 1 2_右一開(kāi)始運(yùn)行就輸入-9999 ,那么無(wú)葉子輸出,sum=Q2.寫(xiě)出求二叉樹(shù)深度的算法,先定義二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型.編寫(xiě)遞歸算法,求二叉樹(shù)中以元素值為x的結(jié)點(diǎn)為根的子樹(shù)的深度.答；設(shè)計(jì)思路：只查后繼鏈表指針,假設(shè)左或右孩子的左或右指針?lè)强?那么層次數(shù)加但注意,遞歸時(shí)應(yīng)當(dāng)從葉子開(kāi)

20、始向上計(jì)數(shù),否那么不易確定層數(shù).1;否那么函數(shù)返回.int depth(liuyu*root) /*int d,p;/*p=0;if(root=NULL)return(p); /*elsed=depth(root->lchild);if(d>p) p=d; /*d=depth(root->rchild);統(tǒng)計(jì)層數(shù)*/注意每一層的局部變量d,p都是各自獨(dú)立的*/找到葉子之后才開(kāi)始統(tǒng)計(jì) */向上回朔時(shí),要挑出左右子樹(shù)中的相對(duì)大的那個(gè)深度值*/if(d>p)p=d;p=p+1;return(p);plvasvinputdatal：INinputdata2：Rpleaseinp

21、utdatalilTpleadsinputpls 感.inputdaWJSplinputdBta；2plvasrinputdmWT： 13plea二0input!9plogainputdata!:21inputinputint1281721116 21T,intinputdAtbl,1 2pl吞占"inputdm2 ;ainputdata：1 7pl*己inputdataHi1 1pleas*inputdataS：1 Gpleachinput2inputdata7：1 3input9ploaovinputdata9：2 1pinputdataie：4pleaseinputdatal1

22、：-9939Get_Sub_Depth(BitreeHl Unactive- x)Non output dtpth glue叫x) 43C寫(xiě)按層次順序同一層自左至右遍歷二叉樹(shù)的算法.或：按層次輸出二叉樹(shù)中所有結(jié)點(diǎn);解：思路：既然要求從上到下,從左到右,那么利用隊(duì)列存放各子樹(shù)結(jié)點(diǎn)的指針是個(gè)好方法.這是一個(gè)循環(huán)算法,用 while語(yǔ)句不斷循環(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,*q100;int f,r;f=0; r=0;/*r=(r+1)%max;qr=T;/*while(f!=r)/*f=(f+1%max); p=qf;/*假設(shè)max*/置空隊(duì)*/根結(jié)點(diǎn)進(jìn)隊(duì)*/隊(duì)列不空*/出隊(duì)*/printf("%d",p->data);/*打印根結(jié)點(diǎn)*/if(p->lchild)r=(r+1)%max; qr=p->lchild; /*假設(shè)左子樹(shù)不空,那么左子樹(shù)進(jìn)隊(duì)*/if(p->rchild)r=(r+1)%max; qr=p->rchild; /*假設(shè)右子樹(shù)不空,那么右子樹(shù)進(jìn)隊(duì) */return(0);法二：void LayerOrder(Bitre