python - 在 Python 中搜索二叉搜索树的两边

Question

我在 python 中有一个 BST，每个节点包含 3 条数据。这些数据是 ID、Mark 和 Name。

我正在尝试做的是搜索名称，但节点基于 ID，这就是我搜索的方式。该函数应该输出特定名称的 ID。

def findName(tree,name):
    if tree==None:
        return None
    elif tree['name']==name:
        return tree['id']
    if tree['left']!=None:
        return findName(tree['left'],name)
    if tree['right']!=None:
        return findName(tree['right'],name) 

不幸的是，我只会搜索树的左侧，而不是右侧，如果我先搜索右侧，则相反。

我如何搜索双方？

Answer 1

return如果你还没有完成，你不应该这样做！相反，您可以用一个短路替换最后 4 行or：

return findName(tree['left'], name) or findName(tree['right'], name)

但是，请确保您的 ID 不包含0，否则此方法将失败，因为0它是一个虚假值，就像 None 一样。

Answer 2

...
result = findName(tree['left'],name)
if result is None:
    result = findName(tree['right'],name) 
return result

Answer 3

问题是你正在返回

if tree['left']!=None:
    return findName(tree['left'],name) 

你需要做的是创建一个局部变量并将其设置为findName()从那时起的值，如果你得到 None 继续正确，否则返回值。

Answer 4

如果您希望避免额外的递归调用，您可以像这样遍历分支。请注意，最好测试身份None而不是相等

for branch in ('left', 'right'):
    if tree[branch] is not None:
        result = findName(tree[branch], name)
        if result is not None:
            return result

Answer 5

试试这个：

def search(node, name):
    self_result = [node['id']] if node['name'] == name else []
    if not node['left'] and not node['right']:
        return self_result
    elif node['left'] and not node['right']:
        return self_result + search(node['left'], name)
    elif not node['left'] and node['right']:
        return self_result + search(node['right'], name)
    else:
        return self_result + search(node['left'], name) + search(node['right'], name)

test_tree = {'id':0, 'name': 'a', 
             'left': {'id':1, 'name': 'a', 
                      'left':{'id':3, 'name':'c', 
                              'left':{'id':4,'name': 'd', 
                                  'left' : None,
                                  'right' : None},
                          'right':None},
                  'right':{'id':4, 'name':'e',
                           'left': None,
                           'right': None}
                  }, 
             'right': {'id':5, 'name':'c',
                       'left': {'id':6, 'name':'e',
                                'left': None,
                                'right': None},
                       'right': {'id': 7, 'name': 'a',
                                 'left' : {'id' : 8, 'name': 'b',
                                           'left': None,
                                           'right' : None},
                                 'right' : None
                                }
                      }
            }

if __name__ == '__main__':
    assert search(test_tree, 'a') == [0, 1, 7]
    assert search(test_tree, 'b') == [8]
    assert search(test_tree, 'c') == [3, 5]
    assert search(test_tree, 'e') == [4, 6]
    print 'ok'

它还可以处理多个匹配项。