二叉查找树

基本的二叉查找树代码：

#include <iostream>
using namespace std;

struct node{
	int data;
	struct node *parent;
	struct node *lchild;
	struct node *rchild;
};
//输出
void display(struct node *p)
{
	if (p)
	{
		display(p->lchild);
		cout<<p->data<<" ";
		display(p->rchild);
	}
	return;
}
//最小值节点
struct node *min(struct node *root)
{
	struct node *p, *back;
	p = root;
	while (p)
	{
		back = p;
		p = p->lchild;
	}
	return back;
}
//返回最大值节点
struct node *max(struct node *root)
{
	struct node *p, *back;
	p = root;
	while (p)
	{
		back = p;
		p = p->rchild;
	}
	return back;
}

//后继
struct node *Successor(struct node *q)
{
	struct node *y;
	if (q->rchild != NULL)
	{
		return min(q->rchild);
	}
	y = q->parent;
	while (y && y->rchild == q)
	{
		q = y;
		y = y->parent;
	}
	return y;
}

//前驱
struct node *Presuccessor(struct node *q)
{
	struct node *y;
	if (q->lchild != NULL)
	{
		return max(q->lchild);
	}
	y = q->parent;
	while (y && y->lchild == q)
	{
		q = y;
		y = y->parent;
	}
	return y;
}
//查找
struct node *find(struct node *root, int value)
{
	struct node *p;
	p = root;
	while(p && p->data != value){
		if (p->data < value)
		{
			p = p->rchild;
		} 
		else
		{
			p = p->lchild;
		}
	}
	return p;
}
//插入节点
struct node *insert(struct node *root, struct node *q)
{
	struct node *back = new node;
	struct node *p = new node;
	
	back = NULL;
	p = root;
	while (p != NULL)
	{
		back = p;
		if (p->data < q->data)
		{		
			p = p->rchild;
		} 
		else
		{
			p = p->lchild;
		}
	}
	
	q->parent = back;
	if (back == NULL)
	{
		root = q;
	} 
	else
	{
		if (back->data < q->data)
		{
			back->rchild = q;
		}
		else
		{
			back->lchild = q;
		}
	}
	return root;
}

//删除节点
struct node *del(struct node *root, struct node *z)
{
	struct node *y = new node;
	struct node *x = new node;
	x = NULL;
	if (z->lchild == NULL || z->rchild == NULL){
		y = z;
	}
	else {
		y = Successor(z);
	}
	if (y->lchild != NULL) {
		x = y->lchild;
	}
	else {
		x = y->rchild;
	}
	if (x != NULL) {
		x->parent = y->parent;
	}
	if (y->parent == NULL) {
		root = x;
	}
	else {
		if (y == y->parent->lchild){
			y->parent->lchild = x;
		}
		else{
			y->parent->rchild = x;
		}
	}
	//
	if (y != z){
		z->data = y->data;
	}
	return root;
}

int main()
{
	struct node *root = NULL;

	int input;
	cin>>input;
	while (input)
	{
		struct node *p = new node;
		p->data = input;
		p->parent = NULL;
		p->lchild = NULL;
		p->rchild = NULL;

		root = insert(root, p);

		cin>>input;
	}
	display(root);
	cout<<endl;

	cout<<"Input the data you want to find: ";
	cin>>input;
	struct node *f = find(root, input);
	if (f == NULL)
	{
		cout<<"Not exit!!"<<endl;
	}
	cout<<"Delete..."<<endl;
	root = del(root, f);
	//struct node *y = del(&root, f);

	cout<<"After deteting...."<<endl;
	display(root);
	cout<<endl;
	return 0;
}