數(shù)據(jù)結(jié)構(gòu)-第四章樹習(xí)題課

第四章樹與二叉樹習(xí)題課1作業(yè)：p1254-1(省略)4-3

有m個葉子的二叉樹最少有多少個結(jié)點?4-4現(xiàn)有按后序遍歷二叉樹的結(jié)果為C，B，A，有幾種不同的二叉樹可得到這一結(jié)果？24-10設(shè)計一個算法，將一個用二叉鏈表存儲的二叉樹的每個結(jié)點的左、右子女位置交換。voidChange(BinTreeNode*t){if(!t)return0;

if(t->leftChild||t->rightChild){p=t->leftChild;t->leftChild=t->rightChild;t->rightChild=p;}}34-14．將圖4.25中的樹轉(zhuǎn)換成二叉樹。然后對樹和轉(zhuǎn)換成的二叉樹分別進(jìn)行適當(dāng)?shù)谋闅v，并加以對比。4一、填空題

（1）對于一棵具有n個結(jié)點的樹,該樹中所有結(jié)點度數(shù)之和為

。（2）k叉樹上的i層最大有

個結(jié)點。（3）高度為h的k叉樹最多有

個結(jié)點。

n個結(jié)點的k叉樹的最小高度為

。

假定一棵三叉樹的結(jié)點個數(shù)為50，則它的最小高度為最大高度為

。一棵高度為5的滿二叉樹中的結(jié)點數(shù)為

。

一棵高度為3的滿四叉樹中的結(jié)點數(shù)為

。

n-150ki-1

(43-1)/325-15

（4）在一棵二叉樹中，若度為2的結(jié)點數(shù)有5個，度為1的結(jié)點數(shù)有6個，那么度為0的結(jié)點數(shù)有

個？（5）在一棵三叉樹中，若度為3的結(jié)點數(shù)有2個，度為2的結(jié)點數(shù)有1個，度為1的結(jié)點數(shù)有2個，那么度為0的結(jié)點數(shù)有

個？

一、填空題6n=n0+n1+n2=n0+5+6=e+1=2*5+1*6+1=>n0=66(5)

n=n0+n1+n2+n3=n0+2+1+2=e+1=3*2+2*1+1*2+1=>n0=66（6）若對一棵二叉樹從0開始進(jìn)行結(jié)點編號，并按此編號把它順序存儲到一維數(shù)組a中，則a[i]元素的左子女結(jié)點編號為

，右子女結(jié)點編號為

，雙親結(jié)點編號為

。（7）對于一棵具有n個結(jié)點的二叉樹的二叉鏈表中，指針總數(shù)為為

，其中

個指針指向子女結(jié)點，

指針空閑。2i+12i+22nn-1n+17（8）在Huffman樹中，若編碼長度只允許小于等于4，則除了已對兩個字符編碼為0和10外，還可最大對

個字符編碼。（9）設(shè)高度為h（h≥1）的二叉樹中，若設(shè)二叉樹只有度為0和度為2的結(jié)點，則二叉樹中所含結(jié)點個數(shù)至少

個。（10）設(shè)森林F中有4棵樹，第1，2，3，4棵樹的結(jié)點個數(shù)分別為n1,n2,n3,n4，當(dāng)把該森林F轉(zhuǎn)換成一棵二叉樹后，其根結(jié)點的左子樹有

個結(jié)點，右子樹有

個結(jié)點。2h-14n1n2+n3+n48二、判斷題(11)二叉樹是樹的特殊情形。(12)若有一個結(jié)點是二叉樹中某個子樹的中序遍歷結(jié)果序列的最后一個結(jié)點，則它一定是該子樹的前序遍歷結(jié)果序列的最后一個結(jié)點。(13)若有一個葉結(jié)點是二叉樹中某個子樹的中序遍歷結(jié)果序列的最后一個結(jié)點，則它一定是該子樹的前序遍歷結(jié)果序列的最后一個結(jié)點。(14)若有一個葉結(jié)點是二叉樹中某個子樹的前序遍歷結(jié)果序列的最后一個結(jié)點，則它一定是該子樹的中序遍歷結(jié)果序列的最后一個結(jié)點?！痢痢痢?二、對二叉樹遞歸算法的理解voidPreorder(BinTree*r){//前序遍歷的遞歸算法

if(r){

cout<<r->data;②

Preorder(r->leftChild);①

Preorder(r->rightChild);}}voidPreorder(BinTree*r){

//消去前序遍歷第二個遞歸調(diào)用

while(r){

cout<<r->data;

Preorder(r->leftChild);r=r->rightChild;}}ABCDE10非遞歸的前序遍歷算法：voidPreOrderTraverse(BinaryTreeNode*r){Stacks;s.InitStack()；p=r;

while(p||!s.IsEmpty()){while(p){

cout<<p->data;s.Push(p);p=p->leftChild;}

if(!s.IsEmpty()){

p=s.Pop()；p=p->rightChild；

}//if}//while}//lnOrderTraverse

112、如一棵樹有n1個度為1的結(jié)點，有n2個度為2的結(jié)點，……,nm個度為m的結(jié)點，試問有多少個度為0的結(jié)點？解：n=n0+n1+n2+…+nm

n-1=n1+2*n2+…+mnm

化簡：n=1+n2+2n3+…+(m-1)nm

=1+1、3個結(jié)點的樹和二叉樹個共有多少不同形態(tài)？樹有2種，二叉樹有5種。12

(1)空二叉樹或左子樹為空的二叉樹。

(2)空二叉樹或右子樹為空的二叉樹。

(3)空二叉樹或只有根結(jié)點的二叉樹。3、試分別找出滿足下列條件的所有二叉樹：（1）二叉樹的前序遍歷與中序遍歷相同；（2）二叉樹的中序遍歷與后序遍歷相同；（3）二叉樹的前序遍歷與后序遍歷相同；13四、設(shè)二叉樹以二叉鏈表表示，試編寫有關(guān)二叉樹的遞歸算法。統(tǒng)計二叉樹中葉結(jié)點的個數(shù)。intDegrees0(BinTreeNode*t){if(!t)return0;

if(!t->leftChild&&!t->rightChild)return1;returnDegrees0(t->leftChild)+Degrees0(t->rightChild);}或voidDegrees0(BinTreeNode*t，&count){if(t){

if(!t->leftChild&&!t->rightChild)count++;Degrees0(t->leftChild,count);Degrees0(t->rightChild,count);}}14四、設(shè)二叉樹以二叉鏈表表示，試編寫有關(guān)二叉樹的遞歸算法。2.統(tǒng)計二叉樹中度為1的結(jié)點個數(shù)。intDegrees1(BinTreeNode*t){if(!t)return0;

if((t->leftChild&&!t->rightChild)||(!t->leftChild&&t->rightChild))return1;returnDegrees1(t->leftChild)+Degrees1(t->rightChild);}或intDegrees1(BinTreeNode*t){if(!t)return0;

if((t->leftChild&&!t->rightChild)||(!t->leftChild&&t->rightChild))return1+Degrees1(t->leftChild)+Degrees1(t->rightChild);}15intDegrees2(BinTreeNode*t){if(!t)return0;

if(t->leftChild&&t->rightChild)return1+Degrees2(t->leftChild)+Degrees2(t->rightChild);}3.統(tǒng)計二叉樹中度為2的結(jié)點個數(shù)。16int

high(BinaryTreeNode*t){if(!t)return0;

lh=high(t->leftChild);

rh=high(t->rightChild);