19.4 排序二叉树（二叉搜索树）

19.4 排序二叉树（二叉搜索树）

排序二叉树(BST, Binary Search Tree)具有这样的性质，根节点的元素大于左子树所有节点的元素，且小于右子树所有节点的元素，并且左子树和右子树也是排序二叉树。

创建排序二叉树：

link insert(link t, unsigned char elem)
{
	if (!t)
		return make_node(elem);
	if (t->elem > elem)		/* insert to left subtree */
		t->l = insert(t->l, elem);
	else				/* if (t->elem <= elem), insert to right subtree */
		t->r = insert(t->r, elem);
	return t;
}

在排序二叉树中搜索某个元素的节点：

link search(link t, unsigned char elem)
{
	if (!t)
		return NULL;
	if (t->elem > elem)
		return search(t->l, elem);
	if (t->elem < elem)
		return search(t->r, elem);
	
	/* if (t->elem == elem) */
	return t;
}

删除排序二叉树中的某个元素的节点：

link delete(link t, unsigned char elem)
{
	link p;
	if (!t)
		return NULL;
	if (t->elem > elem)				/* delete from left subtree */
		t->l = delete(t->l, elem);
	else if (t->elem < elem)			/* delete form right subtree */
		t->r = delete(t->r, elem);
	else {				/* if (t->elem == elem) */
		if (t->l == NULL && t->r == NULL) {	/* if t is leaf node */
			free_node(t);
			t = NULL;
		} else if (t->l) {			/* if t has left subtree */
			/* replace t with the rightmost node in left subtree */
			for (p = t->l; p->r; p = p->r)
				;
			t->elem = p->elem;
			t->l = delete(t->l, t->elem);
		} else {				/* if t has right subtree */
			/* replace t wiht the leftmost node in right subtree */
			for (p = t->r; p->l; p = p->l)
				;
			t->elem = p->elem;
			t->r = delete(t->r, t->elem);
		}
	}
}