查找——二叉排序树（一）

想要了解更多的动态查找可以看看前面的文章

1.二叉排序树

二叉排序树或者是一棵空树;或者是具有下列性质的二叉树:

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值;

• 若它的右子树不空，则子树上所有结点的值均大于它的根结点的值;

• 它的左、右子树也分别是二叉排序树。

查找过程中，当二叉排序树不空时，首先将给定值与根结点的关键字比较，若相等查找成功;若给定值小于根结点的关键字，则在左子树上继续查找，否则，在右子树上继续查找。

下图为二叉树：

• 二叉排序树递归算法：

BiTree SearchBST(BiTreeT, KeyTepykey){

if( (!T)EQ(key, T->data.key)) return(T);//查找结束

else if LT(key,T->data.key)

return(SearchBST(T->Ichild,key));//在左子树继续查找

else return(SearchBST(T->rchildkey));//在右子树继续查找

}// SearchBST

• 查找不成功返回插入位置

Status SearchBSTBiTreeTKeyTepy keyBiTreefBiTree&p){/*在根指针 T 所指二叉排序树中递归地查找其关键字等于 kev 的数据元素，若查找成功，则指针 p 指向该数据元素结点，并返回 TRUE，否则指针 p 指向查找路径上访问的最后一个结点并返回 FALSE，指针 f 指向 T 的双亲，其初始调用值为 NULL*/

if(!T) { P=f; return FALSE;}//查找不成功

else if EQ(Key,T->data.key) {

p=T; return TRUE;

}//查找成功

else if LT(Key,T->data.key)

return SearchBST(T->lchild,key,T,p);//在左子树继续查找

else return SearchBST(T->rchild,key,T,p);//在右子树继续查找

}// SearchBST

• 二叉排序树上插入算法

‍

Status Insert BST(BiTree &TElemTypee){

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

if(!SearchBST(Te.key,NULL,p){(查找不成功)

s=(BiTree)malloc(sizeof(BiTNode));(申请新的空间构成新结点)

s->data=e;

s->lchild= s->rchild = NULL;

if(!p)T=s;(若为空树，新结点为根结点)

else if LT(e.key,p->data.key)p->lchild=s;(新结点值小于当前值,插入点*s 为左孩子)

else p->rchild=s;(新结点值大于当前值,插入点*s 为右孩子)

return TRUE;

else return FALSE;//树中已有和关键字相同的结点,不再插入

}// Insert BST