Python中的树型映射

Question

mapSearch是一个函数，它接受一个键和一个映射，并返回与键相关的值；如果键不存在，则返回None。在

问题：当我运行搜索函数时，无论我为键输入了什么，它都会返回相同的值。在

class EmptyMap():
    __slots__ = ()


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

EMPTY_MAP = EmptyMap()

def mkEmptyMap():
    return EMPTY_MAP

def mkNonEmptyMap(b1, key, value, b2):
    node = NonEmptyMap()
    node.left = b1;
    node.key = key;
    node.value = value;
    node.right = b2;
    return node;

def mapInsert(key, value, mp):

if isinstance(mp, EmptyMap):
    return mkNonEmptyMap(mkEmptyMap(), key, value, mkEmptyMap())

else:
    if key == mp.key:
        mp.value = value
    elif mp.key < key:
        mp.left = mapInsert(key, value, mp.left)
    else:
        mp.right = mapInsert(key, value, mp.right)

    return mp

def search(key, mp):
    if isinstance(mp, EmptyMap):
        return None
    elif isinstance(mp, NonEmptyMap):
        if key == mp.key:
            return mp.value
        elif mp.key < key:
            mp.left = search(key, mp.left)
            return mp.value
        else:
            mp.right = search(key, mp.right)
            return mp.value

Answer 1

我很确定您遇到的问题很简单，就是您没有从mapInsert获得期望的返回值。当前代码始终返回插入所提供值的节点，即使该节点是树中某个深处的叶节点。（事实上，我并没有仔细研究它，在您递归和返回的内容中还有一些额外的错误。）

我认为您应该更改mapInsert的else块中的return语句，以返回mp，而不是递归调用的结果。调用的结果应该分配给mp.left或{}，这取决于我们递归的哪一边。在

def mapInsert(key, value, mp):

    if isinstance(mp, EmptyMap):
        return mkNonEmptyMap(mkEmptyMap(), key, value, mkEmptyMap())

    else:
        if key == mp.key:
            mp.value = value
        elif mp.key < key:
            mp.left = mapInsert(key, value, mp.left) # don't return recursive result
        else:
            mp.right = mapInsert(key, value, mp.right) # pass the right child here!

        return mp # always return mp from this branch

请注意，更“Pythonic”的设计可能会使用类中的方法，而不是使用单独的函数来处理这种事情。不过，这需要对空树进行一些不同的处理。在

Answer 2

一个明显的问题是：

    if key == mp.key:
        mp.value = value
    elif mp.key > key:
        return mapInsert(key, value, mp.left)
    else:
        return mapInsert(key, value, mp.left)

其中一个根本不返回任何内容，其他两个返回相同的内容。在