判断二叉树是否是二叉排序树 查找 - 树上的查找 - 二叉排序树（一）

查找 - 树上的查找 - 二叉排序树（一）  

　　当用线性表作为表的组织形式时 可以有三种查找法 其中以二分查找效率最高 但由于二分查找要求表中结点按关键字有序 且不能用链表作存储结构 因此 当表的插入或删除操作频繁时 为维护表的有序性 势必要移动表中很多结点 这种由移动结点引起的额外时间开销 就会抵消二分查找的优点 也就是说 二分查找只适用于静态查找表 若要对动态查找表进行高效率的查找 可采用下面介绍的几种特殊的二叉树或树作为表的组织形式 不妨将它们统称为树表 下面将分别讨论在这些树表上进行查找和修改操作的方法

　　二叉排序树

　　 二叉排序树的定义

　　二叉排序树(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是二叉排序树的类型