BST 插入删除查找遍历

时间:2023-01-06 21:42:35
/*-------------------
输入:
5
66 99 33 22 11
3
33 5 11
输出
11 22 33 66 99
1
11 22 66 99
0
11 22 66 99
1
22 66 99
任务是输入N个数,建立一颗BST二叉搜索树,查找删除其中的一些元素,再中序遍历
如果找到了,删除并返回1,如果没找到,返回0;
-------------------*/

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
const int maxn=10000+10;
struct node{
	int x;
	struct node *f,*l,*r;	
	node(){
		f=NULL;l=NULL;r=NULL;
	}
};
void insert(struct node *p,int k){
	struct node *q;
	if(k>=p->x){
		if(p->r==NULL){
			q=new node;
			q->x=k;
			p->r=q;
			q->f=p;
		}else insert(p->r,k);
	}else{
		if(p->l==NULL){
			q=new node;
			q->x=k;
			p->l=q;
			q->f=p;
		}else insert(p->l,k);
	}
}
void zx(struct node *p){
	if(p->l!=NULL)zx(p->l);
	printf("%d ",p->x);
	if(p->r!=NULL)zx(p->r);
}
int find(struct node *p,int k){
	struct node *q,*t;
	if(p->x==k){
		if(p->l==NULL && p->r==NULL){			
			if(p==p->f->l)
				p->f->l=NULL;
			else
				p->f->r=NULL;
			free(p);			
		}else if(p->l==NULL && p->r!=NULL){
			q=p;t=p->f;
			if(p==t->l)t->l=p->r;
			else t->r=p->r;
			p->r->f=t;
			free(q);
		}else if(p->r==NULL && p->l!=NULL){
			q=p;t=p->f;
			if(p==t->l)t->l=p->l;
			else t->r=p->l;
			p->l->f=t;
			free(q);
		}else{
			q=p->l;
			while(q->r!=NULL)q=q->r;
			p->x=q->x;
			if(q->l==NULL && q->r==NULL){			
				if(q==q->f->l)
					q->f->l=NULL;
				else	
					q->f->r=NULL;
				free(q);			
			}else if(q->l!=NULL){
				p=q;t=q->f;
				if(q==t->l)t->l=q->l;
				else t->r=q->l;
				q->l->f=t;
				free(p);	
			}		
		}
		return 1;
	}
	if(p->x>k){
		if(p->l==NULL)return 0;
		else return find(p->l,k);		
	}else if (p->x<k){
		if(p->r==NULL)return 0;
		else return find(p->r,k);		
	}
}
int main(){
	int i,j,k,m,n,len,tmp,p;
	int ans=0;
	struct node *h;
	scanf("%d",&n);
	scanf("%d",&k);
	h=new node;
	h->x=k;	
	for(i=2;i<=n;i++){
		scanf("%d",&k);
		insert(h,k);
	}
	zx(h);
	puts("");
	scanf("%d",&m);
	for(i=1;i<=m;i++){
		scanf("%d",&k);
		printf("%d\n",find(h,k));
		zx(h);
	}
	system("pause");
	return 0;
}