二分查找树插入函数

Question

大家晚上好，

我的任务是在Python中设计一个函数，它将构建一个二进制搜索树。当我自己遍历这个函数时，它看起来很有意义，应该可以工作。然而，无论出于什么原因，它只构建最后一棵“树”，而不保存任何先前的树信息。我已经包括了我的类，构造函数，当然还有函数。任何建议都很感谢！为了测试这个函数，我使用下面的代码行：

newMap = mapInsert1('one', 1, mapInsert1('two', 2, mkEmptyMap()))


///CODE///
class EmptyMap():
    __slots__ = ()

class NonEmptyMap():
    __slots__ = ('left', 'key', 'value', 'right')

def mkEmptyMap():
    return EmptyMap()

def mkNonEmptyMap(left, key, value, right):
    nonEmptyMap = NonEmptyMap()
    nonEmptyMap.left = left
    nonEmptyMap.key = key
    nonEmptyMap.value = value
    nonEmptyMap.right = right

    return nonEmptyMap

def mapInsert1(key, value, node):
    if isinstance(node, EmptyMap):
        node = mkNonEmptyMap(mkEmptyMap(), key, value, mkEmptyMap())
        return node
    else:
        if key > node.key:
            return mapInsert1(key, value, node.right)
        elif key < node.key:
            return mapInsert1(key, value, node.left)
        elif key == node.key:
            node.value = value
            return mapInsert1(key, value, node)
        else:
            raise TypeError('Bad Map')

Answer 1

好的，我已经得到你的答案了。你的逻辑本身没有问题，只是你试图用Python实现你的算法的问题。

在你尝试实现你的算法的方式上有几个问题。第一个问题是如何将变量传递给函数。我推荐阅读这篇StackOverflow Question here，它讨论了如何将变量传递给函数Python。简而言之，由于您在代码中传递和更新变量的方式，您总是在更新变量的本地作用域副本，这实际上并不影响您想要更新的变量。

要在代码中看到这一点，请尝试执行以下操作：

>>> newMap = mapInsert1('one', 1, mapInsert1('two', 2, mkEmptyMap()))

如你所说，这是行不通的。但这确实是：

>>> newMap = mapInsert1('one', 1, mkEmptyMap())
>>> newMap.right = mapInsert1('two', 2, mkEmptyMap()))

但这并不是很有帮助，因为在尝试添加新节点之前，您必须知道要更新的节点。

为了修复你的代码，我所做的就是清理你的类实现。我做了以下更改：

1. 首先，我开始使用正确的构造函数。Python类使用初始化函数作为构造函数。有关我添加的information.
2. Second，函数的更多信息，请参阅here。这才是真正解决你问题的方法。使用此函数意味着您不会覆盖本地范围的变量，而是更改外部变量。再次查看上面链接的变量传递问题以获取更多实例。我将空映射设置为映射类的一个空实例，并去掉了isinstance()检查。在Python中，通常最好尽可能避免使用isinstance。Here是关于避免isinstance
3. Fourth，的更多信息我修复了代码中的无限循环错误。如果您查看elif key == node.key条件，您将再次使用相同的参数调用mapInsert1，这将产生一个无限递归循环。

以下是生成的代码：

class Map():
    __slots__ = ('left', 'key', 'value', 'right')

    def __init__(self, left, key, value, right):
        self.left = left
        self.key = key
        self.value = value
        self.right = right

    def insert(self, left, key, value, right):
        self.left = left
        self.key = key
        self.value = value
        self.right = right

    def isEmpty(self):
        return self.left == self.right == self.key == self.value == None

def mkEmptyMap():
    return Map(None, None, None, None)

def mapInsert1(key, value, node):
    if node.isEmpty():
        print '0'
        node.insert(mkEmptyMap(), key, value, mkEmptyMap())
        return node
    else:
        if key > node.key:
            print '1'
            return mapInsert1(key, value, node.right)
        elif key < node.key:
            print '2'
            return mapInsert1(key, value, node.left)
        elif key == node.key:
            print '3'
            node.value = value
            return node
        else:
            raise TypeError('Bad Map')

这里有一个快速测试：

>>> root = mapInsert1('five', 5, mkEmptyMap())
>>> mapInsert1('four', 4, root)
>>> mapInsert1('ace', 1, root)
>>> mapInsert1('five', 'five', root)
>>> root.left.isEmpty()
Out: False
>>> root.left.key
Out: 'ace'
>>> root.left.value
Out: 1
>>> root.right.isEmpty()
Out: False
>>> root.right.key
Out: 'four'
>>> root.right.value
Out: 4
>>> root.key
Out: 'five'
>>> root.value
Out: 'five'