Как преобразовать двоичное дерево в словарь уровней

Question

В python и любом другом языке довольно легко выполнить (в порядке уровня так BFS) двоичное дерево, используя структуру данных очереди. Учитывая представление списка смежности в python и корень дерева, я могу перемещать дерево в порядке уровня и элементы уровня печати по порядку. Тем не менее то, что я не могу сделать, это перейти от представления списка adjecency к level_dictionary или что-то любит:

так, например, я хотел бы перейти от

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

в

levels = {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).

---

Пример/Demo -

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