#include<stdio.h>
#include<stdlib.h>
typedef struct Tnode{
int data;/输入的数据/
struct Tnode *lchild,*rchild;/结点的左右指针，分别指向结点的左右hai子/
}*node,BSTnode;
searchBST(node t,int key,node f,node *p)/查找函数/
{
if(!t)
{*p=f;return(0);}/查找不成功/
else
if(key==t->data) {*p=t;return(1);}/查找成功/
else
if(keydata) searchBST(t->lchild,key,t,p);/在左子树中继续查找/
else
searchBST(t->rchild,key,t,p);/在右子树中继续查找/
}
insertBST(node t,int key)/插入函数/
{
node p=NULL,s=NULL;
if(!searchBST(t,key,NULL,&p))/查找不成功/
{
s=(node)malloc(sizeof(BSTnode));
s->data=key;
s->lchild=s->rchild=NULL;
if(!p) t=s;/被插结点s为新的根结点/
else
if(keydata) p->lchild=s;/被插结点s为左hai子/
else p->rchild=s;/被插结点s为右hai子/
return(1);
}
else
return(0);/树中已有关键字相同的结点，不再插入/
}
inorderTraverse(node *t) /中序遍历函数/
{
if(*t){
if(inorderTraverse(&(*t)->lchild)) /中序遍历根的左子树/
printf("%d",(t)->data); /输出根结点/
if(inorderTraverse(&(t)->rchild));/中序遍历根的右子树/
}
return(1);
}
node Delete(node t,int key) /删除函数/
{
node p=t,q=NULL,s,f;
while(p!=NULL) /查找要删除的点/
{
if(p->data==key)
break;
q=p;
if(p->data>key) p=p->lchild;
else
p=p->rchild;
}
if(p==NULL)
return t; /查找失败/
if(p->lchild==NULL)/p指向当前要删除的结点/
{
if(q==NULL) t=p->rchild; /q指向要删结点的父母/
else
if(q->lchild==p) q->lchild=p->rchild; /p为q的左hai子/
else
q->rchild=p->rchild;/p为q的右hai子/
free(p);
}
else{ /p的左hai子不为空/
f=p;
s=p->lchild;
while(s->rchild) /左拐后向右走到底/
{
f=s;
s=s->rchild;
}
if(f==p) f->lchild=s->lchild; / 重接f的左子樹/
else f->rchild=s->lchild; /重接f的右子树/
p->data=s->data;
free(s);
}
return t;
}
void main()
{
node T=NULL;
int num;
int s=0,j=0,i=0;
int ch=0;
node p=NULL;
printf("输入一串数,每个数以空格分开:");
do{
scanf("%d",&num);
if(!num)printf("完成输入!\n");
else insertBST(&T,num);
}while(num);
printf("\n 1:中序输出");
printf("\n 2:输入元素");
while(ch==ch)
{
scanf("%d",&ch);
switch(ch){
case 0:
exit(0);/*0--退出*/
case 1:
printf("中序遍历输出结果为:\n ");
inorderTraverse(&T);/*1--中序遍历*/
break;
case 2:
printf("输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历，否则输出无x:");
scanf("%d",&num); /*3--删除某个结点*/
if(searchBST(T,num,NULL,&p))
{
T=Delete(T,num);
printf("删除成功!中序遍历输出: \n ");
inorderTraverse(&T);
}
else
printf(" 无%d",num);
break;
default:
printf("无此结点\n");
break; /*输入无效字符*/
}
}
}
#include
using namespace std;
class node
{
public:
node(int i):data(i),lef(NULL),right(NULL){}
void inorder(node*&root)//中序遍历，符合升序输出
{
if(root!=NULL)
{
inorder(root->left);
cout<data<<' ';
inorder(root->right);
}
}
void insert(node *&ptr,int item)//在查找树中插入元素
{
if(ptr==NULL)
ptr=new node(item);
else if(itemdata)
insert(ptr->left,item);
else insert(ptr->right,item);
}
node *find(node *&ptr,int item) //在查找树中查找元素，找到返回所在结点指针，找不到返回空指针.
{
if(ptr==NULL)
return NULL;
if(ptr->data==item)
return ptr;
else if(itemdata)
find(ptr->left,item);
else find(ptr->right,item);
}
node &findy(node &ptr,int item) //在查找树中查找肯定存在的元素，并返回其引用
{
if(ptr->data==item)
return ptr;
else if(itemdata)
findy(ptr->left,item);
else findy(ptr->right,item);
}
node rl(){return left;}
node rr(){return right;}
void dele(node *&ptr)//删除值为item所在结点
{
if(ptr->rl)==NULL&&ptr->rr()==NULL)
ptr=NULL;
else if(ptr->rr()==NULL)
ptr=ptr->rl();
else
ptr=ptr->rr();
}
private:
int data;
node *left;//左hai子结点
node *right;//右hai子结点
};
int main()
{
int t,i=0,j;
cout<<"输入数字个数(结点个数):";
cin>>t;
cout<<"输入"<<t<<"个数字，数字之间用空格隔开:";
cin>>j;
node *x=new node(j);
for(;i<t-1;i++)
{
cin>>j;
x->insert(x,j);
}
cout<<"中序遍历为:";
x->inorder(x);//作中序遍历
cout<<"\n输入操作(当输入-1时程序结束):"<<endl;
cin>>j;
while(j!=-1)
{
node *t=x->find(x,j);//定位结点
if(t!=NULL)
{
node *&y=x->findy(x,j);
x->dele(y);
cout<<"中序遍历为:";
x->inorder(x);
}
else cout<<"无"<<j;
cout<<"\n输入操作(当输入-1时程序结束):"<<endl;
cin>>j;
}
return 0;
}
