各种树结构之一二叉查找树

好久没动数据结构了，今天就来一发。

~~之后的几篇都会介绍树形结构~~。。。what a flag

二叉查找/搜索树

1：定义

二叉树(binary)是一种特殊的树。二叉树的每个节点最多只能有2个子节点：

由于二叉树的子节点数目确定，所以可以直接采用上图方式在内存中实现。每个节点有一个左子节点(left children)和右子节点(right children)。左子节点是左子树的根节点，右子节点是右子树的根节点。

如果我们给二叉树加一个额外的条件，就可以得到一种被称作二叉搜索树(binary search tree)的特殊二叉树。二叉搜索树要求：每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大。（所以还有一个特性就是”中序遍历“可以让结点有序。）

(如果我们假设树中没有重复的元素，那么上述要求可以写成：每个节点比它左子树的任意节点大，而且比它右子树的任意节点小)

如下图

2：实现

1.节点

节点有四个域，左儿子，右儿子，父亲，值域。

typedef int treetype;

typedef struct bstnode
{
	struct bstnode *lson;
	struct bstnode *rson;
	struct bstnode *parent;
	treetype key;
} bstnode,*bsttree;

2.中序遍历

由于bst的性质我们知道，中序遍历可以使节点有序。

void inorder_treewalk(bstnode *x)
{
	if (x!=NULL)
	{
		inorder_treewalk(x->lson);
		printf("%tpye ",x->key);
		inorder_treewalk(x->rson);
	}
}

3.搜索

在二叉搜索树b中查找x的过程为：

1、若b是空树，则搜索失败，否则：

2、若x等于b的根节点的数据域之值，则查找成功；否则：

3、若x小于b的根节点的数据域之值，则搜索左子树；否则：

4、查找右子树。

bstnode *bst_search(bstnode *x,treetpye key)
{
	if (x==NULL && x->key==key)
		return x;
	if (x->key > key)
		return bst_search(x->lson,key);
	else
		return bst_search(x->rson,key);
}

还有一个迭代版本的，比上面的效率高（系统栈调用）

bstnode *bst_search(bstnode *x,treetpye key)
{
	while (x!=NULL && k!=x->key)
		if (x->key > key)
			x=x->lson;
		else
			x=x->rson;
	return x;
}

4.最大最小值

直接找到最左，最右边的点

bstnonde *tree_min(bstnode *x)
{
	while (x->lson!=NULL)
		x=x->lson;
	return x;
}

bstnode *tree_max(bstnode *x)
{
	while (x->rson!=NULL)
		x=x->rson;
	return x;
}

5.前驱和后继

某一个节点x的后继就是大于key[x]的关键字中最小的那个节点，前驱就是小于key[x]的关键字中最大的那个节点。

bstnode *tree_successor(bstnode *x)
{
	if (x->rson != NULL)
		return tree_min(x->rson);
	else
	{
		bstnode *y=x->parent;
		while (y!=NULL && x==y->rson)
		{
			x=y;
			y=x->parent;
		}
		return y;
	}
}

bstnode *tree_predecessor(bstnode *x)
{
	if (x->lson != NULL)
		return tree_max(x->lson);
	else
	{
		bstnode *y=x->parent;
		while (y!=NULL && x==y->lson)
		{
			x=y;
			y=x->lson;
		}
		return y;
	}
}

6.插入

向一个二叉搜索树b中插入一个节点s的算法，过程为：

1、若b是空树，则将s所指结点作为根节点插入，否则：

2、若s->key等于b的根节点的数据域之值，则返回，否则：

3、若s->key小于b的根节点的数据域之值，则把s所指节点插入到左子树中，否则：

4、把s所指节点插入到右子树中。（新插入节点总是叶子节点）

bstnode *tree_insert(bsttree *bst,treetype key)
{
	bstnode *x,*y=NULL,*z;
	x=*bst;
	z=(bstnode *)malloc(sizeof(bstnode));
	z->key=key;
	z->lson=NULL;
	z->rson=NULL;
	z->parent=NULL;
	while (x!=NULL)
	{
		y=x;
		if (z->key>x->key)
			x=x->rson;
		else
			x=x->lson;
	}
	if (y==NULL)   //empty
		*bst=z;
	else  if(z->key>y->key)
		y->rson=z;
	else
		y->lson=z;
	z->parent=y;
}

7.删除

(待删除的节点key和图a图b图c中的节点y是相同的节点。)

情况1 key为叶节点，则直接删。

情况2 key只有一个子节点，就把key给排挤掉。也就是，让key的父节点指向key的左儿子节点(或右儿子节点)，并且让key的左子节点(或右儿子节点)的父节点指向key的父节点。如果要通过这样的图形形象的方式而非前面数字逻辑的方式进行删除，那么需要在节点结构体中增加parent指针，从而维护树的结构。

情况3 key有两个子节点，则找到key的后继，然后先用key的后继的值替换key的值，在进入到以key的后继为root的子树中，删除key节点。容易根据后继的特点知道，key的后继没有左儿子，所以删除key节点，转化为了在以key后继为root的子树中，进行情况2的删除。

void tree_delete(bsttree *t,treetype key)
{
	bstnode *x,*y,*z;
	x=tree_search(t,key);
	if (x==NULL) return;
	if (x->lson==NULL || x->rson==NULL)
		y=x;
	else
		y=tree_predecessor(x);
	if (y->rson!=NULL)
		z=y->rson;
	else
		z=y->lson;
	if (z!=NULL)
		z->parent=y->parent;
	if (y->parent==NULL)
		*t=z;
	else
	{
		if (y->parent->rson == y)
            y->parent->rson = z;
    	else
            y->parent->lson = z;
	}
	if (y!=x)
		x->key=y->key;
	free(y);
}

上述实现中的删除比较复杂。有一种简单的替代操作，称为懒惰删除(lazy deletion)。在懒惰删除时，我们并不真正从二叉搜索树中删除该节点，而是将该节点标记为“已删除”。这样，我们只用找到元素并标记，就可以完成删除元素了。如果有相同的元素重新插入，我们可以将该节点找到，并取消删除标记。

懒惰删除的实现比较简单，可以尝试一下。树所占据的内存空间不会因为删除节点而减小。懒惰节点实际上是用内存空间换取操作的简便性。

至此，bst的所有操作就都讲完了。

the end.

各种树结构之一 二叉查找树

各种树结构之一二叉查找树