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