树表的查找

树表的查找

顺序查找、二分(折半)查找和索引查找都是静态查找表，其中二分查找的效率最高。

静态查找表的缺点是当表的插入或删除操作频繁时,为维护表的有序性，需要移动表中很多记录。

这种由移动记录引起的额外时间开销，就会抵消二分查找的优点（二分查找和分块查找只适用于静态查找表）。

若要对动态查找表进行高效率的查找，可以使用树表。

以二叉树或树作为表的组织形式，称为树表。

一、二叉排序树

 二叉排序树（简称BST）又称二叉查找（搜索）树，其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：

（1）若它的左子树非空，则左子树上所有记录的值均小于根记录的值；

（2）若它的右子树非空,则右子树上所有记录的值均大于根记录的值；

（3）左、右子树本身又各是一棵二叉排序树。

在讨论二叉排序树上的运算之前,定义其节点的类型如下：

      typedef struct node        //记录类型
   { KeyType key;            //关键字项
    InfoType data;          //其他数据域
    struct node *lchild,*rchild; //左右孩子指针

   } BSTNode;

1. 二叉排序树上的查找

因为二叉排序树可看做是一个有序表，所以在二叉排序树上进行查找，和二分查找类似，也是一个逐步缩小查找范围的过程。

递归查找算法SearchBST()如下（在二叉排序树bt上查找关键字为k的记录,成功时返回该节点指针，否则返回NULL）：

   BSTNode *SearchBST(BSTNode *bt,KeyType k)
 {  if (bt==NULL || bt->key==k)      //递归终结条件
       return bt;
    if (k<bt->key)
    　 return SearchBST(bt->lchild,k); //在左子树中递归查找
    else
    　 return SearchBST(bt->rchild,k); //在右子树中递归查找

 }

也可以采用如下非递归算法：

BSTNode *SearchBST1(BSTNode *bt,KeyType k)