Создание двоичного дерева

Question

Я пытаюсь создать дерево из плоского списка. Мне нужно определить функцию под названием tree_from_flat_list. Для любого узла в позиции индекса i левый ребенок сохраняется в позиции индекса 2*i, а правый ребенок хранится в позиции индекса 2*i+1. :

class BinaryTree: 

    def __init__(self, data): 
     self.data = data 
     self.left = None 
     self.right = None 

    def get_left(self): 
     return self.left 

    def get_right(self): 
     return self.right 

    def set_left(self, tree): 
     self.left = tree 

    def set_right(self, tree): 
     self.right = tree 

    def set_data(self, data): 
     self.data = data 

    def get_data(self): 
     return self.data 

    def create_string(self, spaces): 
     info = ' ' * spaces + str(self.data) 
     if self.left != None: 
      info += '\n(l)' + self.left.create_string(spaces+4) 
     if not self.right == None: 
      info += '\n(r)' + self.right.create_string(spaces+4) 
     return info  

    def __str__(self): 
     representation = self.create_string(0) 
     return representation 

def tree_from_flat_list(node_list): 
    if node_list != None: 
     root_index = 1 
     list1 = [] 
     list2 = [] 
     root = node_list[root_index] 
     left_sub_tree = list1.append(node_list[2*root_index]) 
     right_sub_tree = list2.append(node_list[2*root_index+1]) 
     tree = BinaryTree(root) 
     tree.set_left(tree_from_flat_list(left_sub_tree)) 
     tree.set_right(tree_from_flat_list(right_sub_tree)) 
     return tree 

При попытке запуска этого:

def test(): 
    flat_list = [None, 10, 5, 15, None, None, 11, 22] 
    my_tree = tree_from_flat_list(flat_list) 
    print(my_tree) 

test() 

я должен получить вывод:

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

Edit: все еще застряли на том, что я должен делать для этой функции. Любая помощь по-прежнему ценится.

Количество промежутков между ними - высота дерева, а l и r представляют, если они являются левым ребенком или правым ребенком. Это будет выглядеть так:

 10 
    /\ 
     5 15 
     /\ 
     11 22 

, но вместо этого я только получаю:

10 

Как я должен изменить свою tree_from_flat_list функцию так, что это работает. Любая помощь приветствуется. Спасибо.

Answer 1

Суть вашей проблемы в этих строках:

left_sub_tree = list1.append(node_list[2*root_index]) 
    right_sub_tree = list2.append(node_list[2*root_index+1]) 

функция устанавливает Append не возвращает ничего - он добавляет к списку. Это устанавливает левую и правую подребрами в None.

Answer 2

Формат списка представляется вариантом двоичной кучи, где элементы могут быть None. Я думаю, вы можете упростить эту совсем немного:

class BinaryTree(object): 
    def __init__(self, label, left, right): 
     self.label = label 
     self.left = left 
     self.right = right 

def tree_from_flat_list(ls, index=1): 
    if index < len(ls) and ls[index] is not None: 
     left = tree_from_flat_list(ls, 2*index) 
     right = tree_from_flat_list(ls, 2*index+1) 
     return BinaryTree(ls[index], left, right) 

Интересно, хотя, почему вы не храните левые и правые ребенок в индексах 2*i+1 и 2*i+2, как в двоичной куче; то вам не нужно иметь None в начале.