二叉查找树

定义

二叉就是每个节点最多有两个孩子节点，并且左子树的结点值小于根节点，右子树的结点值大于根节点，左右子树分别为二叉查找树。
下面就是一个简单的二叉查找树：

查找

查找的步骤：

• 比较查找值与根节点值
• 小于根节点，则查找左子树
• 大于根节点，则查找右子树

比如在下面的二叉查找树中查找9的过程：

插入

插入跟查找的过程很相似，利用查找的步骤找到要插入的位置，插入的位置肯定为叶子节点。
例如在下面的二叉查找树中插入30的过程：

删除

删除节点分为三种情况，下面详细介绍一下每种情况下的处理过程。

没有子节点

这种情况下，可以直接删除节点。
例如在下面的二叉查找树中删除1节点：

只有一个子节点的情况

只有左节点或者只有右节点的情况下，用左/右节点替换掉要删除的节点。
例如在下面的二叉查找树中删除20对应节点：

有两个子节点的情况

有两个子节点的时候，分两步：

• 找到右子树中最小的节点，用找到的节点替换掉要删除的节点
• 删除找到的节点

例如在下面的二叉查找树中删除3对应的节点：

代码实现

import reprlib

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def __repr__(self):
        return 'Node(%s)' % reprlib.repr(self.value)

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def search(self, value):
        return self._search(self.root, value) is not None

    def _search(self, node, value):
        if node is None:
            return None
        elif node.value == value:
            return node
        elif value > node.value:
            return self._search(node.right, value)
        else:
            return self._search(node.left, value)

    def delete(self, value):
        self.root = self._delete(self.root, value)

    def _delete(self, node, value):
        if node is None:
            print("No node to delete.")
        elif node.value > value:
            node.left = self._delete(node.left, value)
        elif node.value < value:
            node.right = self._delete(node.right, value)
        elif node.value == value:
            if node.left is None and node.right is None:
                node = None
            elif node.left is not None and node.right is not None:
                minnode = self.findmin(node.right)
                node.value = minnode.value
                node.right = self._delete(node.right, minnode.value)
            elif node.left is not None:
                node = node.left
            else:
                node = node.right

        return node

    def findmin(self, node):
        if node is None:
            return None
        elif node.left is None:
            return node
        else:
            return self.findmin(node.left)

    def insert(self, value):
        self.root = self._insert(self.root, value)

    def _insert(self, node, value):
        if node is None:
            node = Node(value)
        elif value > node.value:
            node.right = self._insert(node.right, value)
        elif value < node.value:
            node.left = self._insert(node.left, value)
        else:
            print("The node is exist!")

        return node

bst = BinarySearchTree()
bst.insert(10)
bst.insert(3)
bst.insert(20)
bst.insert(1)
bst.insert(7)
bst.insert(25)
bst.insert(5)
bst.insert(9)
bst.insert(23)
print(bst.search(9))
bst.delete(9)

遍历

树存在三种遍历方式，这些遍历方式都是针对根节点来说的：

• 前序遍历：根节点→左子树→右子树
• 中序遍历：左子树→根节点→右子树
• 后序遍历：左子树→右子树→根节点