1.
解：略
2.
解：略
3.已知一棵度為m的樹(shù)中有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)
，.....，nm個(gè)度為m的結(jié)點(diǎn)，問(wèn)樹(shù)中有多少個(gè)葉子結(jié)點(diǎn)？
解：
設(shè)葉子結(jié)點(diǎn)數(shù)為n0，則樹(shù)中結(jié)點(diǎn)數(shù)和總度數(shù)分別為
結(jié)點(diǎn)數(shù)=n0+n1+n2+...+nm
總度數(shù)=n1+2n2+...+m×nm
根據(jù)樹(shù)的性質(zhì)1可知，結(jié)點(diǎn)數(shù)等于總度數(shù)加1，所以得到
m
n0=1+Σ((i-1)×ni)
i=2
4.畫(huà)出由三個(gè)結(jié)點(diǎn)a,b,c組成的所有不同結(jié)構(gòu)的二叉樹(shù)，共有多少種不同的結(jié)構(gòu)？每一種結(jié)
構(gòu)又對(duì)應(yīng)多少種不同的值的排列次序？
解：
由三個(gè)結(jié)點(diǎn)a,b,c組成的所有不同結(jié)構(gòu)的二叉樹(shù)如下圖所示，共有5種不同的結(jié)構(gòu)，每一
種結(jié)構(gòu)對(duì)應(yīng)6種不同的值的排列次序。
a a a a a
/ \ / / \ \
b c b b b b
/ \ / \
c c c c
5.已知一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)被順序存儲(chǔ)于一維數(shù)組的A[1]～A[n]元素中，試編寫(xiě)一
個(gè)算法打印出編號(hào)為i的結(jié)點(diǎn)的雙親和所有孩子。
解：
void Request(int a[],int n,int i)
//從數(shù)組A中打印出編號(hào)為i的結(jié)點(diǎn)的雙親和孩子
{
if(i>n){
cerr<<"編號(hào)為"<<i<<"的結(jié)點(diǎn)不存在！"<<end1;
exit(1);
}
cout<<"current element:"<<A[i]<<end1;
int j=i/2; //下標(biāo)為j的結(jié)點(diǎn)是下標(biāo)為i結(jié)點(diǎn)的雙親
if(j>0)
cout<<"parent:"<<A[j]<<end1;
else
cout<<"樹(shù)根結(jié)點(diǎn)沒(méi)有雙親結(jié)點(diǎn)!"<<end1;
if(2*i<n){
cout<<"left child:"<<A[2*i]<?end1;
cout<<"right child:"<<A[2*i+1]<<end1;
}
else if(2*i==n){
cout<<"left child:"<<A[2*i]<<end1;
cout<<"no right child!"<<end1;
}
else
cout<<"no children!"<<end1;
}
6.已知一棵二叉樹(shù)如下圖所示，試分別畫(huà)出它的不帶雙親指針的鏈接存儲(chǔ)結(jié)構(gòu)的示意圖和
存儲(chǔ)于數(shù)組的鏈接存儲(chǔ)映像(假定按層次依次為各結(jié)點(diǎn)分配下標(biāo)位置)。
解：
25
/ \
16 37
/ / \
8 30 48
/ \ \
28 32 60
/ \ \
26 29 35
在數(shù)組中的二叉樹(shù)存儲(chǔ)映像如下所示。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...BTreeMaxSize
data 25 16 37 8 30 48 28 32 60 26 29 35
left 1 2 4 5 0 7 0 10 0 0 0 0 0
right 13 3 0 6 0 8 9 11 12 0 0 0 0 14 0
7.寫(xiě)出對(duì)圖5-3所示的二叉樹(shù)分另按前序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。
解：
前序遍歷為 25,16,8,37,30,28,26,29,32,35,48,60
中序遍歷為 8,16,25,26,28,29,30,32,35,37,48,60
后序遍歷為 8,16,26,29,28,35,32,30,60,48,37,25
8.寫(xiě)出對(duì)二叉樹(shù)進(jìn)行中序遍歷的非遞歸算法。
解：
void InorderN(BTreeNode*BT)
//對(duì)二叉樹(shù)進(jìn)行中序遍歷的非遞歸算法
{
BTreeNode* s[10];//定義用于存儲(chǔ)結(jié)點(diǎn)指針的棧
int top=-1;定義棧頂指針并賦初值使s棧為空
BTreeNode* p=BT;//定義指針p并使樹(shù)根指針為它的初值
while(top!=-1||p!=NULL)
{//當(dāng)棧非空或p指針?lè)强諘r(shí)執(zhí)行循環(huán)
while(p!=NULL){
top++;
s[top]=p;
p=p->left;
}
if(top!=-1){
p=s[top];
top--;
cout<<p->data<<'';
p=p->right;
}
}
}
9.編寫(xiě)一算法，求出一棵二叉樹(shù)中所有結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)，假定分別用變參C1和C2統(tǒng)計(jì)所
有結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(shù)，初值均為0。
解：
void Count(BTreeNode* BT,int& C1,int& C2)
//分別統(tǒng)計(jì)出二叉樹(shù)中所有結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(shù)
{
if(BT!=NULL){
C1++;//統(tǒng)計(jì)所有結(jié)點(diǎn)
if(BT->left==NULL&&BT->right==NULL)
C2++; //統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)
Count(BT->left,C1,C2);
Count(BT->right,C1,C2);
}
}
10.編寫(xiě)具有下列功能的每個(gè)函數(shù)：
把在內(nèi)存中生成的一棵二叉樹(shù)寫(xiě)入到一個(gè)磁盤(pán)文件中，該函數(shù)聲明為
void WriteFile(char* fname,BTreeNode*BT);
解：
根據(jù)從鍵盤(pán)上輸入的一棵二叉樹(shù)廣義表表示建立一棵二叉樹(shù)bt;
把bt二叉樹(shù)寫(xiě)入到磁盤(pán)文件"a:xxkl.dat"中；
把磁盤(pán)文件"a:xxkl.dat"中保存的二叉樹(shù)恢復(fù)到內(nèi)存中，并由bt指向樹(shù)根結(jié)點(diǎn)；
以廣義表的形式輸出以bt為樹(shù)根指針的二叉樹(shù)。
解：
寫(xiě)出先根遍歷得到的結(jié)點(diǎn)序列；
寫(xiě)出按層遍歷得到的結(jié)點(diǎn)序列；
畫(huà)出轉(zhuǎn)換后得到的二叉樹(shù)和二叉鏈表。
解：
void WriteFile(char* fname,BTreeNode*BT)
//把由BT指針?biāo)付鏄?shù)按照層次遍歷的次序存儲(chǔ)結(jié)點(diǎn)到文件fname中
{
ofstream ofs(fname,ios::binary);
//把由fname所指字符串作為文件名的文件定義為輸出文件流ofs，并按二進(jìn)制方
//式打開(kāi)
LinkQueue HQ;InitQueue(HQ);
//定義一個(gè)鏈接隊(duì)列并進(jìn)行初始化，該鏈接隊(duì)列中結(jié)點(diǎn)值的類(lèi)型應(yīng)為二叉樹(shù)結(jié)點(diǎn)
//的類(lèi)型
BTreeNode* p;
if(BT!==NULL)QInsert(HQ,BT){
//將樹(shù)根指針插入到隊(duì)列中
while(! QueueEmpty(HQ)){
p=QDelete(HQ);
//從隊(duì)列中刪除一個(gè)元素并賦給指針
ofs.write((char*)p,sizeof(*p));
//把p指針?biāo)附Y(jié)點(diǎn)寫(xiě)入到文件中
if(p->left!=NULL)QInsert(HQ,p->left);
//若p結(jié)點(diǎn)存在左孩子，則左孩子指計(jì)入隊(duì)
if(p->right!=NULL)QInsert(HQ,p->right);
//若p結(jié)點(diǎn)存在右孩子，則右孩子指計(jì)入隊(duì)
}
ofs.closs();//關(guān)閉文件流對(duì)象所對(duì)應(yīng)的文件
}
2.把存儲(chǔ)到磁盤(pán)文件中的一棵二叉樹(shù)恢復(fù)到內(nèi)存存中，該函數(shù)聲明為
void WriteFile(char* fname,BTreeNode*&BT);
解：
void WriteFile(char* fname,BTreeNode*&BT)
//把fname文件中按層掃描存儲(chǔ)的二叉樹(shù)恢復(fù)到內(nèi)存中，并由引用指針BT指向樹(shù)根結(jié)點(diǎn)
{
ifstream ifs(fname,ios::in | ios::nocreate | ios::binary);
//把fname文件定義為輸入文件流ifs，并按二進(jìn)制方式打開(kāi)
if(! ifs){cout<<"File not open!"<<end1;exit(1);}
LinkQueue HQ; InitQueue(HQ);
//定義一個(gè)鏈接隊(duì)列并進(jìn)行初始化
BTreeNode *p1,*p2;
int b=sizeof(*p1);
//把二叉樹(shù)結(jié)點(diǎn)的大小賦給b，作為讀取文件的基本單位
ifs.seekg(0,ios::end);
//把文件指針移到結(jié)束位置
int n=ifs.tellg()/b;
//求出文件中所存二叉樹(shù)的結(jié)點(diǎn)數(shù)并賦給n
ifs.seekg(0);
//將文件指針移到文件開(kāi)始位置，以便從頭開(kāi)始讀取每個(gè)結(jié)點(diǎn)
if(n==0){ifs.close();BT=NULL;return;}
//如果文件為空，則把BT置空后返回，用文件中的第一個(gè)結(jié)點(diǎn)構(gòu)成樹(shù)根結(jié)點(diǎn)并將
//該結(jié)點(diǎn)指針插入隊(duì)列中
p1=new BTreeNode;
ifs.read((char*)p1,b);
BT=p1;
QInsert(HQ.p1);
n--;
//依次用文件中的每個(gè)結(jié)點(diǎn)構(gòu)成新結(jié)點(diǎn)并把它插入到雙親結(jié)點(diǎn)的左孩子或右孩子位置
while(n)
{ //當(dāng)讀完文件中的結(jié)點(diǎn)后循環(huán)結(jié)束
p2=QDelete(HQ);//從隊(duì)列中刪除隊(duì)首元素并賦給p2
if(p2->left!=0)
{//需要給p2結(jié)點(diǎn)添加左孩子，并使左孩子指針進(jìn)隊(duì)
p1=new BTreeNode;
ifs.read((char*)p1,b);
p2->left=p1;
Qinsert(HQ,p1);
n--;
}
if(p2->right!=0)
{ //需要給p2結(jié)點(diǎn)添加右孩子，并使右孩子指針進(jìn)隊(duì)
p1=new BTreeNode;
ifs.read((char*)p1,b);
p2->right=p1;
QInsert(HQ,p1)
n--;
}
}
ifs.close();//關(guān)閉ifs對(duì)應(yīng)的磁盤(pán)文件
}
11.編寫(xiě)一個(gè)完整的程序?qū)崿F(xiàn)下列功能：
#include<iostream.h>
#include<fstream.h>
#include<strstrea.h>
#include<stdlib>
struct BTreeNode {//定義二叉樹(shù)結(jié)點(diǎn)類(lèi)型
char data; //定義結(jié)點(diǎn)值的類(lèi)型為整型
BTreeNode *left;
BTreeNode *right;
};
typedef BTreeNode* ElemType;//定義鏈接隊(duì)列中結(jié)點(diǎn)值的類(lèi)型為二叉樹(shù)結(jié)點(diǎn)的指針類(lèi)型
struct LNode{ElemType data;LNode* next;};
//定義鏈接隊(duì)列中結(jié)點(diǎn)的類(lèi)型
struct LinkQueue{LNode* front;LNode*rear;};
//定義一個(gè)鏈接隊(duì)列的存儲(chǔ)類(lèi)型
#include"linkqueue.h"http://包含對(duì)鏈接隊(duì)列的各種運(yùn)算
#include"btree.h"http://包含二叉樹(shù)的各種運(yùn)算
void WriteFile(char* fname,BTreeNode* BT)
//把由BT指針?biāo)付鏄?shù)按照層次遍歷的次序存儲(chǔ)結(jié)點(diǎn)到文件fname中
{
//函數(shù)體略
}
void ReadFile(char* fname,BTreeNode*&BT)
//把fname文件中按層掃描存儲(chǔ)的二叉樹(shù)恢復(fù)到內(nèi)存中，并由引用指針BT
//指向樹(shù)根結(jié)點(diǎn)
{
//函數(shù)體略
}
void main()
{
BtreeNode *bt;
InitBTree(bt);
while(1)
{
cout<<"功能菜單:"<<end1;
cout<<'\t'<<"1.建立二叉樹(shù)"<<end1;
cout<<'\t'<<"2.二叉樹(shù)存盤(pán)"<<end1;
cout<<'\t'<<"3.由文件恢復(fù)二叉樹(shù)"<<end1;
cout<<'\t'<<"4.以廣義表形式輸出二叉樹(shù)"<<end1;
cout<<'\t'<<"5.結(jié)束程序運(yùn)行"<<end1;
cout<<end1;
int m;
cout<<"輸入你的選擇(1-5):";
do cin>>m;while(m<1||m>5);
switch(m){
case 1:
char a[50];
cout<<"輸入以'@'字符作為結(jié)束符的二叉樹(shù)廣義表表示:"<<end1;
cin>>ws;//跳過(guò)鍵盤(pán)輸入緩沖區(qū)中的空白字符
cin.getline(a,50);
createBTree(bt,a);
break;
case 2:
WriteFile("a:xxkl.dat",bt);
break;
case 3:
ReadFile("a:xxkl.dat",bt);
break;
case 4:
PrintBTree(bt);cout<<end1;
break;
default;
break;
}
if(m==5)break;
}
}
12.對(duì)于圖5-16所示的樹(shù)：
略
13.假定一棵樹(shù)采用標(biāo)準(zhǔn)形式存儲(chǔ)，試寫(xiě)出廣義表形式輸出樹(shù)的算法。
解：
void printGTree(GTreeNode* GT)
//以廣義表形式輸出按標(biāo)準(zhǔn)方式存儲(chǔ)的三叉樹(shù)
{
if(GT!=NULL){//若樹(shù)不為空則進(jìn)行如下處理
cout<<GT->data<<'';//輸出根結(jié)點(diǎn)的值
if(GT->t[0]||GT->t[1]||GT->t[2]){
cout<<'(';
printGTree(GT->t[0]);//輸出第一棵子樹(shù)
cout<<',';
printGTree(GT->t[1]);//輸出第二棵子樹(shù)
cout<<',';
printGTree(GT->t[2]);//輸出第三棵子樹(shù)
cout<<')';
}
}
}
14.假定采用標(biāo)準(zhǔn)形式存儲(chǔ)，試寫(xiě)出求其深度的算法。
解：
int GTreeDepth(GTreeNode* GT)
//求一棵普通樹(shù)的深度
{
if(GT==NULL)//空樹(shù)的深度為0
return 0;
else{
int max=0;//用來(lái)保存子樹(shù)中的最大深度
for(int i=0;i<3;i++){
int d=GTreeDepth(GT->t[i]);
//計(jì)算出一棵子樹(shù)的深度并賦給變量d
if(d>max)max=d;
}
return max+1; //返回樹(shù)的深度，它等于子樹(shù)的最大深度加1
}
}
10.在一份電文中共使用五種字符：a、b、c、d、e ，它們的出現(xiàn)頻率依次為4、7、5、2、9
，試畫(huà)出對(duì)應(yīng)的編碼哈夫曼樹(shù)(請(qǐng)按照左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)的次序構(gòu)
造)，求出每個(gè)字符的哈夫曼編碼，并求出傳送電文的長(zhǎng)度。
解：
五種字符的哈夫曼編碼依次為001,10,00,010,11。傳送電文的總長(zhǎng)度為60。
