二叉查找树是一种特殊的二叉树，任意一个节点，右子树中的所有的值都比节点本身大，左子树中所有的值都比节点本身的值要小。

二叉查找树

使用二叉查找树来进行数据的插入、查找、删除的效率是很高的。整体上来体会，由于是二叉树的结构，所以最直观的给人的体会就是查找数据，速度会很快。

一棵二叉查找树.png

二叉查找树的插入

向一棵 普通 的二叉查找树中插入一个数据，这个数据肯定是插入之后作为了 叶子节点 的。从根节点开始，每次都比较当前的节点与要插入节点的值的大小关系，如果当前节点的值大于要插入的节点的值，就遍历当前节点的左子树继续找位置，反之遍历右子树。找到最终的位置插入值。比如，我们向已知的一棵二叉查找树插入一个值：

插入节点21到已有的二叉查找树中.png

二叉查找树的查询

查询操作跟插入操作基本一样，都是通过对二叉树的层层比较来找到需要查找的值。

查找节点值为21的节点.png

二叉查找树的删除

删除节点的操作是最复杂的操作，随着删除的节点的位置不同，可以分为几种不同的情况来进行删除。

• 1. 删除的是叶子节点

被删除的是叶子节点.png

被删除的如果是叶子节点的话，那么只需要把该叶子节点的父节点中指向该被删除节点的指针（左或者右）置空就可以了。

• 2. 删除的节点只有左子树或者只有右子树

被删除的节点只含有一棵子树.png

这种情况，我们只需要将该节点删除，并且用它的子树来代替它的位置“取而代之”即可。

• 3. 删除的节点含有左子树和右子树

被删除的节点含有左右子树.png

这种情况下，我们需要遍历该节点的右子树，找到右子树中值最小的节点。该节点一定是右子树中最“靠左”的节点。这个最靠左的节点一定没有左子树了，如果有左子树的话它也就不是最小值的节点了。

只有找到这个点，并且用这个点取代该要被删除节点，才能使这个节点呗替换掉了之后，该节点的左子树中的值全都小于它，右子树中的所有值全都大于它。

我们以15这个节点为例，删掉15这个节点之后，我们找到最靠左的节点，就是16这个节点，我们用16这个15的右子树中最小的节点的值替代15这个节点的值，然后将16的父节点18的左子节点置空，这样就完成了15节点的删除工作。

删除15节点.png

删除后，先序遍历二叉树的话，结果将会是：25 => 16 => 10 => 18 => 21 => 28 => 30（后面程序中会有验证）

算法实现

# -*- coding: utf-8 -*-
# @Time    : 2019-03-28 16:06
# @Author  : Jaedong
# @Version : 3.6
# @File    : BinarySearchTree.py
# @Software: PyCharm

# 引入的上一篇文章中的二叉树查找相关，方便打印
import TraversingBinaryTree

# 节点的数据结构
class Node:
    value = -1
    leftNode = None
    rightNode = None

    def __init__(self, value, leftNode, rightNode):
        self.value = value
        self.leftNode = leftNode
        self.rightNode = rightNode

# 插入节点
def insert_node(node):
    global tree
    if tree == None:
        tree = node
        return

    p = tree
    while p != None:
        if p.value > node.value:
            if p.leftNode == None:
                p.leftNode = node
                return
            else:
                p = p.leftNode
        else:
            if p.rightNode == None:
                p.rightNode = node
                return
            else:
                p = p.rightNode

# 查找相应值的节点
def search_node(value):
    global tree
    if tree == None:
        return None

    p = tree
    while p != None:
        if p.value > value:
            p = p.leftNode
        elif p.value < value:
            p = p.rightNode
        else:
            return p

    return None

# 删除相应的节点
def delete_node(value):
    global tree
    p = tree
    pp = None

    # 找到值为value的节点，以及这个节点的父节点
    while p != None and value != p.value:
        pp = p
        if p.value > value:
            p = p.leftNode
        elif p.value < value:
            p = p.rightNode

    # 没有找到相应的值的节点
    if p == None:
        return

    # 要删除的节点是中间的节点
    if p.leftNode != None and p.rightNode != None:
        # 应找到右子树中最左边的节点，就是右子树中值最小的节点，替换掉当前的节点的值，并删除掉最小节点
        minNode = p.rightNode
        pMinNode = p
        while minNode.leftNode != None:
            pMinNode = minNode
            minNode = minNode.leftNode

        # 找到了最小节点之后, 最小的节点肯定是叶子节点
        p.value = minNode.value
        # 把p和pp指向要删除的那个最小节点，这样的话，在后面统一删除叶子节点的时候会将其删掉
        p = minNode
        pp = pMinNode

    # 要删除的节点是叶子节点或者只有一个子节点
    childNode = None
    if p.leftNode == None:
        childNode = p.rightNode
    else:
        childNode = p.leftNode

    if pp == None:          # 要删除的节点，正好是根节点，并且只有一个或者没有子节点
        tree = childNode
    elif pp.leftNode == p:  # 要删除的节点是父节点的左子节点
        pp.leftNode = childNode
    elif pp.rightNode == p: # 要删除的节点是父节点的右子节点
        pp.rightNode = childNode



# 定义一个全局的tree，以及tree中的相关数据
tree = None
values = [25, 15, 10, 18, 16, 21, 28, 30]
for value in values:
    node = Node(value, None, None)
    insert_node(node)

print('先序遍历二叉树的结果：')
TraversingBinaryTree.preorder_traversal(tree)
print('查找到的节点的值：')
searched = search_node(18)
print(searched.value)
print("删除节点15...")
delete_node(15)
print("删除节点15之后的先序遍历二叉树：")
TraversingBinaryTree.preorder_traversal(tree)

结果是：

程序运行结果.png

上一篇：写给媳妇儿的算法（十五）——二叉树及其遍历