二叉搜索树

typedef struct node{
	ElemType key;
	struct node* left, * right;
	struct node* p;
}*TREE;
typedef struct {
	TREE root;
}*ROOTTREE;

TREE TREE_SEARCH(TREE x, int k)
{
	if (x == NULL || k == x->key)
		return x;
	if (k < x->key)
		return TREE_SEARCH(x->left, k);
	else
		return TREE_SEARCH(x->right, k);
}

TREE TREE_MINIMUM(TREE x)
{
	while (x->left != NULL)
		x = x->left;
	return x;
}

TREE TREE_MAXIMUM(TREE x)
{
	while (x->right != NULL)
		x = x->right;
	return x;
}

TREE tree_successor(TREE x)
{
	TREE y;
	if (x->right != NULL)
		return TREE_MAXIMUM(x->right);
	y = x->p;
	while (y != NULL && y->right = x)
	{
		x = y;
		y = x->p;
	}
	return y;
}

void tree_insert(ROOTTREE T,TREE z)
{
	TREE x, y;
	x = T->root;
	while (x != NULL)
	{
		y = x;
		if (z->key < x->key)
			x = x->left;
		else
			x = x->right;
	}
	z->p = y;
	if (y == NULL)
		T->root = x;
	else if (z->key < y->key)
		y->left = z;
	else
		y->right = x;
}

void transplant(ROOTTREE T, TREE u, TREE v)
{
	if (u->p == NULL)
		T->root = v;
	else if (u->p->left == u)
		u->p->left = v;
	else
		u->p->right = v;
	if (v != NULL)
		v->p = u->p;
}

void tree_delete(ROOTTREE T, TREE z)
{
	TREE y;
	if (z->left == NULL)
		transplant(T, z, z->right);
	else if (z->right == NULL)
		transplant(T, z, z->left);
	else
	{
		y = TREE_MAXIMUM(z->right);
		if (y != z->right)
		{
			transplant(T, y, y->right);
			y->right = z->right;
			z->right->p = y;
		}
		transplant(T, z, y);
		y->left = z->left;
		y->left->p = y;
	}
}