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

Question

Скажем, у меня есть список, как так:

flat_list = [None, 10, 5, 15, None, None, 11, 22] 

Я знаю, что алгоритм создания дерева из укрытого списка выглядит:

def create_tree_from_nested_list(node_list): 
    if not node_list: 
     return node_list 
    d, l, r = node_list 
    tree = BinaryTree(d) 
    tree.set_left(create_tree_from_nested_list(l)) 
    tree.set_right(create_tree_from_nested_list(r)) 
    return tree 

выход для кода выше будет:

10 
(l) 5 
(r) 15 
(l)  11 
(r)  22 

Как бы идти о создании функции для плоских списков в деревья, так что левые сохраняются в позиции индекса 2*i, а правые сохраняются в позиции индекса 2 * i + 1, а результат совпадает с выходом для вложенного списка. Любая помощь приветствуется.

Answer 1

Вы можете изменить свой код вложенного списка, чтобы работать в плоском списке. Поскольку нет простого способа разделить списки поддерева, я предлагаю вместо этого передать индекс узла, который вы хотите построить в качестве аргумента, вместе со всем плоским списком. Индекс будет иметь значение по умолчанию 1 (так что вам не нужно, чтобы передать его для корневого узла):

def create_tree_from_flat_list(node_list, index=1): 
    if index >= len(node_list) or node_list[index] is None: 
     return None 
    d = node_list[index] 
    l = index * 2 
    r = l + 1 
    tree = BinaryTree(d) 
    tree.set_left(create_tree_from_flat_list(node_list, l)) 
    tree.set_right(create_tree_from_flat_list(node_list, r)) 
    return tree 

Это вовсе не важно иметь отдельные d, l и r переменных в этой функции (они каждый может быть вычислен правильно, где они используются). Я сделал это таким образом, чтобы сделать функцию более явно параллельной версии вложенного списка. l и r - это индексы корней левого и правого поддеревьев.

Пример вывода:

> print(create_tree_from_flat_list([None, 10, 5, 15, None, None, 11, 22])) 
10 
(l) 5 
(r) 15 
(l)  11 
(r)  22