1

大家晚上好

我的任务是在 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')
4

1 回答 1

2

好的，我在这里得到了你的答案。您的逻辑本身没有问题，只是您尝试在 Python 中实现算法的问题。

您尝试实现算法的方式存在几个问题。其中第一个与变量如何传递给函数有关。我建议在此处阅读此 StackOverflow 问题，该问题讨论了如何将变量传递到 Python 函数中。长话短说，由于您在代码中传递和更新变量的方式，您总是在更新变量的本地范围副本，这实际上不会影响您要更新的变量。

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

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

正如你所说，这不起作用。但这确实：

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

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

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

  1. 首先，我开始使用适当的构造函数。Python 类使用init函数作为构造函数。请参阅此处了解更多信息。
  2. 其次，我添加了插入功能。这才是真正解决您的问题的方法。使用此函数意味着您不会覆盖局部范围的变量，而是改变外部变量。再次，查看我上面链接的变量传递问题以获取更多详细信息。
  3. 第三，我使空地图只是地图类的一个空实例，并去掉了 isinstance() 检查。在 Python 中，通常最好尽可能避免使用 isinstance。 这是有关避免 isinstance 的更多信息
  4. 第四，我修复了代码中的一个无限循环错误。如果您查看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'
于 2012-11-03T04:34:32.737 回答