【正文】 二叉樹(shù)的所有不同形態(tài)?！?0. 用鏈表(llinkrlink)存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n1個(gè)空指針。后根序列：D C B F J I H G E A。else if(x0) {bt=(BiNode *)malloc(sizeof(BiNode))。 //首次出現(xiàn)結(jié)點(diǎn)為空 if (prchild amp。//tag=0 表示結(jié)點(diǎn)的左子女已被訪問(wèn)，tag=1表示結(jié)點(diǎn)的右子女已被訪問(wèn)}stack。 }//將棧s的元素轉(zhuǎn)入輔助棧s1 保存if(bt==q) //找到q 結(jié)點(diǎn)。 /*入隊(duì)列*/ while (not emptyqueue (q) ) /*若隊(duì)列非空*/ {outqueue (q, p) 。}}}5．．void InOrder(BiTree bt) {BiTree s[],p=bt。第一個(gè)葉子結(jié)點(diǎn)由指針head指向，遍歷到葉子結(jié)點(diǎn)時(shí)，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點(diǎn)的rchild為空。 DeleteXTree(btrchild)。c)。 else succ= pRChild。 q=qLChild)。 prchild=null。 } //InOrder時(shí)間復(fù)雜度為O(n),輔助變量使用head和pre,?？臻g復(fù)雜度O(n)8.[題目分析] 刪除以元素值x為根的子樹(shù)，只要能刪除其左右子樹(shù)，就可以釋放值為x的根結(jié)點(diǎn)，因此宜采用后序遍歷。btrchild=Copy(trchild)。 }else { Pop(amp。｝ //沿右分枝向下遍歷}//結(jié)束while(bt!=null ||top0)return(null)。} //沿左分枝向下if(bt==p) //不失一般性，假定p在q的左側(cè),遇結(jié)點(diǎn)p時(shí)，棧中元素均為p的祖先結(jié)點(diǎn){for(i=1。將?？饺肓硪惠o助棧中。amp。BiTree Creat() //建立二叉樹(shù)的二叉鏈表形式的存儲(chǔ)結(jié)構(gòu){ElemType x；BiTree bt。9．二叉排序樹(shù)10．前序11．6912． *count++, countleaf(lrchile,count)13．(1) p=plchild // 沿左子樹(shù)向下 （2）p=prchild 14．(1)0 （2）hlhr (3)hr=hl15．(1)prchild (2)plchild (3)plchild (4)ADDQ(Q,plchild) (5)ADDQ(Q,prchild)四、應(yīng)用題1．樹(shù)和二叉樹(shù)邏輯上都是樹(shù)形結(jié)構(gòu)，樹(shù)和二叉樹(shù)的區(qū)別有三：一是二叉樹(shù)的度至多為2，樹(shù)無(wú)此限制；二是二叉樹(shù)有左右子樹(shù)之分，即使在只有一個(gè)分枝的情況下， 也必須指出是左子樹(shù)還是右子樹(shù)，樹(shù)無(wú)此限制；三是二叉樹(shù)允許為空，樹(shù)一般不允許為空（個(gè)別書(shū)上允許為空）。5. 用一維數(shù)組存儲(chǔ)二叉樹(shù)時(shí)，總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn)。7．如果結(jié)點(diǎn)A有 3個(gè)兄弟，而且B是A的雙親，則B的度是______。( )4. 一棵一般樹(shù)的結(jié)點(diǎn)的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹(shù)的結(jié)點(diǎn)前序遍歷和后序遍歷是一致的。A．左子結(jié)點(diǎn) B．右子結(jié)點(diǎn)　 C．左子結(jié)點(diǎn)和右子結(jié)點(diǎn) D．左子結(jié)點(diǎn)，右子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)20．由3 個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹(shù)？（ D ）A．2 B．3 C．4 D．5 22. 一棵有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，按層次從上到下，同一層從左到右順序存儲(chǔ)在一維數(shù)組A[1..n]中，則二叉樹(shù)中第i個(gè)結(jié)點(diǎn)（i從1開(kāi)始用上述方法編號(hào)）的右孩子在數(shù)組A中的位置是（ D ）A．A[2i](2i=n) B．A[2i+1](2i+1=n) C．A[i2] D．條件不充分，無(wú)法確定二、判斷題（在各題后填寫(xiě)“√”或“”）1. 完全二叉樹(shù)一定存在度為1的結(jié)點(diǎn)。,一共有________個(gè)指針域,其中只有________個(gè)用來(lái)指向結(jié)點(diǎn)的左右孩子，其余的________個(gè)指針域?yàn)镹ULL。2. 對(duì)于有N個(gè)結(jié)點(diǎn)的二叉樹(shù)，其高度為log2n。 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。7．字符A，B，C，D出現(xiàn)的次數(shù)為9,1,5,3。 QueueIn(Q,p)。采用后序非遞歸算法，棧中存放二叉樹(shù)結(jié)點(diǎn)的指針，當(dāng)訪問(wèn)到某結(jié)點(diǎn)時(shí)，棧中所有元素均為該結(jié)點(diǎn)的祖先。 bt!=q) //結(jié)點(diǎn)入棧{s[++top].t=bt。 s[top].tag==1) top。push(amp。 else{bt=(BiTree)