二叉查找树及其实现(1)

     最近开始读算法导论，写的过程中把一些想法和代码写来下来，希望各种多多指点，提供建议，抑或指出我理解的不对的地方。

      二叉查找树比二叉树多了一个指向父节点的指针，在查询二叉树中根节点是唯一父节点域是NULL的节点。二叉查找树的性质：

       设x是一个二叉查找树的节点。如果y是x的左子树中的一个节点则key[y]<key[x],反之，若y是x的右子树中的一个节点则key[x]<key[y].

       二叉树的结构定义：

typedef int Item;
typedef struct node{
	Item item;
	struct node* left;
	struct node* right;
	struct node* parent;
}node;
typedef struct node* tree;

        二叉树寻找后继的函数

node* successor(node *x)
{
	if( x->right != NULL)
	{
		return successor(x->right);
	}
	node* y = x->parent;
	while( y != NULL && x == y->right)
	{
		x = y;
		y = y->parent;
	}
	return y;
}

      二叉树搜索函数，从根节点开始，如果要找的值小于当前节点的数据域的值，则左移指针，否则向右子树移动。直到相等的时候，返回指针所指的节点。

node* search(node *x, Item k)
{
	if( x == NULL || k == x->item)
		return x;
	if( k < x->item)
		search(x->left, k);
	else
		search(x->right, k);
}

    插入函数的实现。首先生成一个节点，指针域置空，数据域是要插入的值，然后使用x指针search整个树，找到要插入的位置，y指针始终指向x的父节点。

tree insert(tree t, const Item item)
{
	node *p = (node*)malloc(sizeof(node));
	p->left = p->right = p->parent = NULL;
	p->item = item;
	node *x = t, *y = NULL;
	// x用来遍历tree
	// y用来记录x的 parent
	while( x != NULL)
	{
		y = x;
		if( item < x->item)
			x = x->left;
		else
			x = x->right;
	}
	p->parent = y;

	//如果t是空树 
	if( y == NULL)
	{
		t = p;
	}
	else
	{
		if( item < y->item)
			y->left = p;
		else
			y->right = p;
	}
	return t;
}