|
当用线性表作为表的组织形式时可以有三种查找法其中以二分查找效率最高但由于二分查找要求表中结点按关键字有序且不能用链表作存储结构因此当表的插入或删除操作频繁时为维护表的有序性势必要移动表中很多结点这种由移动结点引起的额外时间开销就会抵消二分查找的优点也就是说二分查找只适用于静态查找表若要对动态查找表进行高效率的查找可采用下面介绍的几种特殊的二叉树或树作为表的组织形式不妨将它们统称为树表下面将分别讨论在这些树表上进行查找和修改操作的方法 二叉排序树 二叉排序树的定义 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)其定义为二叉排序树或者是空树或者是满足 如下性质的二叉树 ①若它的左子树非空则左子树上所有结点的值均小于根结点的值; ②若它的右子树非空则右子树上所有结点的值均大于根结点的值; ③左右子树本身又各是一棵二叉排序树 上述性质简称二叉排序树性质(BST性质)故二叉排序树实际上是满足BST性质的二叉树 二叉排序树的特点 由BST性质可得 () 二叉排序树中任一结点x其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字 () 二叉排序树中各结点关键字是惟一的 注意 实际应用中不能保证被查找的数据集中各元素的关键字互不相同所以可将二叉排序树定义中BST性质()里的小于改为大于等于或将BST性质()里的大于改为小于等于甚至可同时修改这两个性质 () 按中序遍历该树所得到的中序序列是一个递增有序序列 【例】下图所示的两棵树均是二叉排序树它们的中序序列均为有序序列 二叉排序树的存储结构 typedef int KeyType; //假定关键字类型为整数 typedef struct node { //结点类型 KeyType key; //关键字项 InfoType otherinfo; //其它数据域InfoType视应用情况而定下面不处理它 struct node *lchild*rchild; //左右孩子指针 } BSTNode; typedef BSTNode *BSTree; //BSTree是二叉排序树的类型 |
