генерирование двоичного дерева из заданных данных в 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), узел (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)