二叉排序树

二叉排序树(Binary Search Tree)又称为二叉查找树。他或是一颗空树，或者是具有下列性质的二叉树。

• 若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左右子树也分别为二叉排序树。

二叉排序树的查找操作

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef struct BitNode{
	int data;
	struct BitNode *lchild, *rchild;
}BitNode, *BitTree;
Status SearchBST(BitTree T, int key, BitTree f, BitTree *p)
{
	/*
	指针f指向T的双亲，函数第一次调用时传入 f = NULL
	二级指针p 用于指向找到的key值 修改传入的BitTree(一级指针)的指向
	*/
	if(!T)
	{
		*p = f;
		return FALSE;
	}	
	else if(T->data == key)
	{
		*p = T;
		return TRUE;
	}
	else if(key < T->data)
	{
		return SearchBST(T->lchild, key, T, p);
	}
	else 
	{
		return SearchBST(T->rchild, key, T, p);
	}
}

二叉排序树的插入操作

当二叉排序树T中不存在关键字等于key的数据元素时，插入key并且返回TRUE， 否则返回FALSE。

Status InsertBST(BitTree *T, int key)
{
	BitTree p, s;
	if(!SearchBST(*T, key, NULL, &p))
	{
		//没有找打key元素则插入新的结点
		s = (BitTree)malloc(sizeof(BitNode));
		s->data = key;
		s->lchild = s->rchild = NULL;
		if(!p)
		{
			*T = s;
		}
		else if(key < p->data)
		{
			p->lchild = s;
		}
		else 
		{
			p->rchild = s;
		}
		return TRUE;
	}
	else
	{
		//已经有相同值结点在树种，插入失败返回FALSE
		return FALSE;
	}
}

二叉排序树的删除操作

如果待删除结点只有左子树，那么就把左子树提到待删除结点的位置；如果待删除结点只有右子树，那么就把右子树提到待删除结点的位置。倘若左右子树均无，则直接删除结顶即可。最复杂的情况左右子树都有，这时候要仔细考虑怎么删这个结点才可以维持二叉排序树的结构。我们的步骤是找到待删除结点在中序遍历（LDR）中的直接前驱或者后继，用这个结点代替待删除结点不会导致结构被破坏。

Status DeleteBST(BitTree *T, int key)
{
	if(!*T)
	{
		// *T = NULL 为空树，则返回FALSE 不存在关键字等于key的数据元素
		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);
		}
	}
}
Status Delete(BitTree *P)
{
	BitTree 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->rchild)
		{
            /*直到右子树的最深右结点*/
			q = s;
			s = s->rchild;
		}
		(*p)->data = s->data;
        /*   
        		
        		此时找到了s即为 待删除结点p的直接前驱，而q则为s的双亲
        		q -----------> s ---------->  s->rchild(NULL)   
        		不理解的话一定要中序遍历画个图，然后这个左拐向右的操作画图，画出来的结果肯定会发现s即为p的之间前驱
        */
		if(q != *p)
		{
            /*见下图*/
			q->rchild = s->lchild;//重接q的右子树
		}
		else
		{
			q->lchild = s->lchild;//重接q的左子树
		}
		free(s);
	}
	return TRUE;
}