1

各ノードが 3 つのデータを保持する Python の BST があります。それらのデータは、ID、マーク、および名前です。

私がやろうとしているのは名前を検索することですが、ノードは ID に基づいています。これが私が検索した方法です。この関数は、特定の Name の 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)

残念ながら、ツリーの左側のみを検索し、右側は検索しません。最初に右側を検索すると、逆になります。

これを両側で検索するにはどうすればよいですか？

4

5 に答える 5

4

returnまだ終わっていないのならやめるべきです！代わりに、最後の 4 行を 1 つの短絡に置き換えることができますor。

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

ただし、 ID に が含まれていないことを確認してください。含まれていない場合、 は None と同様に偽の値である0ため、このメソッドは失敗します。0

于 2012-04-11T00:00:36.267 に答える
2 
...
result = findName(tree['left'],name)
if result is None:
    result = findName(tree['right'],name) 
return result
于 2012-04-10T23:59:28.033 に答える
0

問題は、あなたが戻ってきていることです

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

あなたがしなければならないことは、ローカル変数を作成し、それをそれからの値に設定することfindName()です。

于 2012-04-11T00:00:52.027 に答える
0

これを試して： 

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-11T00:48:44.410 に答える
0

余分な再帰呼び出しを避けたい場合は、このようにブランチをたどることができます。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-11T00:10:28.220 に答える