二叉查找树（BST：Binary Search Tree）

大家好，欢迎来到IT知识分享网。

二叉查找树（BST：Binary Search Tree）属于二叉树的一种，它提高了二叉树节点的查找效率。一般具有以下几个性质：

1. 若左子树不空，则左子树上所有节点的值均小于它的根节点的值。
2. 若右子树不空，则右子树上所有节点的值均大于它的根节点的值。
3. 左右子树也分别为二叉查找树。
4. 没有键值相等的节点

列举一个二叉树，如图1。

图1 二叉查找树

从查找效率来说，如果二叉查找树的所有非叶子节点的左右子树的节点数目保持差不多，此时，二叉查找树的查找性能与二分查找接近。对于增加或者删除节点，二分查找的内部空间是连续的，而二叉查找树的树结构则不需要移动大段的内存数据。

二分查找是一种高效的查找方法。在查找前使用线性表已经排好了序，充分利用线性表的位置关系，使用分治策略。查找如下线性表总的节点20过程如下图2。

二分查找

二叉查找树可以表示按顺序排列的数据集合，所以二叉查找树也被称为二叉排序树。如图3。

图3 二叉查找树又被称为二叉排序树

一般情况下，二分查找效率就很高。但是，频繁增加、删除的线性表中使用二分查找，效率是非常低的。因为顺序表的修改操作效率很低，二分查找的高效是基于顺序表的位置索引来进行比较的。为了支持频繁的修改，可以选择链表数据结构。单链表的查找效率又很低，为了解决这些问题，二叉查找树（BST）就诞生了。

二叉查找树（BST）的查询操作。从根节点开始查找，待查找的值是否与根节点的值相同，若相同则返回True；否则，判断待寻找的值是否比根节点的值小，若是则进入根节点左子树进行查找，否则进入右子树进行查找。该操作使用递归实现。

//C语言实现
BTree SearchBST(BTree Tree,KeyType key){
    //如果递归过程中 Tree 为空，则查找失败，返回NULL；否则查找成功，返回指向该关键字的指针
    if (!Tree || key == Tree->data) {
        return Tree;
    }else if(key < Tree->data){
        //递归遍历其左孩子
        return SearchBST(Tree->lchild, key);
    }else{
        //递归遍历其右孩子
        return SearchBST(Tree->rchild, key);
    }
}

//python实现
def query(self, root, val):
		'''二叉搜索树查询操作'''
		if root == None:
			return False
		if root.val == val:
			return True
		elif val < root.val:
			return self.query(root.left, val)
		elif val > root.val:
			return self.query(root.right, val)