二叉排序树（二叉查找树）的基本操作

           二叉排序树的查找属于动态查找的范畴，根据查找过程中是否对表进行修改，可以把查找分为静态查找和动态查找。动态查找表的特点是：表结构本身是在查找过程中动态生成的，即对于给定的key值，若表中存在其关键字等于key的记录，则查找成功并返回，否则插入关键字等于key的记录。

       二叉排序树或者是一颗空树，或者是具有下列性质的二叉树：

     （1）若它的左子树非空，则左子树上的所有结点的值均小于根节点的值；

     （2）若它的右子树非空，则右子树上的所有结点的值均大于根节点的值；

     （3）它的左右子树也分别为二叉排序树；

1、二叉排序树的数据结构

typedef struct node
{
	short key;
	struct node *rchild,*lchild;
} BSTNode,*BSTree;

2、二叉排序树的插入和生成

      已知一个关键字值为key的节点s，若将其插入到二叉排序树中，只要保证插入后仍符合二叉排序树的定义即可，插入可以用一下方法。

    （1）若二叉排序树为空树，则key称为二叉排序树的根;
    （2）若二叉排序树非空，则将key与二叉排序树的根比较，如果key值等于根节点，则停止插入；如果key值小于根节点的值，则将key插入左子树；如果key值大于根节点的值，则将key插入右子树；

二叉树的插入算法如下：

void InsertBST(BSTree* bst,short key)
{
    BSTree s;
    if(*bst==NULL)    //递归结束条件;该结点为空时创建结点;
    {
        s=(BSTree)malloc(sizeof(BSTNode));
        s->key=key;
        s->lchild=NULL;
        s->rchild=NULL;
        *bst=s;
    }
    else if(key<(*bst)->key)
    {
        InsertBST(&((*bst)->lchild),key);
    }
    else if(key>(*bst)->key)
    {
        InsertBST(&((*bst)->rchild),key);
    }
}

/******************
* 根据二叉排序树的插入算法可以创建一颗二叉排序树;
****************************/
void CreateBST(BSTree* bst)
{
    char key;
    *bst=NULL;
    scanf("%c",&key);
    while (key!='?')          //输入字符的结束是'？';
    {
        InsertBST(bst,key);
        scanf("%c",&key);
    }
}

3、二叉排序树的删除

       在二叉排序树中删除一个结点比插入一个结点要困难，除非是叶子结点，否则必须考虑部分链的对接，以保证删除一个结点后能使剩下的结点仍是一颗二叉排序树。

假设要删除的结点为P，其双亲结点为F，且不失一般性，并设结点P是结点F的左孩子（右孩子情况类似）。如下图所示：（注：下图截至数据结构书中）。

下面分三种情况进行讨论：

（1）若P为叶子节点,删除P后只需修改双亲节点的指针即可;
（2）如果P的左子树为空或者P的右子树为空,此时只需令其左右子树PL，PR成为其双亲结点F的左右子树即可;

（3）若P的左右子树均不为空，如图8.7（a）所示：此时有两种处理方法。

  方法1：首先找到P结点在中序序列中的直接前驱S结点，如图8.7（b）所示，然后将P的左子树改为F的左子树，P的右子树改为S的右子树；

  F->lchild=P->lchild;S->rchild=P->rchild;free(P);结果如图8.7（c）所示：因为P的右结点数值比S的数值大，故不会改变二叉排序树的性质;

 方法2：首先找到P结点在中序序列中的直接前驱S结点，如图8.7（b）所示，然后用S结点的值代替P结点的值，再将S结点删除,原S结点的左子树改为双亲

 结点Q结点的右子树；P->data=S->data;Q->rchild=S->lchild;free(S)。结果如图8.7（d）所示。

具体算法描述如下：

void DelBST(BSTree *t,short key)
{
	BSTNode *p,*f,*s,*q;

	p=*t;
	f=NULL;
	while (p)				//查找关键字为key的待删节点;
	{
		if(p->key==key)		
		{
			break;			
		}
		f=p;				//f指向p节点的双亲节点;

		if(p->key>key)
		{
			p=p->lchild;
		}
		else
		{
			p=p->rchild;
		}
	}

	if(p==NULL)								//如果没有找到直接返回;
	{
		return;
	}
	if(f==NULL)								//如果p是原二叉排序树的根;
	{
		free(p);
		*t=NULL;
		return;
	}

	if(p->lchild==NULL&&p->rchild==NULL)	//如果p没有左右子树;
	{
		if(f->lchild==p)
		{
			f->lchild=NULL;
		}
		else
		{
			f->rchild=NULL;
		}

		free(p);
	}
	else if(p->lchild==NULL&&p->rchild!=NULL) //如果p的左子树为空,右子树不为空;
	{
		if(f->lchild==p)
		{
			f->lchild=p->rchild;   //把p的右子树链接到父亲的左链上;
		}
		else
		{
			f->rchild=p->rchild;	//把p的右子树链接到父亲的右链上;
		}

		free(p);
	}
	else if(p->lchild!=NULL&&p->rchild==NULL) //如果p的左子树不为空,右子树为空;
	{
		if(f->lchild==p)
		{
			f->lchild=p->lchild;   //把p的右子树链接到父亲的左链上;
		}
		else
		{
			f->rchild=p->lchild;	//把p的右子树链接到父亲的右链上;
		}

		free(p);
	}
	else if(p->lchild!=NULL&&p->rchild!=NULL)	//如果p的左右子树都不为空;
	{
		q=p;						
		s=p->lchild;				//s指向p的左节点;
		while (s->rchild)
		{
			q=s;
			s=s->rchild;
		}
		p->key=s->key;				//把s节点的数据赋值给p节点;
		if(p==q)				//说明待删除的p节点的左子节点下没有右结点;
		{
			q->lchild=s->lchild;	//把s节点的左子树链接到q的左节点下;
		}
		else
		{
			q->rchild=s->lchild;	//把s节点的左子树链接到q的右节点下;
		}

		free(s);
	}
}

4.二叉排序树的查找

       由二叉排序树的定义可知,在二叉排序树上进行查找与二分查找类似。即：当二叉排序树不为空时，首先将给定值与根结点的关键值相比较，若相等，则查找成功。否则，将依据给定值和根节点关键值之间的大小关系，分别在左右子树上继续进行查找，其查找过程的算法如下：

BSTree SearchBST(BSTree bst,short key)
{
	if(bst==NULL)
	{
		return NULL;
	}
	if(bst->key==key)
	{
		return bst;
	}
	else if(bst->key>key)
	{
		return SearchBST(bst->lchild,key);
	}
	else 
	{
		return SearchBST(bst->rchild,key);
	}
}

5、二叉排序树的查找分析

        根据二叉排序树的查找算法可以看出，二叉排序树的查找和二分查找类似，和关键字比较次数不超过树的深度，然而二分查找长度n的表判定树是唯一的，而含有n个结点二叉排序树却不唯一。对于含有同样关键字序列的一组结点，结点插入的先后次序不同，所构成的二叉排序树的形态和深度不同。而二叉排序树的平均查找长度ASL与二叉树的形态相关，二叉排序树的各分支越均衡，树的深度越浅，其平均查找长度ASL越小。

        就平均性能而言，二叉排序树上的查找和二分查找相差不大，并且二叉排序树上的插入和删除结点十分方便，无需移动大量的结点。因此，对于需要经常做插入、删除、查找运算的表，宜采用二叉排序树，因此二叉排序树又称为二叉查找树。

6、总结

      上面是我在精读数据结构时，对二叉排序树的一点总结，也参考了相关的书籍，望各位读者多多指教。