定义
二叉就是每个节点最多有两个孩子节点，并且左子树的结点值小于根节点，右子树的结点值大于根节点，左右子树分别为二叉查找树。
下面就是一个简单的二叉查找树：
查找
查找的步骤：
- 比较查找值与根节点值
- 小于根节点，则查找左子树
- 大于根节点，则查找右子树
比如在下面的二叉查找树中查找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)
遍历
树存在三种遍历方式，这些遍历方式都是针对根节点来说的：
- 前序遍历：根节点→左子树→右子树
- 中序遍历：左子树→根节点→右子树
- 后序遍历：左子树→右子树→根节点
