1.已知一组元素(46,25,78,62,12,37,70,29)，画出按元素排列顺序输入生成的一棵二叉树。
解：略
2.已知一棵二叉排序树如图6-11所示，若从中依次删除72,12,49,28结点，试分别画出每删除一
个结点后得到的二叉排序树。
解：略
28
/ \
12 49
\ / \
16 34 72
/ /
30 63
3.设在一棵二叉排序树的每个结点中，含有关键字key域和统计相同关键字结点个数的count域，
当向该树插入一个元素时，若树中已存在与该元素的关键字相同的结点，则就使该结点的count
域增1，否则就由该元素生成一个新结点而插入到树中，并使其count域置为1，试按照这种插入
要求编写一个算法。
解：
void Insert(BTreeNode*&BST,ElemType& item)
//向二叉排序树中插入一个不重复元素item，若树中存在该元素，则将一配结点值域中的
//count域的值加1即可
{
//从二叉排序树中查找关键字为item.key的结点，若查找成功则指针t指向该点结点，否则
//指针s指向待插入新结点的双亲结点
BTreeNode *t=BST,*S=NULL;
while(t!=NULL){
s=t;
if(item.key==t->data.key)
break;
else if(item.key<t->data.key)
t=t->left;
else
t=t->right;
}
//元素已存在，则将其值域中的count域的值增1，否则建立新结点并插入到合适位置
if(t!=NULL)
t->data.count++;
else{
BTreeNode* p=new BTreeNode;
p->data=item;
p->data.count=1;
p->left=p->right=NULL;
if(s==NULL)
BST=p;
else{
if(item.key<s->data.key)
s->left=p;
else
s->right=p;
}
}
}
4.编写一个非递归算法求出二叉排序树中的关键字最大的元素。
解：
ElemType FindMax(BTreeNode* BST)
//从二叉排序树中返回关键字最大的元素
{
if(BST==NULL){
cerr<<"不能在空树上查找最大值!"<<end1;
exit(1);
}
BTreeNode* t=BST;
while(t->right!=NULL)
t=t->right;
return t->data;
}
5.假定一棵二叉排序树被存储在具有ABTList数组类型的一个对象BST中，试编写出以下
算法。
1.初始化对象BST。
解：
void InitBTree(ABTList BST)
{
//将树置空
BST[0].left=0;
//建立空闲链接表
BST[0].right=1;
for(int i=1;i<BTreeMaxSize-1;i++)
BST[i].right=i+1;
BST[BTreeMaxSize-1].right=0;
}
2.向二叉树排序树中插入一个元素。
解：
void Insert(ANTList BST,int&t,const ElemType& item)
//向数组中的二叉排序树插入一个元素item的递归算法，变参t初始指向树根结点
{
if(t==0)//进行插入操作
{
//取出一个空闲结点
int p=BST[0].right;
if(p==0){
cerr<<"数组空间用完!"<<end1;
exit(1);
}
//修改空闲链表的表头指针，使之指向下一个空闲结点
BST[0].right=BST[p].right;
//生成新结点
BST[p].data=item;
BST[p].left=BST[p].right=0;
//把新结点插入到确定的位置
t=p;
}
else if(item.key<BST[t].data.key)
Insert(BST,BST[t].left,item);
//向左子树中插入元素
else
Insert(BST,BST[t].right,item);
//向右子树中插入元素
}
void Insert(ABTList BST,const ElemType& item)
//向数组中的二叉排序树插入一个元素item的非递归算法
{
//为新元素寻找插入位置
int t=BST[0].left,parent=0;
while(t!=0){
parent=t;
if(item.key<BST[t].data.key)
t=BST[t].left;
else
t=BST[t].right;
}
//由item生成新结点并修改空闲链表的表头指针
int p=BST[0].right;
if(p==0){
cerr<<"数组空间用完!"<<end1;
exit(1);
}
BST[0].right=BST[p].right;
BST[p].data=item;
BST[p].left=BST[p].right=0;
//将新结点插入到二叉排序树中的确定位置上
if(parent==0)
BST[o].left=p;
else if(item.key<BST[parent].data.key)
BST[parent].left=p;
else
BST[parent].right=p;
}
3.根据数组a中的n个元素建立二叉排序树。
解：
void CreateBSTree(ABTList BST,ElemType a[],int n)
//利用数组中的元素建立二叉排序树的算法
{
for(int i=0;i<n;i++)
Insert(BST,BST[0].left,a[i]);
}
4.中序遍历二叉排序树。
解：
void Inorder(ABTList BST,int t)
//对数组中的二叉树进行中序遍历的递归算法
{
if(t!=0){
Inorder(BST,BST[t].left);
cout<<BST[t].data.key<<'';
Inorder(BST,BST[t].right);
}
}
void Inorder(ABTList BST)
//对数组中的二叉树进行中序遍历的非递归算法
{
int s[10];//定义用于存储结点指针的栈
int top=-1; //定义栈顶指针并赋初值使s栈为空
int p=BST[0].left;//定义指针p并使树根指针为它的初值
while(top=-1||p!=0)
{//当栈非空或p指针非0时执行循环
while(p!=0){
top++;
s[top]=p;
p=BST[p].left;
}
if(top!=-1){
p=s[top];
top--;
cout<<BST[p].data.key<<'';
p=BST[p].right;
}
}
}
5.写出一个完整程序调用上述算法。
解：
#include<iostream.h>
#include<stdlib.h>
const int BTreeMaxSize=50;
struct student{
int key;
int rest;
};
typedef student ElemType;
//定义二叉排序树中元素的类型为student记录型
struct ABTreeNode{//定义二叉排序树的结点类型
ElemType data;
int left,right;
};
typedef ABTreeNode ABTList[BTreeMaxSize];
//定义保存二叉排序树的数组类型，各算法同上，在此省略
void main()
{
student a[8]={{36},{54},{25},{30},{43},{18},{50},{28}};
//为简单起见在每个元素中只给出关键字
ABTList bst;
InitBTree(bst);//初始化数组bst
//利用数组a在数组bst上建立一个二叉排序树
CreateBSTree(bst,a,8);
cout<<"中序:"<<end1;
Inorder(bst,bst[0].left);
cout<<end1;
}
该程序的运行结果为：
中序：
18 25 28 30 36 43 50 54
