93二叉排序树 1、瘫心索方法中二分检索法具有最 高的查嶽率树但趄只匙j顺酯结耷越 纯索业伊蛟锯啥明带束其定义为:二叉 排序树或者是空树,或者是满定如下性质的二叉树 ①若它的左子树非空,则左子树上所有结点的值均 小于根结点的值 ②若它的右子树非空,则右子树上所有结点的值均 大于根结点的值 ③左、右子树本身又各是一棵二叉排序树。 上述性质简称二叉排序树性质(BST性质),故 二叉排序树实际上是满足BST性质的二叉树9.3 二叉排序树 在线性表的三种检索方法中二分检索法具有最 高的查找效率，但是它只适合于顺序存储结构，这 给查找表中数据的增、删带来不便。 1、二叉排序树的定义 二叉排序树(Binary Sort Tree)又称二叉查找 (搜索)树(Binary Search Tree)。其定义为：二叉 排序树或者是空树，或者是满足如下性质的二叉树 ： ①若它的左子树非空，则左子树上所有结点的值均 小于根结点的值； ②若它的右子树非空，则右子树上所有结点的值均 大于根结点的值； ③左、右子树本身又各是一棵二叉排序树。 上述性质简称二叉排序树性质(BST性质)，故 二叉排序树实际上是满足BST性质的二叉树