新手插入二进制树检查

Question

我正在学习二进制搜索树，我不明白为什么这段代码不能插入二进制搜索树：

def insert(self, data, node):
    node_to_insert = Node(data)
    if node is None:
        node = node_to_insert
    else:
        if data < node.data:
            node.left = self.insert(data, node.left)
        else:
            node.right = self.insert(data, node.right)

我知道这个代码有效：

    def insert(self, data, node):
        node_to_insert = Node(data)
        if node is None:
            node = node_to_insert
        else:
            if data < node.data:
                if node.left is None:
                    node.left = node_to_insert
                else:
                    self.insert(data, node.left)
            else:
                if node.right is None:
                    node.right = node_to_insert
                else:
                    self.insert(data, node.right)

我认为，当函数被调用时，应该进行额外的is None检查，不是吗？

为什么这样做：

def print_inorder(self, node):
    if node is not None:
        self.print_inorder(node.left)
        print node.data
        self.print_inorder(node.right)

当它在调用self.print_inorder(node.left) 之前没有额外的检查node.left is None时

Answer 1

在您的代码中：

if data < node.data:
    node.left = self.insert(data, node.left)
else:
    node.right = self.insert(data, node.right)

您的方法self.insert返回None，因此在将数据正确插入node.left或node.right之后，您将为它们分配None。相反，你想要

if data < node.data:
    self.insert(data, node.left)
else:
    self.insert(data, node.right)