是否可以使用一个指针将节点插入到 BST 中？

Question

我想知道我是否可以在没有尾随指针 y 的情况下插入。这是我的代码：

def tree_insert(root, key):
    z = TreeNode(key)
    y = None
    x = root
    while x:
        y = x
        if z.val < x.val:
            x = x.left
        else:
            x = x.right
    if y is None:
        root = z
    elif z.val < y.val:
        y.left = z
    else:
        y.right = z

谢谢！

Answer 1

你的函数有一个问题：当函数赋值 root = x 时，调用者不会知道它，因为 root 是一个局部变量。

您可以通过多种方式解决此问题。一个是你有一个合同，该功能总是 returns 根。

为了避免 y，您可以在知道应该去哪里后立即分配 z：

def tree_insert(root, key):
    z = TreeNode(key)
    if not root:
        return z  # new root
    x = root
    while True:
        if z.val < x.val:
            if not x.left:
                x.left = z
                return root
            x = x.left
        else:
            if not x.right:
                x.right = z
                return root
            x = x.right

所以按如下方式使用它——总是分配回 root:

root = None
root = tree_insert(root, 5)
root = tree_insert(root, 2)
root = tree_insert(root, 4)
root = tree_insert(root, 8)
root = tree_insert(root, 1)

你甚至可以保存更多的变量，如果你把这个函数变成递归的：

def tree_insert(root, key):
    if not root:
        return TreeNode(key)
    if key < root.val:
        root.left = tree_insert(root.left, key)
    else:
        root.right = tree_insert(root.right, key)
    return root

同样，这个函数 returns 根，调用者必须考虑到它。

是否可以使用一个指针将节点插入到 BST 中？

Is it possible to use one pointer to insert a node into a BST?

algorithm

binary-search-tree

data-structures