На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
Модераторы: RaD
  
    > Как создать бинарное дерево из списка?
      Дан список в котором записаны все узлы дерева, если обходить его в прямом порядке (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 Кбайт, скачиваний: 669)

      Python 2.7
        Набросок алгоритма:
        ExpandedWrap disabled
          организуем стек, каждый элемент которого содержит узел дерева 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 -
          Спасибо за совет. Работает если не нужны 0 как листья, в моем задании 0 должны быть листьями.

          Есть такой нерабочий вариант. После создания узла 8, указатель смещается до 10 а должен к 1 :(
          ExpandedWrap disabled
            # -*- 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. -
            Цитата
            в моем задании 0 должны быть листьями

            Да ну? А как же:
            Цитата
            В этот обход добавляются нулевые значения для того, чтобы обозначить отсутствие тех или иных листьев дерева

            ?
              Он неправильно выразился, нулевые значения у него являются являются терминальными узлами.
              Но алгоритм отличается от твоего лишь тем, что, встретив ноль, надо перед переходом к следующей ветви подвесить на текущую узел с нулём.
                После запуска следующего кода
                ExpandedWrap disabled
                  # -*- 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


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

                ExpandedWrap disabled
                  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. -
                  в while нужно добавить очевидное условие окончания, опустошение стека tail >=0
                  0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                  0 пользователей:


                  Рейтинг@Mail.ru
                  [ Script execution time: 0,0312 ]   [ 17 queries used ]   [ Generated: 28.03.24, 13:40 GMT ]