1.已知一組元素(46,25,78,62,12,37,70,29)，畫出按元素排列順序輸入生成的一棵二叉樹。
解：略
2.已知一棵二叉排序樹如圖6-11所示，若從中依次刪除72,12,49,28結(jié)點(diǎn)，試分別畫出每刪除一
個結(jié)點(diǎn)后得到的二叉排序樹。
解：略
28
/ \
12 49
\ / \
16 34 72
/ /
30 63
3.設(shè)在一棵二叉排序樹的每個結(jié)點(diǎn)中，含有關(guān)鍵字key域和統(tǒng)計相同關(guān)鍵字結(jié)點(diǎn)個數(shù)的count域，
當(dāng)向該樹插入一個元素時，若樹中已存在與該元素的關(guān)鍵字相同的結(jié)點(diǎn)，則就使該結(jié)點(diǎn)的count
域增1，否則就由該元素生成一個新結(jié)點(diǎn)而插入到樹中，并使其count域置為1，試按照這種插入
要求編寫一個算法。
解：
void Insert(BTreeNode*&BST,ElemType& item)
//向二叉排序樹中插入一個不重復(fù)元素item，若樹中存在該元素，則將一配結(jié)點(diǎn)值域中的
//count域的值加1即可
{
//從二叉排序樹中查找關(guān)鍵字為item.key的結(jié)點(diǎn)，若查找成功則指針t指向該點(diǎn)結(jié)點(diǎn)，否則
//指針s指向待插入新結(jié)點(diǎn)的雙親結(jié)點(diǎn)
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，否則建立新結(jié)點(diǎn)并插入到合適位置
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.編寫一個非遞歸算法求出二叉排序樹中的關(guān)鍵字最大的元素。
解：
ElemType FindMax(BTreeNode* BST)
//從二叉排序樹中返回關(guān)鍵字最大的元素
{
if(BST==NULL){
cerr<<"不能在空樹上查找最大值!"<<end1;
exit(1);
}
BTreeNode* t=BST;
while(t->right!=NULL)
t=t->right;
return t->data;
}
5.假定一棵二叉排序樹被存儲在具有ABTList數(shù)組類型的一個對象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)
//向數(shù)組中的二叉排序樹插入一個元素item的遞歸算法，變參t初始指向樹根結(jié)點(diǎn)
{
if(t==0)//進(jìn)行插入操作
{
//取出一個空閑結(jié)點(diǎn)
int p=BST[0].right;
if(p==0){
cerr<<"數(shù)組空間用完!"<<end1;
exit(1);
}
//修改空閑鏈表的表頭指針，使之指向下一個空閑結(jié)點(diǎn)
BST[0].right=BST[p].right;
//生成新結(jié)點(diǎn)
BST[p].data=item;
BST[p].left=BST[p].right=0;
//把新結(jié)點(diǎn)插入到確定的位置
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)
//向數(shù)組中的二叉排序樹插入一個元素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生成新結(jié)點(diǎn)并修改空閑鏈表的表頭指針
int p=BST[0].right;
if(p==0){
cerr<<"數(shù)組空間用完!"<<end1;
exit(1);
}
BST[0].right=BST[p].right;
BST[p].data=item;
BST[p].left=BST[p].right=0;
//將新結(jié)點(diǎn)插入到二叉排序樹中的確定位置上
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.根據(jù)數(shù)組a中的n個元素建立二叉排序樹。
解：
void CreateBSTree(ABTList BST,ElemType a[],int n)
//利用數(shù)組中的元素建立二叉排序樹的算法
{
for(int i=0;i<n;i++)
Insert(BST,BST[0].left,a[i]);
}
4.中序遍歷二叉排序樹。
解：
void Inorder(ABTList BST,int t)
//對數(shù)組中的二叉樹進(jìn)行中序遍歷的遞歸算法
{
if(t!=0){
Inorder(BST,BST[t].left);
cout<<BST[t].data.key<<'';
Inorder(BST,BST[t].right);
}
}
void Inorder(ABTList BST)
//對數(shù)組中的二叉樹進(jìn)行中序遍歷的非遞歸算法
{
int s[10];//定義用于存儲結(jié)點(diǎn)指針的棧
int top=-1; //定義棧頂指針并賦初值使s棧為空
int p=BST[0].left;//定義指針p并使樹根指針為它的初值
while(top=-1||p!=0)
{//當(dāng)棧非空或p指針非0時執(zhí)行循環(huán)
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.寫出一個完整程序調(diào)用上述算法。
解：
#include<iostream.h>
#include<stdlib.h>
const int BTreeMaxSize=50;
struct student{
int key;
int rest;
};
typedef student ElemType;
//定義二叉排序樹中元素的類型為student記錄型
struct ABTreeNode{//定義二叉排序樹的結(jié)點(diǎn)類型
ElemType data;
int left,right;
};
typedef ABTreeNode ABTList[BTreeMaxSize];
//定義保存二叉排序樹的數(shù)組類型，各算法同上，在此省略
void main()
{
student a[8]={{36},{54},{25},{30},{43},{18},{50},{28}};
//為簡單起見在每個元素中只給出關(guān)鍵字
ABTList bst;
InitBTree(bst);//初始化數(shù)組bst
//利用數(shù)組a在數(shù)組bst上建立一個二叉排序樹
CreateBSTree(bst,a,8);
cout<<"中序:"<<end1;
Inorder(bst,bst[0].left);
cout<<end1;
}
該程序的運(yùn)行結(jié)果為：
中序：
18 25 28 30 36 43 50 54
