BST 插入在 Python 中无法正常工作

Question

我在 Python 中实现了 BST，但我在 but_insert(t, k) 中遇到了问题。基本上，如果我只是将 children 添加到根目录，如下所示，它会起作用：

T = Node(7)
bst_insert(T, 9)
bst_insert(T, 5)

但是如果我插入另一个键，那么从根开始的整个分支似乎都被删除了。例如，如果我执行：

T = Node(7)
bst_insert(T, 9)
bst_insert(T, 5)
bst_insert(T, 3)

然后当我按顺序打印 T 时，我只得到 7 9.

这是 Node 构造函数和 bst_insert（print_in_order 函数正常工作，所以我没有包含它）。

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


def bst_insert(t, k):
    if t is None:
        t = Node(k)

    elif k <= t.key:
        if t.left is None:
            t.left = Node(k)
        else:
            t.left = bst_insert(t.left, k)
    else:
        if t.right is None:
            t.right = Node(k)
        else:
            t.right = bst_insert(t.right, k)

谢谢。

Answer 1

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


    def bst_insert(t, k):
        if t is None:
            t = Node(k)

        elif k <= t.key:
            if t.left is None:
                t.left = Node(k)
            else:
                t.left = bst_insert(t.left, k) #1
        else:
            if t.right is None:
                t.right = Node(k)
            else:
                t.right = bst_insert(t.right, k) #2
        # return the node, #1 and #2 will always get None value
        return t

Answer 2

from __future__ import annotations


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

    def __repr__(self) -> str:
        return f"{self.__class__.__name__}({self.value})"


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

    def add(self, root: Node, value: int) -> Node:
        # if there is not root (empty node) -> then create new one
        if root is None:
            return Node(value)
        if value <= root.value:
            root.left = self.add(root.left, value)
        else:
            root.right = self.add(root.right, value)
        return root

    def print(self, root: Node) -> None:
        """Prints inorders BST values."""
        if root is None:
            return
        self.print(root.left)
        print(root.value, end=" ")
        self.print(root.right)


if __name__ == "__main__":
    values = [10, 6, 12, 3, 7, 4, 2]

    bst = BST()
    root = None
    for value in values:
        root = bst.add(root, value)

    bst.print(root)

    # output
    # 2 3 4 6 7 10 12

BST 插入在 Python 中无法正常工作

BST Insert not working properly in Python

python

implementation

binary-search-tree

data-structures