在二叉搜索树中添加一个节点

Question

我目前正在努力实施 Binary search tree，但我在创建 add_node() 函数时遇到了问题。我试着用递归的方式做了，结果很奇怪。

例如- 如果我运行 add_node(1)、add_node(5) 和 add_node(0)，我的树只有 1，没有 5 和 0。

如果你能告诉我问题出在哪里，我会很高兴。

def add_node(self, value: int) -> None:
        
    if self.root == None:
        self.root = Node(value)
        return

    else:
        return self.add_recursion(self.root, value)

def add_recursion(self, node: Node, value: int) -> None:
        
    if node == None:
        node = Node(value)
        return

    elif value < node.value:
        return self.add_recursion(node.left, value)

    else:
        return self.add_recursion(node.right, value)

Answer 1

问题是如果 node.left 或 node.right 不存在，您如何处理。由于每次调用都会复制参数，因此在 add_recursion 中设置 node 的值对树没有影响。

def foo(val):
    print("foo start:", val)
    val = 5
    print("foo end:", val)

bar = 3
foo(bar)  # Value of bar is copied for call
print("after foo:", bar) # Prints bar is still 3

我想您可能也会对根节点的处理方式感到困惑。这是一些关于如何处理对 add_recursive.

的初始调用的起始代码

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

    def add_recursive(self, value: int):
        # TODO: recursively add to left or right
        # For example, here is how you could recursively make a linked list
        if self.right is None:
            self.right = Node(value)
        else:
            self.right.add_recursive(value)

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

    def add_node(self, value: int):
        if self.root is None:
            self.root = Node(value)
        else:
            # Call add_recursive on root instead of with root.
            self.root.add_recursive(value)

tree = BinarySearchTree()
tree.add_node(1)
tree.add_node(5)
tree.add_node(0)

Answer 2

当 None 值被传递给函数时，它是按值传递的，而不是按引用传递的，因为...没有引用。

    elif value < node.value:
        return self.add_recursion(node.left, value)

    else:
        return self.add_recursion(node.right, value)

当 node.left 或 node.right 为 None 时，节点最终被创建但未附加到 node。所以你可以做的是分别处理它们 None 的情况。

def add_recursion(self, node: Node, value: int) -> None:
    if node == None:
        node = Node(value)
    elif value < node.value:
        if node.left == None:
            node.left = Node(value)
        else:
            self.add_recursion(node.left, value)
    else:
        if node.right == None:
            node.right = Node(value)
        else:
            self.add_recursion(node.right, value)

虽然这是可行的，但它变得非常丑陋。查看 Locke 的答案，了解更好的代码结构方式。

此外，为了提高可读性，请避免在不必要的地方使用 return，例如在流程结束时使用 return。

在二叉搜索树中添加一个节点

adding a node in Binary Search Tree

python

recursion

data-structures

binary-search-tree