首页 > 代码库 > 算法学习之查找算法：动态查找表（1）二叉排序树
算法学习之查找算法：动态查找表（1）二叉排序树
引言：
动态查找表的特点是，在表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
1、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。
2、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
3、它的左、右子树也分别为二叉排序树。
<一>二叉排序树的查找：
二叉排序树又称二叉查找树，查找过程是先将给定值和根结点的关键字比较，若相等，则查找成功，否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找。通常，可取二叉链表作为二叉排序树的存储结构。举例如下：
45
/ \ 以查找关键字100为例。
12 53 1、因为100 > 45，所以查找以45为根的右子树。此时右子树不空。
/ \ \ 2、又100 > 53，所以继续查找以53为根的右子树。
3 37 100 3、53为根的右子树的关键字100，与查找关键字相等，查找成功。
/ / 返回关键字等于100的数据结点的指针。
24 61
\
90
/
78
从上面的分析可以看出，若将查找过程翻译成代码如下：
BiTree SearchBST(BiTree, T, KeyType key)
{
//在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素
//若查找成功，则返回指向该数据元素结点的指针，否则返回空指针
if((!T)||EQ(key, T->data.key)) return(T); //查找结束
else if LT(key, T->data.key) return (SearchBST(T->lchild, key)); //在左子树中继续查找
else return(SearchBST(T->rchild, key)); //在右子树中继续查找
}
<二>二叉排序树的插入
二叉排序树是一种动态树表，特点是：树的结构不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。因此改写上面给出的查找算法，在查找不成功时返回插入位置，以便进行二叉排序树的插入。
二叉排序树插入操作代码实现：
/*********************************************************************
Author：李冰 date：2014-9-25
Email：libing1209@126.com
*********************************************************************/
typedef int ElemType;
typedef struct node{
ElemType key;
struct node *Left, *Right;
}BSTNode, *SearchTree;
SearchTree Insert(ElemType X, SearchTree T)
{
if(T == NULL){
T = (SearchTree)malloc(sizeof(BSTNode)); //创建并返回一个节点树
if(T == NULL)
printf("Out of space!!");
else
{
T->key = X;
T->Left = T->Right = NULL;
}
}else if(X < T->key){
T->Left = Insert(X, T->Left);
}else if(X > T->key){
T->Right = Insert(X, T->Right);
}
return T;
}
以关键字序列为{45, 24, 53, 45, 12, 24, 90}为例，生成二叉排序树的过程如下：
○ 45 45 45 45 45
a b / / \ / \ / \
24 24 53 24 53 24 53
c d / / \
12 12 90
e f
中序遍历二叉排序树可得到一个关键字有序序列。一个有序序列可通过构造一颗二叉排序树而变成一个有序序列，构造树的过程即为无序序列进行排序的过程。而且在插入的过程中，每次插入的新结点都是二叉排序树上新的叶子结点，则在进行插入操作时，不必移动其他结点，仅需改动某个结点的指针，由空变为非空即可。相当于在一个有序序列上插入一个记录而不需要移动其记录。二叉排序树既拥有类似折半查找的特性，又采用了链表作存储结构，因此是动态查找表的一种适宜表示。
测试如下：
/*********************************************************************
Author：李冰 date：2014-9-25
Email：libing1209@126.com
*********************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
void InOrder(SearchTree T)
{
if(T){
InOrder(T->Left);
printf("%d ", T->key);
InOrder(T->Right);
}
}
int main(int argc, char **argv)
{
SearchTree T = NULL;
int array[] = {45, 24, 53, 45, 12, 24, 90};
for(int i = 0; i < 7; i++){
T = Insert(array[i], T);
}
InOrder(T);
return 0;
}
输出结果为：12 24 45 53 90
<三>二叉排序树的删除
对于二叉排序树，删去树上一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后依旧保持二叉排序树的特性即可。
删除结点分为3种情况：
1、如果节点是一片树叶，可直接删除。
2、如果节点有一个儿子，则该节点可在其父节点调整指针绕过该节点后被删除。
3、如果节点有两个儿子，则用所删除结点的右子树的最小数据代替该节点的数据并递归地删除那个节点。
通过上面的删除节点，能够保证删除节点后的二叉排序树仍然是二叉排序树，中序遍历该节点，各节点的顺序不变。
删除操作C语言实现如下
/*********************************************************************
Author：李冰 date：2014-9-25
Email：libing1209@126.com
*********************************************************************/
SearchTree FindMin(SearchTree T)
{
if(T == NULL)
return NULL;
else if(T->Left == NULL)
return T;
else
return FindMin(T->Left);
}
SearchTree Delete(ElemType X, SearchTree T)
{
SearchTree TmpCell;
if(T == NULL)
printf("Element not found");
else if(X < T->key)
T->Left = Delete(X, T->Left);
else if(X > T->key)
T->Right = Delete(X, T->Right);
else if(T->Left && T->Right) //找到了要被删除的节点，两个孩子
{
TmpCell = FindMin(T->Right);
T->key = TmpCell->key;
T->Right = Delete(T->key, T->Right);
}else{ //一个孩子或没有孩子
TmpCell = T;
if(T->Left == NULL)
T = T->Right;
else if(T->Right == NULL)
T = T->Left;
free(TmpCell);
}
return T;
}
查找性能：二叉排序树的平均查找长度和logn是等数量级别的。
算法学习之查找算法：动态查找表（1）二叉排序树