二叉排序树

前言

二叉排序树，又称为二分查找树，它或者是一颗空树，或者具有如下性质
1.若它的左子树不为空，则左子树上所有结点的值均小于根结点值
2.若它的右子树不为空，则右子树上所有结点的值均小于根结点值
3.它的左右子树也分别为二叉排序树

二叉排序树查找操作

typedef struct BiTNode
{
	int data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


//递归查找二叉排序树中是否存在key
//f指向T的双亲，初始值为NULL
//若查找成功，则p指向该节点，并返回true
//若查找失败，则p指向查找路径上访问的最后一个结点，并返回FALSE
Status SearchBST(BiTree T,int key,BiTree f,BiTree *p)
{
	if(!T)     //查找不成功
	{
		*p=f;
		return FALSE;
	}

	else if(key==T->data) //查找成功
	{
		*p=T;
		return TRUE;
	}
	else if(key>T->data){         //在右子树中递归查找
		return SearchBST(T->rchild,key,T,p);
	}
	else if(key<T->data)          //在左子树中递归查找
		return SearchBST(T->lchild,key,T,p);
}

我们来看看它的过程是如何运行的，比如现在要查找93，显然初始化为SearchBST(T,93,NULL,p),因为93>62，所以递归执行SearchBST(T-rchild,93,T,p),即SearchBST(88,93,62,P)这里用结点data值表示结点，又93>88,继续SearchBST(99,93,88,P)，又93<99，SearchBST(93,93,99,P)，所以93==93，得到最终p=T=93，f=99，查找成功。
可以发现二叉排序树的查找算法如此精妙而又优雅

二叉排序树的插入操作

插入操作是基于查找操作的，也就是如果该二叉树为空，则新插入点为根结点，如果不为空，在先查找是否存在此元素，存在返回FALSE，否则在查找路径上的最后一个结点，通过比较插入到左孩子还是右孩子，最终返回TRUE

Status InsertBST(BiTree *T,int key)
{
	BiTree p,s;
	if(!SearchBST(T,key,NULL,&p)) //查找不成功
	{
		s=(BiTree)malloc(sizeof(BiTNode));
		 s->data=key;
		 s->lchild=s->rchild=NULL;
		 if(!p)                    //插入s为新的根结点
		 	*T=s;
		 else if(key<s-data)      //插入s为左孩子
		 	p->lchild=s;
		 else                     //插入s为右孩子
		 	p->rchild=s;
		 return TRUE;
	}
	else                       //树中已存在此关键字，则不插入
		return FALSE;
}

二叉排序树的删除操作

删除操作需要考虑三种情况，因为删除之后要保证还是一颗二叉排序树。如图

一：删除叶子结点，这对这个二叉树来说并无影响，所以不移动其它元素
二：删除只含有左子树或者右子树的二叉排序树，因为根据二叉排序树的特点，很明显只要将它的左子树或右子树全部移动到它双亲的左子树或右子树就行了
三：删除既有左子树又有右子树的结点，我们可以通过它的中序遍历，也就是让它的直接前驱或者直接后继来替换它的位置，然后直接后继在分三种情况，直至只有一个孩子或者无孩子来替换

Status DeleteBST(BiTree *T,int key) //找到待删结点
{
	if(!*T)
		return FALSE;
	else
	{
		if(key==(*T)->data)
			return Delete(T);
		else if(key<(*T)->data)
			return DeleteBST(&(*T)->lchild,key);
		else
			return DeleteBST(&(*T)->rchild,key);
	}
}


//从二叉树中删除结点p，并重接它的左或右子树
Status Delete(BiTree *p)
{
	BiTree q,s;
	if((*p)->rchild==NULL)  //右子树空则重接它的左子树
	{
		q=*p;
		*p=(*p)->lchild;
		free(q);
	}
	else if((*p)->lchild==NULL) //左子树空则重接它的右子树
	{
		q=*p;
		*p=(*p)->rchild;
		free(q);
	}
	else{         //左右子树均不为空
		q=*p;
		s=(*p)->lchild;
		while(s->lchild) //找到待删结点的前驱
		{
			q=s;
			s=s->rchild;
		}
		(*p)->data=s->data;
		if(q!=*p)        //重接q的右子树
			q->rchild=s->lchild;
		else             //重接q的左子树
			q->lchild=s->lchild;
		free(s);
	}
	return TRUE;
}

总结

二叉排序树是以链式结构进行存储，所以在插入和删除元素上高效，，但是查找上走的是从根路径到结点的路径，其比较次数与数的层数有关如果该数是一颗斜数，那么查找就会比较很多次，如果该树是一颗完全二叉树，那么比较次数就最优，此时时间复杂度为O(logn),但是平均来说时间复杂度为O(n)