Как создать бинарное дерево из списка?

[Aleksandr H.]

Дан список в котором записаны все узлы дерева, если обходить его в прямом порядке (pre-order tree walk (parent-leftChild-rightChild)). В этот обход также добавляются нулевые значения для того, чтобы обозначить отсутствие тех или иных листьев дерева

Как из списка сделать дерево которое соответсвует условию ?

Например для списка [1,4,6,10,0,0,0,7,0,8,0,0,2,5,0,0,3,9,0,0,0] ответом будет дерево как на рисунку Прикреплённый файл7_06.png (8,79 Кбайт, скачиваний: 672)

Python 2.7

[MBo]

Набросок алгоритма:

организуем стек, каждый элемент которого содержит узел дерева N и счетчик детей C (инициализируемый нулём)
Первый элемент списка кладём на стек, делаем его корнем
Для каждого последующего P: (обозначим T - текущая вершина стека)
    Если P ненулевой
          если T.C = 0
               T.N.Left = P  
          иначе если T.C = 1
               T.N.Right = P  
          иначе
               ошибка
          увеличиваем T.C
          кладём P на стек
    иначе
       T.C = T.C + 1
       пока T.C = 2
           снимать T со стека

Сообщение отредактировано: MBo - 18.05.15, 12:56

[Aleksandr H.]

Спасибо за совет. Работает если не нужны 0 как листья, в моем задании 0 должны быть листьями.

Есть такой нерабочий вариант. После создания узла 8, указатель смещается до 10 а должен к 1

# -*- coding: cp1251 -*-
class Node:
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
        self.childcount = 0
    
    
a = [1,4,6,10,0,0,0,7,0,8,0,0,2,5,0,0,3,9,0,0,0]
print "root :",a[0]
root = Node(a[0])
stack = []
stack.append(root)
tail = len(stack)-1
 
 
for i in range(1,len(a)):
    if a[i] != 0:
        if stack[tail].childcount == 0:
            stack[tail].left = Node(a[i])
 
            # output+
            if stack[tail].left != None:
                print ' '*tail,' для ',stack[tail].data,'.left  :',stack[tail].left.data
            else:
                print ' '*tail,' для ',stack[tail].data,'.left  : {Х}'
            # output-    
            stack.append(stack[tail].left)
            tail = len(stack)-1
        elif stack[tail].childcount == 1:
            stack[tail].right = Node(a[i])
 
            # output+
            if stack[tail].right != None:
                print ' '*tail,' для ',stack[tail].data,'.right :',stack[tail].right.data
            else:
                print ' '*tail,' для ',stack[tail].data,'.right : {Х}'
            # output-
            
            stack.append(stack[tail].right)
            tail = len(stack)-1
        stack[tail-1].childcount += 1
    else:
        if stack[tail].childcount:
            stack[tail].right = Node(0)
            # output+
            if stack[tail].right != None:
                print ' '*tail,' для ',stack[tail].data,'.right :',stack[tail].right.data
            else:
                print ' '*tail,' для ',stack[tail].data,'.right : {Х}'
            # output-
        else:
            stack[tail].left = Node(0)
            # output+
            if stack[tail].left != None:
                print ' '*tail,' для ',stack[tail].data,'.left  :',stack[tail].left.data
            else:
                print ' '*tail,' для ',stack[tail].data,'.left  : {Х}'
            # output-
        stack[tail].childcount += 1
        while stack[tail].childcount == 2:
            tail -= 1

Сообщение отредактировано: Aleksandr H. - 20.05.15, 11:45

[MBo]

Цитата

в моем задании 0 должны быть листьями

Да ну? А как же:

Цитата

В этот обход добавляются нулевые значения для того, чтобы обозначить отсутствие тех или иных листьев дерева

?

[amk]

Он неправильно выразился, нулевые значения у него являются являются терминальными узлами.
Но алгоритм отличается от твоего лишь тем, что, встретив ноль, надо перед переходом к следующей ветви подвесить на текущую узел с нулём.

[Aleksandr H.]

После запуска следующего кода

# -*- coding: cp1251 -*-
class Node:
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
        self.childcount = 0
    
    
a = [1,4,6,10,0,0,0,7,0,8,0,0,2,5,0,0,3,9,0,0,0]
print "root :",a[0]
root = Node(a[0])
stack = []
stack.append(root)
tail = len(stack)-1
 
 
for i in range(1,len(a)):
    if a[i] != 0:
        if stack[tail].childcount == 0:
            stack[tail].left = Node(a[i])
            stack[tail].childcount += 1
            print ' '*tail,' для ',stack[tail].data,'.left  :',stack[tail].left.data
            stack.append(stack[tail].left)
            tail = len(stack)-1
        elif stack[tail].childcount == 1:
            stack[tail].childcount += 1
            stack[tail].right = Node(a[i])
            print ' '*tail,' для ',stack[tail].data,'.right :',stack[tail].right.data
            stack.append(stack[tail].right)
            tail = len(stack)-1
    else:
        if stack[tail].childcount:
            stack[tail].right = Node(0)
            stack[tail].childcount += 1
            print ' '*tail,' для ',stack[tail].data,'.right :',stack[tail].right.data
        else:
            stack[tail].left = Node(0)
            stack[tail].childcount += 1
            print ' '*tail,' для ',stack[tail].data,'.left  :',stack[tail].left.data
        while stack[tail].childcount == 2:
            tail -= 1

получаю такой результат

root : 1
  для  1 .left  : 4
   для  4 .left  : 6
    для  6 .left  : 10
     для  10 .left  : 0
     для  10 .right : 0
    для  6 .right : 0
   для  4 .right : 7
      для  7 .left  : 0
      для  7 .right : 8
       для  8 .left  : 0
       для  8 .right : 0
  для  1 .right : 2
        для  2 .left  : 5
         для  5 .left  : 0
         для  5 .right : 0
        для  2 .right : 3
          для  3 .left  : 9
           для  9 .left  : 0
           для  9 .right : 0
          для  3 .right : 0
 
Traceback (most recent call last):
  File "E:\Dropbox\20052015.py", line 59, in <module>
    while stack[tail].childcount == 2:
IndexError: list index out of range

Сообщение отредактировано: Aleksandr H. - 21.05.15, 05:43

[MBo]

в while нужно добавить очевидное условие окончания, опустошение стека tail >=0