08數(shù)據(jù)結(jié)構(gòu)第6章習(xí)題

數(shù)據(jù)結(jié)構(gòu)計算機科學(xué)與技術(shù)學(xué)院Page22023/11/13基礎(chǔ)知識題已知一棵樹邊的集合為{<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,

<A,B>,<G,J>,<G,K>,<C,G>,<C,F>,<H,L>,<C,H>,<A,C>}，請畫出這棵樹，并回答下列問題：哪個是根結(jié)點?哪些是葉子結(jié)點?哪個是結(jié)點G的雙親?哪些是結(jié)點G的祖先?哪些是結(jié)點G的孩子?哪些是結(jié)點E的子孫?哪些是結(jié)點E的兄弟?哪些是結(jié)點F的兄弟?結(jié)點B和N的層次號分別是什么?樹的深度是多少?以結(jié)點C為根的子樹的深度是多少?Page32023/11/13試分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。已知在一棵含有n個結(jié)點的樹中，只有度為k的分支結(jié)點和度為0的葉子結(jié)點。試求該樹含有的葉子結(jié)點的數(shù)目。試分別推導(dǎo)含n個結(jié)點和含n0

個葉子結(jié)點的完全三叉樹的深度H。Page42023/11/13假設(shè)n和m為二叉樹中兩結(jié)點，用“1”、“0”或“ф”(分別表示肯定、恰恰相反或者不一定）填寫下表：注：如果離a和b最近的共同祖先p存在；且a在p的

左子樹中，b在p的右子樹中，則稱a在b的左方

(即b在a的右方)。Page52023/11/13找出所有滿足下列條件的二叉樹:它們在先序遍歷和中序遍歷時，得到的結(jié)點訪問序列相同;它們在后序遍歷和中序遍歷時，得到的結(jié)點訪問序列相同;它們在先序遍歷和后序遍歷時，得到的結(jié)點訪問序列相同;將下列二叉鏈表改為先序線索鏈表。Page62023/11/13分別畫出和下列樹對應(yīng)的各個二叉樹，給出的各樹的先根序列、后根序列。

Page72023/11/13將下列森林轉(zhuǎn)換為相應(yīng)的二叉樹Page82023/11/13假設(shè)用于通訊的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。試為這8個字母設(shè)計哈夫曼編碼。使用0～7的二進制表示形式是令一種編碼方案。對于上述實例，比較兩種方案的優(yōu)缺點。假設(shè)一棵二叉樹的前序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。請畫出該樹。假設(shè)一棵二叉樹的中序序列為DCBGEAHFIJK和后序序列為DCEGBFHKJIA。請畫出該樹。Page92023/11/13編程題本章練習(xí)題中的二叉樹和樹的二叉鏈表的類型定義如下：structBiTNode{//二叉樹結(jié)點

ElemTypedata;

BiTLinklchild,rchild;

};typedefBiTLinkBiTree;//二叉樹鏈表//樹的二叉鏈表(孩子-兄弟）存儲表示//typedefstructCSNode{

ElemTypedata;

structCSNode*firstchild,*nextsibling;

}CSNode,*CSTree;Page102023/11/13編寫遞歸算法，在二叉樹中求位于先序序列中第k個位置的結(jié)點的值。

boolpre_Order_K(BiTreebt,intk,ElemType&x)

//已知bt為指向二叉鏈表(二叉樹)的根指針，若k>0且不大于

//二叉樹中的結(jié)點數(shù)，則以x帶回該二叉樹的先序序列中第k個

//數(shù)據(jù)元素并返回true，否則返回false編寫遞歸算法，將二叉樹中所有結(jié)點的左、右子樹相互交換。

voidExchange(BiTree&bt)

//已知bt為指向二叉鏈表(二叉樹)的根指針，

//本函數(shù)實現(xiàn)該二叉樹上所有結(jié)點的左、右子樹互換Page112023/11/13編寫遞歸算法：對于二叉樹中每一個元素值為x的結(jié)點，刪去以它為根的子樹，并釋放相應(yīng)的空間。

voidReleaseX(BiTree&bt,ElemTypex)

//已知bt為指向二叉鏈表(二叉樹)的根指針，若二叉樹上存在其

//數(shù)據(jù)元素和x相同的結(jié)點，則均刪除之。編寫按層次順序(同一層自左至右)遍歷二叉樹的算法。

voidLevelOrder(BiTreebt,charss[],int&n)