генерация двоичного дерева из данных в python

Question

Я хотел знать, как читать значения из списка в двоичное дерево. у меня есть треугольник, как это:

  0 
     1 2 
    3 4 5 
    6 7 8 9 

я написал узел класса как этот

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

в основном то, что я хочу сделать что-то вроде этого

узел (0, узел (1), node (2))

Я хочу сделать рекурсивную функцию, которая может обрабатывать гораздо большие треугольники. Может мне как-то сказать, что я должен делать?

Редактировать: довольно четко бинарное дерево - это не способ приблизиться к этой проблеме. то, что я в основном хочу узнать, - это все разные комбинации сверху донизу. как 0,1,3,6 0,2,5,8 и т.д.

Answer 1

Это звучит как домашнее задание, поэтому я не буду писать код, но вот несколько подсказок:

1. Это может быть сделано, даже если ваш треугольник были написаны в виде списка, как 0 1 2 3 4 5 6 7 8 9

2. Потому что кажется, что это полное бинарное дерево (предполагается, что ваш треугольник является неправильным, а третья строка на самом деле должен быть 3 4 5 6), вы можете сохранить очередь parents, голова которой является следующим родителем, которому нужны дети. Обратите внимание, что я специально не рекомендую рекурсию.

Полное двоичное дерево - это то место, где каждый нелистовой узел имеет ровно два ребенка. Если это не должно быть полным двоичным деревом, то нет детерминированного способа интерпретировать проблему (так как каждый из узлов 1 и 2 может иметь 1 или 2 детей, учитывая ваше изображение).

Answer 2

Для такого списка:

a = 'aBCdef' 

Программа ниже генерирует следующую структуру:

- a - 
- B C 
B C - 
- d e 
d e f 
e f - 

(предполагается список входов, чтобы соответствовать 'полной' треугольной)

Код:

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

    def __unicode__(self): 
     return '%s %s %s' % (
       self.left.data if self.left or '-', 
       self.data, 
       self.right.data if self.right or '-') 


nodelist = [Node(c) for c in a] 

i,y = 0,1 

while True: 
    for x in range(y): 
     nodelist[i].left = nodelist[i-1] if x!=0 else None 
     nodelist[i].right = nodelist[i+1] if x!=y-1 else None 
     i+=1 
    if i<len(a): 
     y+=1 
    else: 
     break 

for n in nodelist: 
    print unicode(n)