數(shù)據(jù)結(jié)構(gòu)樹(shù)的測(cè)試題(二)-文庫(kù)吧資料
2025-03-31 03:01本頁(yè)面
【正文】 t!=p amp。 while(bt!=null ||top0){while(bt!=null amp。{top=0。stack s[],s1[]。int tag。再繼續(xù)遍歷到結(jié)點(diǎn)q時(shí)，將棧中元素從棧頂開(kāi)始逐個(gè)到輔助棧中去匹配，第一個(gè)匹配（即相等）的元素就是結(jié)點(diǎn)p 和q的最近公共祖先。后序遍歷必然先遍歷到結(jié)點(diǎn)p，棧中元素均為p的祖先。采用后序非遞歸算法，棧中存放二叉樹(shù)結(jié)點(diǎn)的指針，當(dāng)訪問(wèn)到某結(jié)點(diǎn)時(shí)，棧中所有元素均為該結(jié)點(diǎn)的祖先。判斷時(shí)易犯的錯(cuò)誤是證明其左子樹(shù)和右子數(shù)都是完全二叉樹(shù)，由此推出整棵二叉樹(shù)必是完全二叉樹(shù)的錯(cuò)誤結(jié)論。 } //whilereturn 1。 //右子女入隊(duì) else if (prchild) return 0。amp。 //前邊已有結(jié)點(diǎn)為空，本結(jié)點(diǎn)不空 else tag=1。 !tag) QueueIn(Q,plchild)。 //出隊(duì) if (plchild amp。 QueueIn(Q,p)。 // Q是隊(duì)列，元素是二叉樹(shù)結(jié)點(diǎn)指針，容量足夠大if(p==null) return (1)。}//結(jié)束 BiTreeint JudgeComplete(BiTree bt) //判斷二叉樹(shù)是否是完全二叉樹(shù),如是，返回1，否則，返回0{int tag=0。 btrchild=creat()。btdata=x。 //本題假定結(jié)點(diǎn)數(shù)據(jù)域?yàn)檎蚷f(x==0) bt=null。scanf(“%d”,amp。判定是否是完全二叉樹(shù)，可以使用隊(duì)列，在遍歷中利用完全二叉樹(shù)“若某結(jié)點(diǎn)無(wú)左子女就不應(yīng)有右子女”的原則進(jìn)行判斷。7．字符A，B，C，D出現(xiàn)的次數(shù)為9,1,5,3。HGDACJIBFEMPONKOL5.6．（l）圖略；（2） (3) 結(jié)點(diǎn)n(n1)的前一結(jié)點(diǎn)編號(hào)為n1（其最右邊子女編號(hào)是(n1)*k+1），故結(jié)點(diǎn) n的第 i個(gè)孩子的編號(hào)是(n1)*k+1+i。n2)/k4．(1)kh1(h為層數(shù))（2）因?yàn)樵摌?shù)每層上均有Kh1個(gè)結(jié)點(diǎn)，從根開(kāi)始編號(hào)為1，則結(jié)點(diǎn)i的從右向左數(shù)第２個(gè)孩子的結(jié)點(diǎn)編號(hào)為ki。中根序列：B C D A F E H J I G。二叉樹(shù)不是樹(shù)的特例。+17．48．任何結(jié)點(diǎn)至多只有右子女的二叉樹(shù)。 prchlid==null 2.(1)2k1 (2)2k13．644. 2n n1 n+1 5． 先序遍歷 后序遍歷 中序遍歷 6．.(1)2k2+1（第k層1個(gè)結(jié)點(diǎn)，總結(jié)點(diǎn)個(gè)數(shù)是2H1，其雙親是2H1/2=2k2）(2) 235。√三、填空題1．plchild==null amp。15．霍夫曼樹(shù)的結(jié)點(diǎn)個(gè)數(shù)不能是偶數(shù)。13．度為二的樹(shù)就是二叉樹(shù)。11．樹(shù)形結(jié)構(gòu)中元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系。9. 給定一棵樹(shù)，可以找到唯一的一棵二叉樹(shù)與之對(duì)應(yīng)。6．中序遍歷一棵二叉排序樹(shù)的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列 √7．完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它必是樹(shù)葉。√4. 一棵一般樹(shù)的結(jié)點(diǎn)的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹(shù)的結(jié)點(diǎn)前序遍歷和后序遍歷是一致的。2. 對(duì)于有N個(gè)結(jié)點(diǎn)的二叉樹(shù)，其高度為log2n。（3）畫(huà)出二叉樹(shù)的后序線索樹(shù)。試完成下列各題:（l）畫(huà)出二叉樹(shù)BT的邏輯結(jié)構(gòu)。（只要求給出轉(zhuǎn)換結(jié)果）NPGHJMOLIKEDFBAC3．分別給出下圖所示二叉樹(shù)的先根、中根和后根序列。10．若一個(gè)二叉樹(shù)的葉子結(jié)點(diǎn)是某子樹(shù)的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的____ __序列中的最后一個(gè)結(jié)點(diǎn)。8．二叉樹(shù)的先序序列和中序序列相同的條件是___ ___。6．一個(gè)深度為k的，具有最少結(jié)點(diǎn)數(shù)的完全二叉樹(shù)按層次，（同層次從左到右）用自然數(shù)依此對(duì)結(jié)點(diǎn)編號(hào)，則編號(hào)最小的葉子的序號(hào)是__ _；編號(hào)是i的結(jié)點(diǎn)所在的層次號(hào)是_ __（根所在的層次號(hào)規(guī)定為1層）。,一共有________個(gè)指針域,其中只有________個(gè)用來(lái)指向結(jié)點(diǎn)的左右孩子，其余的________個(gè)指針域?yàn)镹ULL。2．深度為k的完全二叉樹(shù)至少有___ ____個(gè)結(jié)點(diǎn)，至多有___ ____個(gè)結(jié)點(diǎn)。( )13．度為二的樹(shù)就是二叉樹(shù)。( )11．樹(shù)形結(jié)構(gòu)中元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系。( )9. 給定一棵樹(shù)，可以找到唯一的一棵二叉樹(shù)與之對(duì)應(yīng)。 ( )7．完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它必是樹(shù)葉。( )5. 用一維數(shù)組存儲(chǔ)二叉樹(shù)時(shí)，總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn)。( )3. 二叉樹(shù)的遍歷只是為了在應(yīng)用中找到一種線性次序。A．左子結(jié)點(diǎn) B．右子結(jié)點(diǎn) C．左子結(jié)點(diǎn)和
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1