Python 实现二叉搜索树的四种方法

本文将介绍 4 种 Python 实现二叉搜索树的方法。

定义

二叉搜索树（Binary Search Tree）是一种二叉树，它的每个节点最多只有两个子节点，其中左子节点的值小于父节点的值，右子节点的值大于父节点的值。它的左子树和右子树同样也是一棵二叉搜索树。

方法一：递归实现

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

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

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

    def _insert(self, root, val):
        if root is None:
            return TreeNode(val)
        if val < root.val:
            root.left = self._insert(root.left, val)
        elif val > root.val:
            root.right = self._insert(root.right, val)
        return root

    def inorder(self):
        self._inorder(self.root)

    def _inorder(self, root):
        if root:
            self._inorder(root.left)
            print(root.val, end=" ")
            self._inorder(root.right)

使用示例：

bst = BinarySearchTree()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(1)
bst.insert(9)
bst.inorder()

输出结果：

1 3 5 7 9 

方法二：迭代实现

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

    def insert(self, val):
        if self.root is None:
            self.root = TreeNode(val)
            return
        node = self.root
        while node:
            if val < node.val:
                if node.left is None:
                    node.left = TreeNode(val)
                    return
                else:
                    node = node.left
            elif val > node.val:
                if node.right is None:
                    node.right = TreeNode(val)
                    return
                else:
                    node = node.right

    def inorder(self):
        if self.root is None:
            return
        stack = []
        node = self.root
        while stack or node:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            print(node.val, end=" ")
            node = node.right

使用示例：

bst = BinarySearchTree()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(1)
bst.insert(9)
bst.inorder()

输出结果：

1 3 5 7 9 

方法三：Morris 遍历

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

    def insert(self, val):
        if self.root is None:
            self.root = TreeNode(val)
            return
        node = self.root
        while node:
            if val < node.val:
                if node.left is None:
                    node.left = TreeNode(val)
                    return
                else:
                    node = node.left
            elif val > node.val:
                if node.right is None:
                    node.right = TreeNode(val)
                    return
                else:
                    node = node.right

    def inorder(self):
        curr = self.root
        while curr:
            if curr.left is None:
                print(curr.val, end=" ")
                curr = curr.right
            else:
                pre = curr.left
                while pre.right and pre.right != curr:
                    pre = pre.right
                if pre.right is None:
                    pre.right = curr
                    curr = curr.left
                else:
                    pre.right = None
                    print(curr.val, end=" ")
                    curr = curr.right

使用示例：

bst = BinarySearchTree()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(1)
bst.insert(9)
bst.inorder()

输出结果：

1 3 5 7 9 

方法四：双向链表

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

class BinarySearchTree:
    def __init__(self):
        self.head = None
        self.tail = None

    def insert(self, val):
        node = TreeNode(val)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            curr = self.head
            while curr:
                if val <= curr.val:
                    if curr.left is None:
                        curr.left = node
                        node.right = curr
                        self.head = node
                        break
                    else:
                        curr = curr.left
                else:
                    if curr.right is None:
                        curr.right = node
                        node.left = curr
                        self.tail = node
                        break
                    else:
                        curr = curr.right

    def inorder(self):
        curr = self.head
        while curr:
            print(curr.val, end=" ")
            curr = curr.right

使用示例：

bst = BinarySearchTree()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(1)
bst.insert(9)
bst.inorder()

输出结果：

1 3 5 7 9 

以上就是 Python 实现二叉搜索树的四种方法。可以根据实际情况选择不同的方法来实现。