时间戳

首页 > 解决方案 > 在二叉搜索树中添加一个节点

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

问题描述

我目前正在实现 a但我在创建函数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)

标签： pythonrecursiondata-structuresbinary-search-tree

解决方案

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

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)

推荐阅读