python中使用递归插入二叉搜索树

Question

我试图使用递归在二叉搜索树中插入值，但是当我使用中序遍历运行它时，我得到 None 的输出。我尝试查看其他语言实现此功能，我只是尝试复制它，但它不起作用。我将树的根传递给插入函数，如果它不为空，我希望它向左或向右遍历。有人可以告诉我这有什么问题吗？我尝试将 bst.root 转换为 bst.get_root() ，但仍然产生相同的结果。

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

class BinaryTree:
    def __init__(self):
        self.root = None
        self.size = 0

    def get_size(self):
        return self.size

    def get_root(self):
        return self.root

    def insert(self, root, value):
        if root is None:
            root = Node(value)
        else:
            if value < root.value:
                root.left = self.insert(root.left, value)
            else:
                root.right = self.insert(root.right, value)
        return root

    def inorder(self, root):
        if root == None:
            return
        else:
            self.inorder(root.left)
            print(root.value, end=" -> ")
            self.inorder(root.right)

bst = BinaryTree()
bst.insert(bst.root, 2)
bst.insert(bst.root, 4)
bst.insert(bst.root, 3)
bst.insert(bst.root, 1)

print(bst.inorder(bst.root))

Answer 1

问题是 anode可能是，None并且您正在用它调用一个函数，然后分配一个节点None，但没有保存任何内容。

我们来看一下：

def insert(self, root, value):  # say root is None
    if root is None:
        root = Node(value)  # here we're doing: `None = Node(value)`
    else:
        if value < root.value:
            root.left = self.insert(root.left, value)
        else:
            root.right = self.insert(root.right, value)
    return root 

为了修复它，我们需要“向上一级”，然后进行分配（顺便node.left说一下，root 是一个坏名字，所以我使用“node”代替）。Nonenode.left

一种方法是：

def insert(self, value):  # this is the function that gets called, pay attention that we're not sending `root`
    if self.root is None:
        self.root = Node(value)
    else:
        self._insert(self.root, value) # here's the call to a "private" function to which we are passing nodes down, starting from root

def _insert(self, node, value):
    if value < node.value:  # we know that `node` cannot be None - so it's safe to check its value! 
        if node.left:
            self._insert(node.left, value) # the recursive call is done only when `node.left` is not None
        else:
            node.left = Node(value)  # direct assignment
    else:
        if node.right:
            self._insert(node.right, value)
        else:
            node.right = Node(value)  # direct assignment

两条评论：

1. 现在有一个更清晰的界面，看看插入调用现在的样子：

    bst = BinaryTree()
    bst.insert(2)
    bst.insert(4)
    bst.insert(3)
    bst.insert(1)

2. insert 是一个“设置”值的操作，因此 - 它不必返回任何内容（如果您确实想要的话，也可以）。