二叉排序树
1、二叉排序树定义与描述：
二叉排序树又称为二叉查找树，它是一种特殊的二叉树。
其定义为:二叉树排序树或者是一棵空树， 或者是具有如”下性质的二叉树:
(1)若它的左子树非空，则左子树.上所有结点的值均小于根结点的值;
(2)若它的右子树非空，则右子树上所有结点的值均大于(或大于等于)根结点的值;
(3)它的左右子树也分别为二叉排序树。
这是一个递归定义。注意只要结点之间具有可比性即可，如下图(a)中的数字值间的比较，图(b)中是用单词字符的ASCII码间的比较。

 

 结构描述：

typedef struct node
{KeyType key;/*关键字的值*/
struct node *lchild,*rchild;/* 左右指针*/
}BSTNode, *BSTree;
2.二叉排序树的创建
假若给定一个元素序列，我们可以利用逐个插入结点算法创建一棵二 叉排序树。因此，实现建立二叉排序树包括创建树与插入结点两个算法。
[算法思想]:
首先，将二叉树序树初始化为一棵空树，然后逐个读入元素，每读入一个元素，就建立一个新的结点，并插
入到当前已生成的二叉排序树中，即通过多次调用二叉排序树的插入新结点的算法实现，注意插入时比较结点
的顺序始终是从二叉排序树的根结点开始。
①二叉排序树的插入
已知一个关键字值为key的结点s，若将其插入到二叉排序树中，只要保证插入后仍符合二叉排序树的定义即可。
[算法思想]:
1)若二叉排序树是空树，则key成为二叉排序树的根;
2)若二叉排序树非空，则将key与二叉排序树的根进行比较:
a)如果key的值等于根结点的值，则停止插入;
b)如果key的值小于根结点的值，则将key插入左子树;
c)如果key的值大于根结点的值，则将key插入右子树。
例如，设关键字的输入顺序为: 45，24，53，12，28，90，按上述算法生成的二叉排序树的过程如下图所示。

 

 

 

 

实现代码：
void InsertBST(BSTree *bst, KeyType key)
/*若在二叉排序树bst中不存在关键字等于key的元素，插入该元素*/
{ BiTree s;
if (*bst==NULL)/*递归结束条件*/
s=(BSTree)malloc(sizeof(BSTNode));/*申请新的结点s*/
s-> key=key;
s->lchild=NULL; s->rchild=NULL;
*bst=s;
else if (key < (*bst)->key)
InsertBST(&((*bst)->lchild), key);/*将s插入左子树*/
else
if (key > (*bst)->key)
InsertBST(&((*bst)->rchild), key); /*将s插入右子树*/
}
void CreateBST(BSTree *bst)
/*从键盘输入元素的值，创建相应的二叉排序树*/
{ KeyType key;
*bst=NULL;
scanf("%d", &key);
while (key!=ENDKEY) /*EDNKEY 为自定义常量*/
InsertBST (bst, key) ;
/*在二叉排序树bst中插入结点key*/
scanf'"%d", &key);
}
}
假设共有n个元素，要插入n个结点需要n次插入操作，而插入一个结点的算法时间复杂度为0(log2n)，因此创建二叉排序树的算法时间复杂度为O(nlog2n)。
如果输入顺序为24， 53， 90， 12， 28，45，则生成的二叉排序树如下图所示:

 

 

3.二叉排序树的查找
二叉排序树的特性:根据二叉排序树的定义(左子树小于根结点，右子树大于根结点),根据二叉树中序遍历的定义(先中序遍历左子树，访问根结点，再中序遍历右子树)，可以得出二叉排序树的一一个重要性质，
中序遍历一个二叉排序树，可以得到一个递增有序序列。
如图所示的二叉树就是一棵二叉排序树，若中序遍历下图的二叉排序树，则可得到一个递增有序序列为:1，2, 3，4，5，6，7 ,8，9。

 

 二叉排序树查找的实现方法:
因为二叉排序树可看作是一个有序表，所以在二叉排序树上进行查找，和折半查找类似，也是一个逐步缩小查找范围的过程。

首先将待查关键字k与根结点关键字t进行比较，如果:.
1) k= t: 则返回根结点地址;
2) k<t: 则进一步查左子树;
3) k>t: 则进一步查右子树。

根据二叉排序树的定义，在二叉排序树结构上查找可以用递归与非递归两种实现算法。
1.二叉排序树查找的递归算法
BSTree SearchBST(BSTree bst, KeyType key)
/*在根指针bst所指二叉排序树中，递归查找某关键字等于key的元素，若查找成功，返回
指向该元素结点指针，否则返回空指针*/
if (!bst) retum NULL;
else if (bst->key == key) retun bst;/*查找成功*/
else
if (bst->key> key)
retum SearchBST(bst->lchild, key);/*在左子树继续查找*/
else
returm SearchBST(bst->rchild, key);/*在右子树继续查找*/
}
2.二叉排序树查找的非递归算法
根据二叉排序树定义，其查找也可以用循环方式直接实现。
二叉排序树的非递归查找过程如下:
BSTree SearchBST(BSTree bst, KeyType key)
/*在根指针bst所指二叉排序树bst.上，查找关键字等于key的结点，若查找成功，返回指向该元素结点指针，否则返回空指针*/
{ BSTree q;
q=bst;
while(q)
{if(q->key= key)
returnq; /* 查找成功*/
if (q->key> key)(
q=q->lchild; /* 在左子树中查找*/
else q=q->rchild; .
/*在右子树中查找*/
return NULL; /*查找失败*/
}/* SearchBST*/