二叉排列树的基本运算

二叉排序树（Binary Search Tree，BST）是一种特殊的二叉树，它满足以下条件：

1. 左子树上所有节点的值均小于它的根节点的值；
2. 右子树上所有节点的值均大于它的根节点的值；
3. 左右子树也都是二叉排序树。

基本运算包括：

1. 创建

对于一个空树，直接将新节点插入作为根节点即可。对于非空树，从根节点开始，比较要插入的节点值与当前节点值的大小关系，如果比当前节点值小，则向左子树递归插入；如果比当前节点值大，则向右子树递归插入。

2. 查找

从根节点开始，如果要查找的节点值等于当前节点值，则返回当前节点；如果要查找的节点值小于当前节点值，则向左子树递归查找；如果要查找的节点值大于当前节点值，则向右子树递归查找。如果最后找不到该节点，则返回空。

3. 插入

从根节点开始，比较要插入的节点值与当前节点值的大小关系，如果比当前节点值小，则向左子树递归插入；如果比当前节点值大，则向右子树递归插入。如果最后找到该节点，则不插入，如果没有找到该节点，则将新节点插入到对应的位置。

4. 删除

删除节点分为三种情况：

- 要删除的节点没有子节点，直接删除即可；
- 要删除的节点只有一个子节点，将其子节点替换为该节点；
- 要删除的节点有两个子节点，需要找到该节点的中序遍历的后继节点（即右子树中最小的节点），将其值赋给要删除的节点，然后删除该后继节点。

5. 遍历

- 前序遍历：先遍历根节点，然后递归遍历左子树和右子树。
- 中序遍历：先递归遍历左子树，然后遍历根节点，最后递归遍历右子树。
- 后序遍历：先递归遍历左子树和右子树，然后遍历根节点。

以下是二叉排序树的算法实现：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

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

    # 创建二叉排序树
    def insert(self, val):
        if self.root is None:
            self.root = TreeNode(val)
        else:
            self._insert(self.root, val)

    def _insert(self, node, val):
        if val < node.val:
            if node.left is None:
                node.left = TreeNode(val)
            else:
                self._insert(node.left, val)
        else:
            if node.right is None:
                node.right = TreeNode(val)
            else:
                self._insert(node.right, val)

    # 查找二叉排序树
    def search(self, val):
        return self._search(self.root, val)

    def _search(self, node, val):
        if node is None or node.val == val:
            return node
        elif val < node.val:
            return self._search(node.left, val)
        else:
            return self._search(node.right, val)

    # 删除二叉排序树
    def remove(self, val):
        self.root = self._remove(self.root, val)

    def _remove(self, node, val):
        if node is None:
            return node
        if val < node.val:
            node.left = self._remove(node.left, val)
        elif val > node.val:
            node.right = self._remove(node.right, val)
        else:
            if node.left is None:
                temp = node.right
                node = None
                return temp
            elif node.right is None:
                temp = node.left
                node = None
                return temp
            temp = self._minValueNode(node.right)
            node.val = temp.val
            node.right = self._remove(node.right, temp.val)
        return node

    def _minValueNode(self, node):
        current = node
        while current.left is not None:
            current = current.left
        return current

    # 遍历二叉排序树
    def preorder_traversal(self):
        self._preorder_traversal(self.root)

    def _preorder_traversal(self, node):
        if node is not None:
            print(node.val)
            self._preorder_traversal(node.left)
            self._preorder_traversal(node.right)

    def inorder_traversal(self):
        self._inorder_traversal(self.root)

    def _inorder_traversal(self, node):
        if node is not None:
            self._inorder_traversal(node.left)
            print(node.val)
            self._inorder_traversal(node.right)

    def postorder_traversal(self):
        self._postorder_traversal(self.root)

    def _postorder_traversal(self, node):
        if node is not None:
            self._postorder_traversal(node.left)
            self._postorder_traversal(node.right)
            print(node.val)