Pythonでの各バイナリツリーレベルの要素の検索

Question

私がしようとしているのは、各要素のレベルを取得することです。

私は現在、このコードを使用しています：

私に次のような出力を与えている

re = {0: [b.keys()[0]]} 
n = 1 
for a in b: 
    l = [] 
    for e in s[a]: 
     l.append(e) 
    if l != []: 
     re.update({n: l}) 
    n += 1 
print re 

：私はここで間違って

{"0": ["a"], "1": ["b"], "2": ["i"], "3": ["c", "d"], "4": ["f", "g", "h"], "5": ["e", "l"]} 

何をやっていますか？

あなたが再帰を使用することができます

Answer 1

いくつかの問題がここにあります

1. あなたは木の「根」を見つけるための方法として[s.keys()[0]]を使用しています。ただし、辞書は順序がないことに注意してください（CPython-3.6辞書では挿入順を使用しますが、これは実装の詳細と見なされます）。したがって、実際には[s.keys()[0]]がルートであるという保証はありません。
2. ディクショナリには1回のパスを実行しますが、ディクショナリには順序がないため、親がすでに割り当てられることは保証されません。

見つける根

は、だから我々は二つの問題を解決する必要があります。最初の問題は、別の要素の子ではないノードを探すことで解決できます。

roots = [k for k in s if k not in nonroots] 

根がある：それは子供ではない、辞書内のすべてのキーは、根であることを意味して、これらは、すべての子供であるノードです

nonroots = {c for cs in s.values() for c in cs} 

：だから我々はとしてそれを書くことができますレベル0で、私たちはそれを設定することができます。

levels[0] = roots 

ルーツ：次世代

各反復ごとに、前回の反復に対応する値を参照して次世代を構築します。

next_gen = [c for k in prev_gen for c in s.get(k,())] 

これでループに変えることができます：前世代に少なくとも1つのエレメンが含まれている限り、新しい世代を構築し続けます。だから、完全な実装は次のようになります。最後に

nonroots = {c for cs in s.values() for c in cs} 
level = [k for k in s if k not in nonroots] 
generation = 0 
result = {} 
while level: 
    result[generation] = level 
    generation += 1 
    level = [c for k in level for c in s.get(k,())] 

、resultは子のリストにすべてのレベルをマッピングした辞書です。ため

世代は、インデックス0で始まるので、私たちはより良い、代わりに辞書のリストを使用してください、と私たちは世代が私がある場合、その世代もあることを知っているI-1（ i> 0）。だから我々は、のようなリストにそれを回すことができます：我々はまた、呼び出し側はルートを提供してアプローチを使用することができます

与えられたルート（複数可）について

>>> result 
[['a'], ['b'], ['c', 'd'], ['i', 'e', 'l'], ['f', 'g', 'h']] 

：これは私たちを与える

nonroots = {c for cs in s.values() for c in cs} 
level = [k for k in s if k not in nonroots] 
result = [] 
while level: 
    result.append(level) 
    level = [c for k in level for c in s.get(k,())] 

（s）であり、この場合、我々は木を生成する。たとえば、

def get_levels(tree, roots): 
    result = [] 
    roots = list(roots) 
    while roots: 
     result.append(roots) 
     roots = [c for k in roots for c in tree.get(k,())] 
    return result 

のように、既存のアプローチを変更することができます。これで、指定ルートのリストを呼び出すことができます。場合には根が実根ではありません、私たちは与えられたツリーの下のサブツリー（複数可）のための順序を取得します：

>>> get_levels(s, ['a']) 
[['a'], ['b'], ['c', 'd'], ['i', 'e', 'l'], ['f', 'g', 'h']] 
>>> get_levels(s, ['c']) 
[['c'], ['i']] 
>>> get_levels(s, ['i','l']) 
[['i', 'l']] 
>>> get_levels(s, ['i','e']) 
[['i', 'e'], ['f', 'g', 'h']] 

Answer 2

：

from collections import defaultdict 
listing1 = defaultdict(list) 
s = {"a": ["b"], "b": ["c", "d"], "c": ["i"], "d": ["e", "l"], "e": ["f", "g", "h"], "f": [], "g": [], "h": [], "i": [], "l": []} 
def get_listing(current_node, count): 
    global listing1 
    listing1[count].append(current_node) 
    for i in s[current_node]: 
     get_listing(i, count+1) 

get_listing('a', 0) 
print(dict(listing1)) 

出力：@WillemVanOnsemと@quamranaのコメントで指摘したように、dict.keys()は、このように{0: [s.keys()[0]]}を作り、ソートされていないリストを返すこと

{0: ['a'], 1: ['b'], 2: ['c', 'd'], 3: ['i', 'e', 'l'], 4: ['f', 'g', 'h']} 

は注意をルートの開始として信頼性がありません。

Answer 3

のは、あなたがそのような辞書「D」を持っていると仮定しましょう。

d = {"a": ["b"], "b": ["c", "d"], "c": ["i"], "d": ["e", "l"], "e": ["f", "g", "h"], "f": [], "g": [], "h": [], "i": [], "l": []} 
keys=d.keys() 
keys.sort() 
def getKey(l): 
    for key,value in d.items(): 
    if l == value: 
     return key 

val=dict()# to store level of each node 
val['a']=0 
for l in keys: 
    for v in d.values(): 
    if l in v: 
    key = getKey(v) 
    val[l]=int(val.get(key,0))+1 
    print(l,val[l])