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

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

有m個(gè)葉子的二叉樹(shù)最少有多少個(gè)結(jié)點(diǎn)?4-4現(xiàn)有按后序遍歷二叉樹(shù)的結(jié)果為C，B，A，有幾種不同的二叉樹(shù)可得到這一結(jié)果？24-10設(shè)計(jì)一個(gè)算法，將一個(gè)用二叉鏈表存儲(chǔ)的二叉樹(shù)的每個(gè)結(jié)點(diǎn)的左、右子女位置交換。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中的樹(shù)轉(zhuǎn)換成二叉樹(shù)。然后對(duì)樹(shù)和轉(zhuǎn)換成的二叉樹(shù)分別進(jìn)行適當(dāng)?shù)谋闅v，并加以對(duì)比。4一、填空題

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

。（2）k叉樹(shù)上的i層最大有

個(gè)結(jié)點(diǎn)。（3）高度為h的k叉樹(shù)最多有

個(gè)結(jié)點(diǎn)。

n個(gè)結(jié)點(diǎn)的k叉樹(shù)的最小高度為

。

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

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

。

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

。

n-150ki-1

(43-1)/325-15

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

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

個(gè)？

一、填空題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）若對(duì)一棵二叉樹(shù)從0開(kāi)始進(jìn)行結(jié)點(diǎn)編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組a中，則a[i]元素的左子女結(jié)點(diǎn)編號(hào)為

，右子女結(jié)點(diǎn)編號(hào)為

，雙親結(jié)點(diǎn)編號(hào)為

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

，其中

個(gè)指針指向子女結(jié)點(diǎn)，

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

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

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

個(gè)結(jié)點(diǎn)，右子樹(shù)有

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

if(r){

cout<<r->data;②

Preorder(r->leftChild);①

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

//消去前序遍歷第二個(gè)遞歸調(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、如一棵樹(shù)有n1個(gè)度為1的結(jié)點(diǎn)，有n2個(gè)度為2的結(jié)點(diǎn)，……,nm個(gè)度為m的結(jié)點(diǎn)，試問(wèn)有多少個(gè)度為0的結(jié)點(diǎn)？解：n=n0+n1+n2+…+nm

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

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

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

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

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

(3)空二叉樹(shù)或只有根結(jié)點(diǎn)的二叉樹(shù)。3、試分別找出滿足下列條件的所有二叉樹(shù)：（1）二叉樹(shù)的前序遍歷與中序遍歷相同；（2）二叉樹(shù)的中序遍歷與后序遍歷相同；（3）二叉樹(shù)的前序遍歷與后序遍歷相同；13四、設(shè)二叉樹(shù)以二叉鏈表表示，試編寫(xiě)有關(guān)二叉樹(shù)的遞歸算法。統(tǒng)計(jì)二叉樹(shù)中葉結(jié)點(diǎn)的個(gè)數(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è)二叉樹(shù)以二叉鏈表表示，試編寫(xiě)有關(guān)二叉樹(shù)的遞歸算法。2.統(tǒng)計(jì)二叉樹(shù)中度為1的結(jié)點(diǎn)個(gè)數(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)計(jì)二叉樹(shù)中度為2的結(jié)點(diǎn)個(gè)數(shù)。16int

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

lh=high(t->leftChild);

rh=high(t->rightChild);