【正文】 }。 }(3) 找結點的先序后繼結點BiTNode *PreSucc (BiTNode *p)/*在先序線索二叉樹中查找p的先序后繼結點，并用succ指針返回結果*/{ if (pLtag= =0) succ = pLChild。 pre = q。BTLC(Tlchild,amp。 while(!QueueEmpty(Q)){p=QueueOut(Q)。void DeleteXTree(BiTree bt) //刪除以bt為根的子樹 {DeleteXTree(btlchild)。} //處理第一個葉子結點 else{prerchild=bt。設置前驅(qū)結點指針pre，初始為空。} //退棧，訪問，轉右子樹} }6．BiTree Copy(BiTree t)//復制二叉樹t{BiTree bt。 p=pRChild。 p=root。 enqueue (q, T)。}｝while(top!=0 amp。 top1=top。 bt!=p amp。int tag。判斷時易犯的錯誤是證明其左子樹和右子數(shù)都是完全二叉樹，由此推出整棵二叉樹必是完全二叉樹的錯誤結論。 //前邊已有結點為空，本結點不空 else tag=1。 // Q是隊列，元素是二叉樹結點指針，容量足夠大if(p==null) return (1)。 //本題假定結點數(shù)據(jù)域為整型if(x==0) bt=null。HGDACJIBFEMPONKOL5.6．（l）圖略；（2）中根序列：B C D A F E H J I G?！倘?、填空題1．plchild==null amp。9. 給定一棵樹，可以找到唯一的一棵二叉樹與之對應。（3）畫出二叉樹的后序線索樹。10．若一個二叉樹的葉子結點是某子樹的中序遍歷序列中的最后一個結點，則它必是該子樹的____ __序列中的最后一個結點。2．深度為k的完全二叉樹至少有___ ____個結點，至多有___ ____個結點。 ( )7．完全二叉樹中，若一個結點沒有左孩子，則它必是樹葉。A．CBEFDA B． FEDCBA C． CBEDFA D．不定 13．已知某二叉樹的后序遍歷序列是dabec, 中序遍歷序列是debac , 它的前序遍歷是（ D ）。A．指向最左孩子 B．指向最右孩子 C．空 D．非空12．已知一棵二叉樹的前序遍歷結果為ABCDEF,中序遍歷結果為CBAEDF,則后序遍歷的結果為（ A ）。( )6．中序遍歷一棵二叉排序樹的結點就可得到排好序的結點序列。( )三、填空題1．在二叉樹中，指針p所指結點為葉子結點的條件是___ ___。9．一個無序序列可以通過構造一棵___ ___樹而變成一個有序序列，構造樹的過程即為對無序序列進行排序的過程。（2）寫出按前序、中序、后序遍歷該二叉樹所得到的結點序列?！?. 二叉樹只能用二叉鏈表表示?！?6．哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結點離根較近。2．【解答】具有3個結點的樹 具有3個結點的二叉樹 3．解答：先根序列：A B C D E F G H I J。(4) 根據(jù)以上分析，結點n有右兄弟的條件是，它不是雙親的從右數(shù)的第一子女，即 (n1)%k!=0，其右兄弟編號是n+1。x)。 BiTree p=bt, Q[]。 //左子女入隊 else {if (plchild) return 0。 } //JudgeComplete[算法討論]完全二叉樹證明還有其它方法。typedef struct {BiTree t。amp。i++) s1[i]=s[i]。j)if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”)；return (pp)。void layorder (bitreptr T) {initqueue (q) /*隊列初始化*/ if(T!=NULL) {printf(“%f”, Tdata)。S)。p)。 p=prchild。 }//結束Copy7.[題目分析]葉子結點只有在遍歷中才能知道，這里使用中序遞歸遍歷。 pre=bt。本題要求刪除樹中每一個元素值為 x的結點的子樹，因此要遍歷完整棵二叉樹。 QueueIn(Q,bt)。// 右子女入隊列 }//while }//if(bt) }//search9．int BTLC(BiTree T,int *c)//對二叉樹T的結點計數(shù){if(T) {*c++。 q=qRChild)。 } return (s