python - 在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. 您对字典执行了一次传递，但同样由于字典是无序的，因此不能保证已经分配了父项。

寻根

所以我们需要解决这两个问题。第一个可以通过查找不是另一个元素的子节点的节点来解决。所以我们可以这样写:

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

这些都是子节点，所以这意味着字典中所有不在子节点中的键都是根:

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

根在 0 层，因此我们可以将其设置为:

levels[0] = roots

根:下一代

现在对于每次迭代，我们通过查找与前一次迭代对应的值来构造下一代。

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

所以现在我们可以把它变成一个循环:只要上一代至少包含一个元素，我们就会继续构建新的一代。所以一个完整的实现是:

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，则有也是一代i-1(对于i > 0)。所以我们可以把它变成一个像这样的列表:

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,())]

这给了我们:

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

对于给定的根

我们还可以使用调用者提供根的方法，在这种情况下我们会生成一棵树。我们可以改变现有的方法，例如:

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']]