二叉排序树的基本操作

灰太狼 2024-02-18 22:24 45阅读 0赞

不注意细节，找错找了半天。

\#include<iostream>  
\#include<stdio.h>  
\#include<stdlib.h>  
\#include<string.h>  
using namespace std;  
typedef struct node  
\{  
int d;  
node \*lchild,\*rchild;  
\}node,\*BiTree;  
int Search(BiTree T,int key,BiTree f,BiTree \*p)  
\{  
if(!T)  
\{  
\*p=f;  
return 0;  
\}  
else if(T->d==key)  
\{  
\*p=T;  
return 1;  
\}  
else if(T->d<key)  
\{  
return Search(T->rchild,key,T,p);  
\}  
else  
return Search(T->lchild,key,T,p);  
\}  
int Insert(BiTree \*T,int key)  
\{  
BiTree q,s;  
if(!Search(\*T,key,NULL,&s))  
\{  
q=(BiTree)new node; //这个node地方我错过，我误写成了BiTree  
if(key==0)  
cout<<"99"<<endl;  
q->d=key;  
q->lchild=q->rchild=NULL;  
if(!s)  
\*T=q;  
else if(key>s->d)  
s->rchild=q;  
else  
s->lchild=q;  
  
\}  
  
\}  
void ord(BiTree T)  
\{  
if(!T)  
return ;  
else  
\{  
ord(T->lchild);  
//if(T->d==0)  
//cout<<"99"<<endl;  
cout<<T->d<<" ";  
ord(T->rchild);  
\}  
\}  
int DelBT(BiTree \*T) 分为三种情况，1.叶子节点，2.单分支，3.左右孩子都有，找到左分支的最右下的节点，替换被删节点，然后调整左子树，  
\{  
BiTree p,w;  
if(!(\*T)->lchild&&!(\*T)->rchild)  
\{  
\*T=NULL;  
\}  
else if(!(\*T)->lchild)  
\{  
p=\*T;  
(\*T)=(\*T)->rchild;  
free(p);  
\}  
else if(!(\*T)->rchild)  
\{  
p=\*T;  
(\*T)=(\*T)->lchild;  
free(p);  
\}  
else  
\{  
p=(\*T);  
w=p->lchild;  
while(w->rchild)  
\{  
p=w;  
w=w->rchild;  
\}  
(\*T)->d=w->d;  
if(p!=(\*T))  
p->rchild=w->lchild;  
else  
p->lchild=w->lchild;  
return 1;  
\}  
\}

int Del(BiTree \*T,int key)  
\{  
if(!(\*T))  
\{  
cout<<"该数不在二叉排序树中！"<<endl;  
return 0;  
\}  
else if(key==(\*T)->d)  
\{  
DelBT(T);  
return 1;  
\}  
else if(key>(\*T)->d)  
Del(&(\*T)->rchild,key);  
else  
Del(&(\*T)->lchild,key);  
\}  
int main()  
\{  
BiTree T=NULL; //这点NULL害我找了半天，长记性了，指针一定要先NULL；  
int a\[10\]=\{2,5,99,4,8,77,66,15,3,45\};  
int i,j,n=10,m;  
for(i=0;i<10;i++)  
Insert(&T,a\[i\]);  
cout<<"中序遍历为："<<endl;  
ord(T);  
while(n--)  
\{  
cout<<"输入你要删除的元素："<<endl;  
cin>>m;  
Del(&T,m);  
cout<<"删除后二叉排序树为："<<endl;  
ord(T);  
\}  
return 0;  
\}