-1 
class EmptyMap():
    """
    EmptyMap has no slots
    """
    __slots__ = ()

class NonEmptyMap():
    """
    Has slots of left, key, value, and right. 
    """
    __slots__ = ('left', 'key', 'value', 'right')

def mkEmptyMap():
    """
    Is a function that takes no arguments and returns an instance of EmptyMap
    """
    return EmptyMap()

def mkNonEmptyMap(left, key, value, right):
    """
    Is a function that takes a map, a key, a value, and another map,
    and returns an instance of NonEmptyMap. This function merely initializes the slots;
    it is possible to use this function to create trees that are not binary search trees.
    """
    nonEmptyMap = NonEmptyMap()
    nonEmptyMap.left = left
    nonEmptyMap.key = key
    nonEmptyMap.value = value
    nonEmptyMap.right = right
    return nonEmptyMap

def mapInsert(key, value, node):
    """
    Is a function that takes a key, a value, and a map, and returns an instance
    of NonEmptyMap. Further, the map that is returned is a binary search tree based
    on the keys. The function inserts the key-value pair into the correct position in the
    map. The map returned need not be balanced. Before coding, review the binary
    search tree definition and the structurally recursive design pattern, and determine
    what the function should look like for maps. If the key already exists, the new value
    should replace the old value.
    """
    if isinstance(node, EmptyMap):
        return mkNonEmptyMap(mkEmptyMap(), key, value, mkEmptyMap())
    else:
        if key > node.key:
            node.right = mapInsert(key, value, node.right)
            return node.right
        elif key < node.key:
            node.left = mapInsert(key, value, node.left)
            return node.left
        elif key == node.key:
            node.value = value
            return mapInsert(key, value, node)
        else:
            raise TypeError("Bad Tree Map")

def mapToString(node):
    """
    Is a function that takes a map, and returns a string that represents the
    map. Before coding, review the structurally recursive design pattern, and determine
    how to adapt it for maps. An EmptyMap is represented as ’ ’. For an instance of
    NonEmptyMap, the left sub-tree appears on the left, and the right sub-tree appears
    on the right.
    """
    if isinstance(node, EmptyMap):
        return '_'
    elif isinstance(node, NonEmptyMap):
       return '(' + mapToString(node.left) + ',' + str(node.key) + '->'  + str(node.value) + ',' + mapToString(node.right)+ ')'
    else:
       raise TypeError("Not a Binary Tree")

def mapSearch(key, node):
    """
    Is a function that takes a key and a map, and returns the value associated
    with the key or None if the key is not there. Before coding, review the binary search
    tree definition and the structurally recursive design pattern, and determine how it
    should look for maps.
    """
    if isinstance(node, EmptyMap):
       return 'None'
    elif isinstance(node, NonEmptyMap):
       if key == node.key:
          return str(node.value)
       elif key < node.key:
          return mapSearch(key, node.left)
       elif key > node.key:
          return mapSearch(key, node.right)
    else:
       raise TypeError("Not a Binary Tree")

def main():
    smallMap = mapInsert(\
        'one',\
        1,\
        mapInsert(\
            'two',\
            2,\
            mapInsert(\
                'three',\
                3,\
                mkEmptyMap())))

    print(smallMap.key)
    print(smallMap.left.key)
    print(smallMap.right.key)

main()

当我运行程序时，我得到了一个我不知道我做错了什么的语法。我很确定 emptymap 有一个在 mkNonEmptyMap 函数中的对象。这是我的作业问题。

映射是将值与键相关联的数据结构。人们可以搜索一个特定的键来找到它的相关值。例如，值 3 可以与键“三”相关联。

one
Traceback (most recent call last):
  File "/Users/USER/Desktop/test.py", line 113, in <module>
    main()
  File "/Users/USER/Desktop/test.py", line 110, in main
    print(smallMap.left.key)
AttributeError: 'EmptyMap' object has no attribute 'key'
4

1 回答 1

1

如果你看看里面有什么smallMap，它left和right都是EmptyMaps。所以当然smallMap.left.key是行不通的——<code>EmptyMaps 没有keys。

那么，为什么会出错呢？好吧，让我们把那个怪物表达式分解成几个步骤，看看它哪里出错了：

>>> empty = mkEmptyMap()
>>> mapToString(empty)
'_'
>>> three = mapInsert('three', 3, mkEmptyMap())
>>> mapToString(three)
'(_,three->3,_)'
>>> two = mapInsert('two', 2, three)
>>> mapToString(two)
(_,two->2,_)

有问题。该two对象没有左或右。怎么样three？

>>> mapToString(three)
(_,three->3,(_,two->2,_))

好的，所以我们确实有一个有效的平衡树——但它不在two返回的对象中，而是在您传入的对象中（您的原始程序甚至没有保留对它的引用）mapInsert。threemapInsert

那么，为什么会这样呢？那有效吗？这取决于您的设计。如果你想像这样改变你的论点，这样做是完全合理的（尽管我怀疑这不是你的老师真正想要的——任何试图强迫你像这样用 Python 编写 ML 的人可能希望你使用非变异算法……）。但是你需要总是返回根节点。您的函数显然试图返回新创建的节点，无论它是否是根节点。所以，只要解决这个问题：

    if key > node.key:
        node.right = mapInsert(key, value, node.right)
        return node # not node.right

其他两种情况也是如此。（我不确定你为什么一开始就试图递归地调用自己==。）

如果你这样做，代码不再有错误。

它似乎并没有真正正确地平衡树，但这是你要解决的下一个问题。

于 2013-11-11T05:35:50.337 回答