1.
解：略
2.
解：略
3.已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点
，.....，nm个度为m的结点，问树中有多少个叶子结点？
解：
设叶子结点数为n0，则树中结点数和总度数分别为
结点数=n0+n1+n2+...+nm
总度数=n1+2n2+...+m×nm
根据树的性质1可知，结点数等于总度数加1，所以得到
m
n0=1+Σ((i-1)×ni)
i=2
4.画出由三个结点a,b,c组成的所有不同结构的二叉树，共有多少种不同的结构？每一种结
构又对应多少种不同的值的排列次序？
解：
由三个结点a,b,c组成的所有不同结构的二叉树如下图所示，共有5种不同的结构，每一
种结构对应6种不同的值的排列次序。
a a a a a
/ \ / / \ \
b c b b b b
/ \ / \
c c c c
5.已知一棵具有n个结点的完全二叉树被顺序存储于一维数组的A[1]～A[n]元素中，试编写一
个算法打印出编号为i的结点的双亲和所有孩子。
解：
void Request(int a[],int n,int i)
//从数组A中打印出编号为i的结点的双亲和孩子
{
if(i>n){
cerr<<"编号为"<<i<<"的结点不存在！"<<end1;
exit(1);
}
cout<<"current element:"<<A[i]<<end1;
int j=i/2; //下标为j的结点是下标为i结点的双亲
if(j>0)
cout<<"parent:"<<A[j]<<end1;
else
cout<<"树根结点没有双亲结点!"<<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.已知一棵二叉树如下图所示，试分别画出它的不带双亲指针的链接存储结构的示意图和
存储于数组的链接存储映像(假定按层次依次为各结点分配下标位置)。
解：
25
/ \
16 37
/ / \
8 30 48
/ \ \
28 32 60
/ \ \
26 29 35
在数组中的二叉树存储映像如下所示。
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所示的二叉树分另按前序、中序、后序遍历时得到的结点序列。
解：
前序遍历为 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];//定义用于存储结点指针的栈
int top=-1;定义栈顶指针并赋初值使s栈为空
BTreeNode* p=BT;//定义指针p并使树根指针为它的初值
while(top!=-1||p!=NULL)
{//当栈非空或p指针非空时执行循环
while(p!=NULL){
top++;
s[top]=p;
p=p->left;
}
if(top!=-1){
p=s[top];
top--;
cout<<p->data<<'';
p=p->right;
}
}
}
9.编写一算法，求出一棵二叉树中所有结点数和叶子结点，假定分别用变参C1和C2统计所
有结点数和叶子结点数，初值均为0。
解：
void Count(BTreeNode* BT,int& C1,int& C2)
//分别统计出二叉树中所有结点数和叶子结点数
{
if(BT!=NULL){
C1++;//统计所有结点
if(BT->left==NULL&&BT->right==NULL)
C2++; //统计叶子结点数
Count(BT->left,C1,C2);
Count(BT->right,C1,C2);
}
}
10.编写具有下列功能的每个函数：
把在内存中生成的一棵二叉树写入到一个磁盘文件中，该函数声明为
void WriteFile(char* fname,BTreeNode*BT);
解：
根据从键盘上输入的一棵二叉树广义表表示建立一棵二叉树bt;
把bt二叉树写入到磁盘文件"a:xxkl.dat"中；
把磁盘文件"a:xxkl.dat"中保存的二叉树恢复到内存中，并由bt指向树根结点；
以广义表的形式输出以bt为树根指针的二叉树。
解：
写出先根遍历得到的结点序列；
写出按层遍历得到的结点序列；
画出转换后得到的二叉树和二叉链表。
解：
void WriteFile(char* fname,BTreeNode*BT)
//把由BT指针所指二叉树按照层次遍历的次序存储结点到文件fname中
{
ofstream ofs(fname,ios::binary);
//把由fname所指字符串作为文件名的文件定义为输出文件流ofs，并按二进制方
//式打开
LinkQueue HQ;InitQueue(HQ);
//定义一个链接队列并进行初始化，该链接队列中结点值的类型应为二叉树结点
//的类型
BTreeNode* p;
if(BT!==NULL)QInsert(HQ,BT){
//将树根指针插入到队列中
while(! QueueEmpty(HQ)){
p=QDelete(HQ);
//从队列中删除一个元素并赋给指针
ofs.write((char*)p,sizeof(*p));
//把p指针所指结点写入到文件中
if(p->left!=NULL)QInsert(HQ,p->left);
//若p结点存在左孩子，则左孩子指计入队
if(p->right!=NULL)QInsert(HQ,p->right);
//若p结点存在右孩子，则右孩子指计入队
}
ofs.closs();//关闭文件流对象所对应的文件
}
2.把存储到磁盘文件中的一棵二叉树恢复到内存存中，该函数声明为
void WriteFile(char* fname,BTreeNode*&BT);
解：
void WriteFile(char* fname,BTreeNode*&BT)
//把fname文件中按层扫描存储的二叉树恢复到内存中，并由引用指针BT指向树根结点
{
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);
//把二叉树结点的大小赋给b，作为读取文件的基本单位
ifs.seekg(0,ios::end);
//把文件指针移到结束位置
int n=ifs.tellg()/b;
//求出文件中所存二叉树的结点数并赋给n
ifs.seekg(0);
//将文件指针移到文件开始位置，以便从头开始读取每个结点
if(n==0){ifs.close();BT=NULL;return;}
//如果文件为空，则把BT置空后返回，用文件中的第一个结点构成树根结点并将
//该结点指针插入队列中
p1=new BTreeNode;
ifs.read((char*)p1,b);
BT=p1;
QInsert(HQ.p1);
n--;
//依次用文件中的每个结点构成新结点并把它插入到双亲结点的左孩子或右孩子位置
while(n)
{ //当读完文件中的结点后循环结束
p2=QDelete(HQ);//从队列中删除队首元素并赋给p2
if(p2->left!=0)
{//需要给p2结点添加左孩子，并使左孩子指针进队
p1=new BTreeNode;
ifs.read((char*)p1,b);
p2->left=p1;
Qinsert(HQ,p1);
n--;
}
if(p2->right!=0)
{ //需要给p2结点添加右孩子，并使右孩子指针进队
p1=new BTreeNode;
ifs.read((char*)p1,b);
p2->right=p1;
QInsert(HQ,p1)
n--;
}
}
ifs.close();//关闭ifs对应的磁盘文件
}
11.编写一个完整的程序实现下列功能：
#include<iostream.h>
#include<fstream.h>
#include<strstrea.h>
#include<stdlib>
struct BTreeNode {//定义二叉树结点类型
char data; //定义结点值的类型为整型
BTreeNode *left;
BTreeNode *right;
};
typedef BTreeNode* ElemType;//定义链接队列中结点值的类型为二叉树结点的指针类型
struct LNode{ElemType data;LNode* next;};
//定义链接队列中结点的类型
struct LinkQueue{LNode* front;LNode*rear;};
//定义一个链接队列的存储类型
#include"linkqueue.h"//包含对链接队列的各种运算
#include"btree.h"//包含二叉树的各种运算
void WriteFile(char* fname,BTreeNode* BT)
//把由BT指针所指二叉树按照层次遍历的次序存储结点到文件fname中
{
//函数体略
}
void ReadFile(char* fname,BTreeNode*&BT)
//把fname文件中按层扫描存储的二叉树恢复到内存中，并由引用指针BT
//指向树根结点
{
//函数体略
}
void main()
{
BtreeNode *bt;
InitBTree(bt);
while(1)
{
cout<<"功能菜单:"<<end1;
cout<<'\t'<<"1.建立二叉树"<<end1;
cout<<'\t'<<"2.二叉树存盘"<<end1;
cout<<'\t'<<"3.由文件恢复二叉树"<<end1;
cout<<'\t'<<"4.以广义表形式输出二叉树"<<end1;
cout<<'\t'<<"5.结束程序运行"<<end1;
cout<<end1;
int m;
cout<<"输入你的选择(1-5):";
do cin>>m;while(m<1||m>5);
switch(m){
case 1:
char a[50];
cout<<"输入以'@'字符作为结束符的二叉树广义表表示:"<<end1;
cin>>ws;//跳过键盘输入缓冲区中的空白字符
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<<'';//输出根结点的值
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 ，它们的出现频率依次为4、7、5、2、9
，试画出对应的编码哈夫曼树(请按照左子树根结点的权小于等于右子树根结点的权的次序构
造)，求出每个字符的哈夫曼编码，并求出传送电文的长度。
解：
五种字符的哈夫曼编码依次为001,10,00,010,11。传送电文的总长度为60。
