二叉搜索树

二叉手搜索树

二叉搜索树(Binary Search Tree)，又名二叉排序树(Binary Sort Tree)。 二叉搜索树是具有有以下性质的二叉树：

  1. 若左子树不为空，则左子树上所有节点的值均小于或等于它的根节点的值。
  2. 若右子树不为空，则右子树上所有节点的值均大于或等于它的根节点的值。
  3. 左、右子树也分别为二叉搜索树。
from typing import List

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

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

    def insert(self, val: int):
        if self.root is None:
            self.root = TreeNode(val)
            return
        self._insert_node(self.root, val)

    def _insert_node(self, root: TreeNode, val: int):
        if val <= root.val:
            if root.left is None:
                root.left = TreeNode(val)
            else:
                self._insert_node(root.left, val)
        else:
            if root.right is None:
                root.right = TreeNode(val)
            else:
                self._insert_node(root.right, val)

    def delete(self, val: int):
        if self.root is None:
            return
        self.root = self._delete_node(self.root, val)

    def _delete_node(self, root: TreeNode, val: int):
        if root is None:
            return None

        if root.val == val:
            # 删除当前节点
            if root.left and root.right:
                # 左右子树不为空，找到右子树中最小的点更新为当前节点的值，然后递归的删除右子树中改节点的值
                left_node = self._get_min_node(root.right)
                root.val = left_node.val
                root.right = self._delete_node(root.right, left_node.val)
            elif root.left is None:
                # 左子树为空
                root = root.right
            elif root.right is None:
                # 右子树为空
                root = root.left
            else:
                root = None
        elif root.val > val:
            root.left = self._delete_node(root.left, val)
        else:
            root.right = self._delete_node(root.right, val)
        return root

    def query(self, val):
        self._query_node(self.root, val)

    def _query_node(self, root: TreeNode, val: int) -> TreeNode:
        if root is None:
            return None
        if root.val == val:
            return root
        elif root.val >= val:
            return self._query_node
        return -1

    def get_min(self)-> TreeNode:
        return self._get_min_node(self.root)

    def _get_min_node(self, root: TreeNode) -> TreeNode:
        if root.left is None:
            return root
        return self._get_min_node(root.left)

    def get_max(self) -> TreeNode:
        return self._get_max_node(self.root)

    def _get_max_node(self, root: TreeNode) -> TreeNode:
        if root.right is None:
            return root
        return self._get_max_node(root.right)

    def get_array(self) -> List:
        arr = []
        self._get_array(self.root, arr)
        return arr

    def _get_array(self, root: TreeNode, arr: List):
        if root is None:
            return
        self._get_array(root.left, arr)
        arr.append(root.val)
        self._get_array(root.right, arr)