#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

#define TREE_TYPE int

typedef struct TREE_NODE{
	TREE_TYPE value;
	struct TREE_NODE *left;
	struct TREE_NODE *right;
}TreeNode;

static TreeNode  *tree;

void insert(TREE_TYPE value)
{
	TreeNode *current;
	TreeNode **link;

	link = &tree;

	while(( current =*link)!=NULL)
	{
		if(value < current->value)
			link =&current->left;
		else
		{
			assert(value !=current->value);
			link=&current->right;
		}
	}

	current = malloc(sizeof(TreeNode));
	assert(current !=NULL);
	current->value = value;
	current->left =NULL;
	current->right = NULL;
	*link = current;
}

TreeNode *find(TREE_TYPE value)
{
	TreeNode *current;
	current = tree;
	while(current !=NULL && current->value != value)
	{
		if(value < current->value)
		{
			current = current->left;
		}
		else
		{
			current = current->right;
		}
	}
	if(current != NULL)
		return current;
	else
		return NULL;
}
TreeNode *find_parent(TREE_TYPE value)
{
	TreeNode *current;
	TreeNode *parent;
	current = tree;
	while(current !=NULL && current->value != value)
	{
		if(value < current->value)
		{
			parent=current;
			current = current->left;
		}
		else
		{
			parent=current;
			current = current->right;
		}
	}
	if(current != NULL)
		return parent;
	else
		return NULL;
}

void delete(TreeNode *current,TreeNode *parent,TreeNode *delNode)
{
	TreeNode *s,*q;
	int fag	= 0;
	if(delNode->left == NULL)
		s = delNode->right;
	else if(delNode->right == NULL)
		s = delNode->left;
	else 
	{
		q=delNode;
		s=delNode->left;
		while(s->right != NULL)
		{
			q=s;
			s=s->right;
		}
		if(q==delNode)
		{
			q->left=s->left;
		}
		else 
			q->right=s->left;
		delNode->value = s->value;
		free(s);
		fag=1;
	}
	if(fag==0)
	{
		if(parent==NULL)
			current=s;
		else if(parent->left==delNode)
			parent->left=s;
		else
			parent->right=s;
		free(delNode);
	}
}