python - 如何将二叉树转换为级别字典

Question

在 python 和任何其他语言中，使用队列数据结构遍历(按级别顺序，即 BFS)二叉树是非常容易的。给定 python 中的邻接列表表示和树的根，我可以按级别顺序遍历树并按顺序打印级别元素。尽管如此，我不能做的就是从邻接列表表示转到 level_dictionary 或类似的东西:

例如我想从

adjecency_list = {'A': {'B','C'}, 'C':{'D'}, 'B': {'E'}}

至

级别 = {0: ['A'], 1: ['B','C'], 2: ['D','E']}

到目前为止，我有以下内容:

q = Queue()
o = OrderedDict()
root = find_root(adjencency_list) # Seperate function it works fine
height = find_height(root, adjencency_list) # Again works fine
q.put(root)

# Creating a level ordered adjecency list
# using a queue to keep track of pointers
while(not q.empty()):
    current = q.get()
    try:
        if(current in adjencency_list):
            q.put(list(adjencency_list[current])[0])
            # Creating ad_list in level order
            if current in o:
                o[current].append(list(adjencency_list[current])[0])
            else:
                o[current] = [list(adjencency_list[current])[0]]
        if(current in adjencency_list):
            q.put(list(adjencency_list[current])[1])
            # Creating ad_list in level order
            if current in o:
                o[current].append(list(adjencency_list[current])[1])
            else:
                o[current] = [list(adjencency_list[current])[1]]
    except IndexError:
        pass

它所做的就是将邻接列表放置在树的正确级别顺序中，如果我打印循环的开头，它将按级别顺序遍历打印。尽管如此，它并不能解决我的问题。我知道邻接列表不是树的最佳表示，但我需要将它用于我正在执行的任务。

Answer 1

从邻接列表创建级别字典的递归方法是 -

def level_dict(adj_list,curr_elems,order=0):
    if not curr_elems:    # This check ensures that for empty `curr_elems` list we return empty dictionary
            return {}   
    d = {}
    new_elems = []
    for elem in curr_elems:
            d.setdefault(order,[]).append(elem)
            new_elems.extend(adj_list.get(elem,[]))
    d.update(level_dict(adj_list,new_elems,order+1))
    return d

该方法的起始输入将是列表中的根元素，例如 - ['A'] ，以及初始级别，即 0。

在每个级别中，它都会获取该级别元素的子级并创建一个新列表，同时创建级别字典(在 d 中)。

<小时/>

示例/演示 -

>>> adjecency_list = {'A': {'B','C'}, 'C':{'D'}, 'B': {'E'}}
>>> def level_dict(adj_list,curr_elems,order=0):
...     if not curr_elems:
...             return {}
...     d = {}
...     new_elems = []
...     for elem in curr_elems:
...             d.setdefault(order,[]).append(elem)
...             new_elems.extend(adj_list.get(elem,[]))
...     d.update(level_dict(adj_list,new_elems,order+1))
...     return d
...
>>> level_dict(adjecency_list,['A'])
{0: ['A'], 1: ['C', 'B'], 2: ['D', 'E']}