在Python中搜索二叉搜索树的两侧

我在python中有一个BST，每个节点保存3段数据。这些数据是ID，标记和名称。在Python中搜索二叉搜索树的两侧

我想要做的是搜索一个名称，但节点基于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)

不幸的是，我会永远只能搜索树的左侧，而不是正确的，相反，如果适用我第一次搜索的右侧。

如何搜索双方？

来源

2012-04-10 Unknown

如果树['left']：'和'if tree ['right']：''可能可以做，因为None的结果为false。 – 2012-04-11 00:06:15

如果您还没有完成，您不应该return！相反，你可以用一个单一的，短路or取代你的最后四行：

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

确保您的ID不包括0，虽然，否则此方法将失败，因为0是falsy值，只是像无。

来源

2012-04-11 00:00:36

当其中一个分支是None时，这将导致一个额外的递归级别，但不应该造成任何伤害，因为这种情况是在函数开始时进行测试的。 – 2012-04-11 00:06:55

这工作完美，非常感谢:) – Unknown 2012-04-11 00:07:03

@gnibbler：是的，我正在考虑:) – 2012-04-11 00:07:48

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

来源

2012-04-10 23:59:28

问题是你在

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

，你所要做的就是创建一个局部变量，它从findName()设定值然后如果你没有正在返回继续与正确的，否则返回值。

来源

2012-04-11 00:00:52 twain249

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

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

来源

2012-04-11 00:10:28

试试这个：

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'

它还可以处理多个匹配。

来源

2012-04-11 00:48:44 user866903

在Python中搜索二叉搜索树的两侧

回答

相关问题