樹和二叉樹習(xí)題答案

1、第六章 練習(xí)1、試分別畫出具有3個(gè)結(jié)點(diǎn)的樹和3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。態(tài)。解：（1）3個(gè)結(jié)點(diǎn)的樹：（2）3個(gè)結(jié)點(diǎn)的二叉樹：2、已知一棵度為m的樹中有個(gè)度為1的結(jié)點(diǎn)，個(gè)度為2 結(jié)點(diǎn)，個(gè)度為m的結(jié)點(diǎn)，問該樹中有多少個(gè)葉子結(jié)點(diǎn)？解：由樹的特征可知，除頂點(diǎn)外每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一條邊，總邊數(shù)等于各頂點(diǎn)度數(shù)之和，所以有：所以： 3、對(duì)第1題所得的各種形態(tài)的二叉樹，分別寫出前序、中序和后序遍歷的序列。解：(1) 前：ABC 中：BAC 后：BCA(2) 前：ABC 中：CBA 后：CBA(3) 前：ABC 中：BCA 后：CBA(4) 前：ABC 中：ABC 后：CBA(5) 前：ABC 中：ACB 后：

2、CBA 4、試以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，編寫算法將二叉樹中所有結(jié)點(diǎn)的左、右子樹相互交換。void Bitree_Revolute(Bitree T)/交換所有結(jié)點(diǎn)的左右子樹 T->lchild<->T->rchild; /交換左右子樹 if(T->lchild) Bitree_Revolute(T->lchild); if(T->rchild) Bitree_Revolute(T->rchild); /左右子樹再分別交換各自的左右子樹/Bitree_Revolute 5、畫出和下面樹對(duì)應(yīng)的二叉樹： 6、畫出和下面二叉樹對(duì)應(yīng)的森林： 7、寫出判斷給定

3、的二叉樹是否是完全二叉樹的算法。int IsFull_Bitree(Bitree T)/判斷二叉樹是否完全二叉樹,是則返回1,否則返回0 InitQueue(Q); flag=0; EnQueue(Q,T); /建立工作隊(duì)列 while(!QueueEmpty(Q) DeQueue(Q,p); if(!p) flag=1; else if(flag) return 0; else EnQueue(Q,p->lchild); EnQueue(Q,p->rchild); /不管孩子是否為空,都入隊(duì)列 /while return 1;/IsFull_Bitree分析:該問題可以通過層序遍

4、歷的方法來解決.不管當(dāng)前結(jié)點(diǎn)是否有左右孩子,都入隊(duì)列.這樣當(dāng)樹為完全二叉樹時(shí),遍歷時(shí)得到是一個(gè)連續(xù)的不包含空指針的序列.反之,則序列中會(huì)含有空指針. 8、根據(jù)棧的存儲(chǔ)結(jié)構(gòu)寫出二叉樹的非遞歸形式的先序遍歷算法。解：void PreOrder_Nonrecursive(Bitree T)/先序遍歷二叉樹的非遞歸算法 InitStack(S); Push(S,T); /根指針進(jìn)棧 while(!StackEmpty(S) while(Gettop(S,p)&&p) visit(p->data); push(S,p->lchild); /向左走到盡頭 pop(S,p); if(!StackEmpty(S) pop(S,p); push(S,p->rchild); /向右一步 /while/PreOrder_Nonrecursive 9、假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。 所以這8個(gè)字