15问答网 > 二叉搜索树的基本操作

二叉搜索树的基本操作

2025-02-08 02:00:26

推荐回答（1个）

回答1：

哈哈，居然有人来提问了，城院的

我刚奋斗了2小时做了下，你看看对不？

Test5.cpp:

#include

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<<"请输入你要测试的二叉搜索树:"<

for(i=0;i

cin>>a[i];

}

CreateBSTree(bst,a,n);

cout<<"你输入的二叉搜索树的广义表形式为:";

PrintBSTree(bst);

cout<

cout<<"输入一个待插入结点的整数值:";

cin>>x;

Insert(bst,x);

cout<<"插入结点后的二叉搜索树的广义表形式为:";

PrintBSTree(bst);

cout<

cout<<"输入一个待删除结点的值:";

cin>>x;

if(Delete(bst,x)) cout<<"删除元素"<

else cout<<"删除元素"<

PrintBSTree(bst);

cout<

cout<<"该二叉搜索树中的最大值为:"<

}

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<data;

cout<<'['<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(itemdata) 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(itemdata) parent->left=p;

else parent->right=p;

}

void CreateBSTree(BTreeNode *&bst, ElemType a[], int n) //建立二叉搜索树（用非递归算法实现)

{

bst=NULL;

for(int i=0;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(itemdata){

parent=t;

t=t->left;

}

else{

parent=t;

t=t->right;

}

if(t->count>1){

t->count--;

return true;

}

else if(t==NULL){

cout<<"没有找到待删除结点!"<

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<<"该二叉搜索树为空！"<

exit(1);

}

max=bst->data;

while(bst!=NULL){

if(maxdata)

max=bst->data;

bst=bst->right;

}

return max;

}

你试试吧，应该对的，选我做答案哈~

最新问答

我今天收到公安局询问通知书是东公（刑）询通字这个是什么意思啊？

广州天河去东莞石龙怎样比较便宜?

我们一起看动画片用英语怎么说

在郑州找个会计工作，想问下郑州的会计工资一般都是多少呢？

江苏慈安堂的刘家峰大夫擅长治疗什么疾病？

五一节放假安排

前几天跳绳现在小肚子不能用力用力就疼怎么回事

从南昌到九江开车走国道怎么走

email营销

上海泰衡中医门诊部有限公司泰衡母婴护理服务分公司怎么样？