二叉搜索树的基本操作二.实验内容设在一棵二叉搜索树的每个结点的data域中,含有关键字key域和统计相同关键字元素个数的count域.当向该树插入一个元素时,若树中已有相同关键字值的结点,
来源：学生作业帮助网 编辑：六六作业网 时间：2025/01/12 23:01:15
二叉搜索树的基本操作二.实验内容设在一棵二叉搜索树的每个结点的data域中,含有关键字key域和统计相同关键字元素个数的count域.当向该树插入一个元素时,若树中已有相同关键字值的结点,
二叉搜索树的基本操作
二.实验内容
设在一棵二叉搜索树的每个结点的data域中,含有关键字key域和统计相同关键字元素个数的count域.当向该树插入一个元素时,若树中已有相同关键字值的结点,则使该结点的count域值增1,否则由该元素值生成一个新结点插入到该树中,并使其count域置为1.当向该树删除一个元素时,若树中该元素结点的count域值大于1,则使该结点的count域值减1,否则（count域值等于1）删除该结点.请编写程序实现该二叉搜索树的下述基本操作：
初始化该二叉搜索树void InitBSTree(BTreeNode *&bst);
以广义表形式输出该二叉搜索树（每个结点输出内容包括关键字值与相同元素个数值）void PrintBSTree(BTreeNode *bst);
插入一个元素到该二叉搜索树（用非递归算法实现） void Insert (BTreeNode *&bst,ElemType item);
从二叉搜索树中删除某个元素（用非递归算法实现） int Delete (BTreeNode *&bst ,ElemType item).
求该二叉搜索树的最大关键字值（用非递归算法实现）ElemType MaxBSTree(BTreeNode *bst).
把二叉搜索树的结构定义及基本操作实现函数存放在文件BSTree.h中.
建立主程序文件test5.cpp,在主函数main()中通过调用BSTree.h中的函数进行测试.提示：可以在主函数中首先初始化二叉搜索树；然后从键盘输入数据,通过循环调用插入算法建立二叉搜索树；再以广义表形式输出该二叉搜索树；输出二叉搜索树中的最大结点值；最后调用删除算法删除某元素,并输出删除后的二叉搜索树.
二叉搜索树的基本操作二.实验内容设在一棵二叉搜索树的每个结点的data域中,含有关键字key域和统计相同关键字元素个数的count域.当向该树插入一个元素时,若树中已有相同关键字值的结点,
哈哈,居然有人来提问了,城院的
我刚奋斗了2小时做了下,你看看对不?
Test5.cpp:
#include <iostream.h>
#include <stdlib.h>
typedef double ElemType;
#define Maxsize 100
#include "BSTree.h"
void main()
{
int i,n;
ElemType x;
ElemType a[Maxsize];
BTreeNode *bst;
InitBSTree(bst);
cout<<"请输入你所要测试的二叉搜索树的结点的个数:";
cin>>n;
cout<<"请输入你要测试的二叉搜索树:"<<endl;
for(i=0;i<n;i++){
cin>>a[i];
}
CreateBSTree(bst,a,n);
cout<<"你输入的二叉搜索树的广义表形式为:";
PrintBSTree(bst);
cout<<endl;
cout<<"输入一个待插入结点的整数值:";
cin>>x;
Insert(bst,x);
cout<<"插入结点后的二叉搜索树的广义表形式为:";
PrintBSTree(bst);
cout<<endl;
cout<<"输入一个待删除结点的值:";
cin>>x;
if(Delete(bst,x)) cout<<"删除元素"<<x<<"成功!"<<endl;
else cout<<"删除元素"<<x<<"失败!"<<endl;
PrintBSTree(bst);
cout<<endl;
cout<<"该二叉搜索树中的最大值为:"<<MaxBSTree(bst)<<endl;
}
BSTree.h:
struct BTreeNode{
ElemType data;
ElemType count;
BTreeNode *left;
BTreeNode *right;
};
void InitBSTree(BTreeNode *&bst) //初始化二叉搜索树
{
bst=NULL;
}
void PrintBSTree(BTreeNode *bst) //以广义表形式输出二叉搜索树
{
if(bst!=NULL){
cout<<bst->data;
cout<<'['<<bst->count<<']';
if(bst->left!=NULL||bst->right!=NULL){
cout<<'(';
PrintBSTree(bst->left);
if(bst->right!=NULL)
cout<<',';
PrintBSTree(bst->right);
cout<<')';
}
}
}
void Insert (BTreeNode *&bst, ElemType item)
{
BTreeNode*t=bst,*parent=NULL;
while(t!=NULL){
parent=t;
if(item<t->data) t=t->left;
else if(item>t->data) t=t->right;
else{
t->count++;
break;
}
}
if((t==NULL)||item!=parent->data){
BTreeNode*p=new BTreeNode;
p->data=item;
p->count=1;
p->left=p->right=NULL;
if(parent==NULL) bst=p;
else if(item<parent->data) parent->left=p;
else parent->right=p;
}
}
void CreateBSTree(BTreeNode *&bst, ElemType a[], int n) //建立二叉搜索树（用非递归算法实现)
{
bst=NULL;
for(int i=0;i<n;i++)
Insert(bst,a[i]);
}
bool Delete (BTreeNode *&bst , ElemType item)
{
BTreeNode *t=bst,*parent=NULL,*m,*n;
while((t!=NULL)&&(t->data!=item)){
if(item==t->data) break;
else{
if(item<t->data){
parent=t;
t=t->left;
}
else{
parent=t;
t=t->right;
}
}
}
if(t->count>1){
t->count--;
return true;
}
else if(t==NULL){
cout<<"没有找到待删除结点!"<<endl;
return false;
}
else{
if((t->left==NULL)&&(t->right==NULL)){
if(t==bst)
bst=NULL;
else{
if(t==parent->left)
parent->left=NULL;
else
parent->right=NULL;
}
}
else if((t->left==NULL)||(t->right==NULL)){
if(t==bst){
if(t->left==NULL)
bst=t->right;
else
bst=t->left;
}
else{
if((t==parent->left)&&(t->left!=NULL))
parent->left=t->left;
else if((t==parent->left)&&(t->right!=NULL))
parent->left=t->right;
else if((t==parent->right)&&(t->left!=NULL))
parent->right=t->left;
else if((t==parent->right)&&(t->right!=NULL))
parent->right=t->right;
}
}
else{
if((t->left!=NULL)&&(t->right!=NULL)){
m=t;
n=t->left;
while(n->right!=NULL){
m=n;
n=n->right;
}
t->data=n->data;
if(m==t)
t->left=n->left;
else
m->right=n->left;
t=n;
}
}
free(t);
return true;
}
}
ElemType MaxBSTree(BTreeNode *bst) //求二叉搜索树的最大结点值（用非递归算法实现）
{
ElemType max;
if(bst==NULL){
cout<<"该二叉搜索树为空!"<<endl;
exit(1);
}
max=bst->data;
while(bst!=NULL){
if(max<bst->data)
max=bst->data;
bst=bst->right;
}
return max;
}
你试试吧,应该对的,选我做答案哈~
