擅长:python、mysql、java
<p>我很确定您遇到的问题很简单,就是您没有从<code>mapInsert</code>获得期望的返回值。当前代码始终返回插入所提供值的节点,即使该节点是树中某个深处的叶节点。(事实上,我并没有仔细研究它,在您递归和返回的内容中还有一些额外的错误。)</p>
<p>我认为您应该更改<code>mapInsert</code>的<code>else</code>块中的<code>return</code>语句,以返回<code>mp</code>,而不是递归调用的结果。调用的结果应该分配给<code>mp.left</code>或{<cd7>},这取决于我们递归的哪一边。在</p>
<pre><code>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
</code></pre>
<p>请注意,更“Pythonic”的设计可能会使用类中的方法,而不是使用单独的函数来处理这种事情。不过,这需要对空树进行一些不同的处理。在</p>