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