对于有序线性表出来说，查找效率非常高，但是对于插入、删除操作，需要对数据进行移动，所以效率就不怎么高了。那么对于这种问题，我们就可以利用二叉查找树来解决了。 二叉查找树也叫二叉搜索树和二叉排序树。顾名思义，就是便于查找的二叉树。二叉查找树不仅类似二分查找法的方式查找数据，同时结合树的链接特性，对于插入和删除操作不需要移动元素，所以插入和删除操作也很高效。
当我们有个关键码序列 {5,3,2,8,7,10,4} ，我们对这个序列构造一个二叉查找树怎么做呢？ 我们首先将第一个元素5作为根结点，然后拿第二个结点3比较根节点5，我们规定新结点比当前结点小的，作为这个结点的左子树，比当前结点大的作为这个结点的右子树，所以3作为5的左子树。 然后第三个元素3从根结点开始比较，比5小，继续和3比较比3小，所以2作为3的左子树。 继续拿第四个元素8和5比较，比5大，那么将8作为5的右子树。 然后依次将后续元素按照如上步骤比较，最终得到的二叉树就是我们的二叉查找树了。 我们可以从上面的二叉查找树得到如下性质：
当它的左子树不为空，那么左子树上面的值都小于当前结点的值当它的右子树不为空，那么右子树上面的值都大于当前结点的值它的左右子树分别都是二叉查找树如果我们在构造二叉查找树的时候实际上就是在排序。我们将这颗二叉树按照中序遍历可以的得到{2,3,4,5,7,8,10}排好序的列表，所以，为啥又叫二叉排序树。关于遍历可以查看二叉树遍历算法。
二叉查找树，插入构建时即是排序，排序就是为了查找效率更高。二叉查找树类似二分查找法，如我们对如下二叉查找树查找为7的结点：
我们先将7和根节点5 比较，比5大，去5的右子节点8比较，7比8小，那么取8的左子节点7比较，7=7，返回true。 代码实现使用Python，语言不重要，重要的是算法逻辑理解，咱们先看下我们的树结点定义：
class TreeNode: def __init__(self, data) -> None: self.data = data # type: int # 数据值 self.parent = -1 # 父级结点，当无父级结点，则表示-1 self.left = None # 左子结点 self.right = None # 右子结点 def __str__(self) -> str: return str(self.data)然后是我们的查找函数：
def search_bst_tree(_tree, value, track_print=False) -> tuple: """ 检索二叉树找到传入value对应值的结点并返回，当树为空时，则返回False和None。如果搜索到结点，则返回True和当前结点。如果没有搜索到结点，则返回False和叶子结点。 :param track_print: 是否打印检索路径 :param _tree: 排序树,每次传入即为当前树的根节点 :type _tree :TreeNode :param value: 搜索的值 :type value :int :return : 返回一个元祖， (bool,node) """ if _tree is None: # 如果树为空，则直接返回False和空 return False, None if track_print: print(_tree.data, end=',') # 仅仅只是为了直观看到搜索路径，打印出每个节点的值 if _tree.data == value: # 如果当前树结点和值相等，则返回True和当前结点 return True, _tree elif _tree.data > value: # 如果当前结点值大于value，则递归当前结点的左子节点 if _tree.left is None: # 如果当前结点无左子节点了，则直接返回False和当前结点 return False, _tree return search_bst_tree(_tree.left, value, track_print) else: # 如果当前结点值小于value，则递归当前结点的右子节点 if _tree.right is None: # 如果当前结点无右子节点了，则直接返回False和当前结点 return False, _tree return search_bst_tree(_tree.right, value, track_print)然后我们写个main来测试一下：
if __name__ == '__main__': a = TreeNode(5) b = TreeNode(3) c = TreeNode(2) d = TreeNode(8) e = TreeNode(7) f = TreeNode(10) g = TreeNode(4) a.left = b a.right = d b.left = c b.right = g d.left = e d.right = f print('前序遍历二叉查找树：', end='') pre_order_traverse(a) print('\b\n', end='') print('中序遍历二叉查找树：', end='') in_order_traverse(a) print('\b\n', end='') search_key = 7 # 检索值 print('开始搜索%s路径为:' % search_key, end='') is_exist, node = search_bst_tree(a, search_key, track_print=True) print('\b\n', end='') print('数据存在 ' if is_exist else '数据不存在', node.data if node.data else '')运行代码我们可以得到如下结果：
前序遍历二叉查找树：5,3,2,4,8,7,10 中序遍历二叉查找树：2,3,4,5,7,8,10 开始搜索7路径为:5,8,7 数据存在 7关于前后序遍历二叉树，可以查看我另外一篇博客来得到代码，在文章末尾也会贴上完整代码。
二叉查找树插入结点就是我们上面介绍的构建流程，就是元素进行比较，小作为左子树，大作为右子树。 代码如下：
def insert_bst_node(_tree, _node) -> bool: """ 二叉查找树，插入结点。 当树中没有对应结点，那么插入，并返回True。如果树中已经存在了当前插入结点，那么返回False。 :param _tree: 排序树 :type _tree :TreeNode :param _node: 需要插入的结点 :type _node :TreeNode """ if not _tree: raise Exception("树不能为空") # 查找传入的当前结点是否在当前树中，返回一个元祖，元素1为是否存在，元素2为结点，当结点不存在，则返回检索到最后的叶子结点 is_exist, leaf_node = search_bst_tree(_tree, _node.data) if is_exist: # 如果存在，则返回False return False else: # 如果不存在，则插入当前结点到检索到的叶子结点 if leaf_node.data > _node.data: # 如果插入结点小于检索的叶子结点，则将插入结点作为叶子结点的左子节点 leaf_node.left = _node _node.parent = leaf_node # 将插入结点的父级结点指向更新 else: # 如果插入结点大于检索的叶子结点，则将插入结点作为叶子结点的右子节点 leaf_node.right = _node _node.parent = leaf_node # 将插入结点的父级结点指向更新 return True写个main方法验证一下：
if __name__ == '__main__': trees = [5, 3, 2, 8, 7, 10, 4] nodes = [TreeNode(t) for t in trees] # 待插入结点序列 print("对关键码序列：%s构建二叉查找树" % str([str(i) for i in nodes])) bst_tree = nodes.pop(0) # 取第一个序列的第一个元素作为一个二叉查找树的根 for node in nodes: # 循环插入节点到bst_tree insert_result = insert_bst_node(bst_tree, node) if not insert_result: # 已经存在，插入失败 print('结点%s已经在树中存在' % node.data) break print('前序遍历二叉查找树：', end='') pre_order_traverse(bst_tree) print('\b\n' * 1, end='') print('中序遍历二叉查找树：', end='') in_order_traverse(bst_tree) print('\b\n' * 1, end='')可以得到如下结果：
对关键码序列：['5', '3', '2', '8', '7', '10', '4']构建二叉查找树 前序遍历二叉查找树：5,3,2,4,8,7,10 中序遍历二叉查找树：2,3,4,5,7,8,10我们拿下面的二叉树做例子 删除有四种情况，第一种：删除叶子结点。
如果删除的是叶子结点，我们可以直接删除即可，如我们删除40结点、58结点都不会对结构产生影响：
第二种情况，删除只有左子树的结点。我们只需要将删除结点的左子树移动到删除结点位置即可如我们将43结点删除：
第三种情况：删除只有右子树的结点。我们也和删除左子树的方式一样，将删除结点的右子树结点移动到删除结点位置：
最后一种情况就是删除既有左子树又有右子树的结点，比如我们删除下面的树的结点47。 我们没有办法像删除只有一边子树那样直接将子节点移动到删除结点位置这么简单了。我们从47的左右子节点中发现43结点和53结点都可以作为47的替代： 我们将上面删除之前的树按照中序遍历出来序列为{35,38,40,43,47,53,58,68,70,72,88}，可以发现43和53正好是47结点的前驱和后继。也就是说，删除结点的左子树的最大值或者右子树的最小值都可以作为删除结点的替代。
结合上面提出的4种情况，代码实现如下：
def delete_bst_node(_tree, value) -> bool: """ 删除二叉查找树结点，当value对应结点存在，则删除并返回True，否则返回False。 当删除结点左右子树不为空，始终使用左子树最大结点作为替代。 :param _tree: 排序树,每次传入即为当前树的根节点 :type _tree :TreeNode :param value: 搜索的值 :type value :int """ if _tree is None: # 如果树为空，则直接返回False return False if _tree.data == value: # 如果当前树结点和值相等，则删除当前结点，并返回True do_delete(_tree) return True elif _tree.data > value: # 如果当前结点值大于value，则递归当前结点的左子节点 if _tree.left is None: # 如果当前结点无左子节点了，则直接返回False return False return delete_bst_node(_tree.left, value) else: # 如果当前结点值小于value，则递归当前结点的右子节点 if _tree.right is None: # 如果当前结点无右子节点了，则直接返回False return False return delete_bst_node(_tree.right, value) def do_delete(_node) -> bool: """ 执行结点删除操作。 :param _node: 需要删除的结点 """ if not _node: return False if _node.left and _node.right: # 如果左右子结点都存在 # 找出当前结点左子结点最大值,即：左子树的最右叶子结点 replace_node = _node.left # 定义左子树最右结点的父节点 while replace_node.right: replace_node = replace_node.right # 将删除结点的data替换成删除结点最大左子结点的data _node.data = replace_node.data # 将找出的最大结点的左子结点作为它父节点的右子结点 if replace_node.left is None and replace_node.right is None: _parent = replace_node.parent if _node.data > _parent.data: _parent.right = None # 删除父节点的右子节点 elif replace_node.right is None: if replace_node.data > replace_node.parent.left.data: replace_node.parent.right = replace_node.left else: replace_node.parent.left = replace_node.left elif _node.left is None and _node.right is None: _parent = _node.parent if _parent.data > _node.data: # 如果父节点比当前结点大，则证明删除结点是父节点的左子节点 _parent.left = None # 删除父节点的左子节点 else: _parent.right = None # 删除父节点的右子节点 elif _node.left is None: # 当前删除结点指针不变，值需要将值替换成右子节点的值，然后清空右子节点的指针 _node.data = _node.right.data _node.right = None elif _node.right is None: # 当前删除结点指针不变，值需要将值替换成左子节点的值，然后清空左子节点的指针 _node.data = _node.left.data _node.left = None