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