Блог

Учитывая это дерево:

          7
    5         9
  _  6      8  _ 
    _ _    _ _
  

Я хочу, чтобы результат был:

 [[Node(7)], [Node(5), Node(9)], [None, Node(6), Node(8), None], [None, None, None, None]]
  

Поэтому важно, чтобы ‘None’ было включено и чтобы выходные данные представляли собой списки в виде списка.

Я много чего перепробовал, но сейчас я нахожусь именно здесь:

 class Node(object):
  def __init__(self, key, value=None):
    self.key = key
    self.value = value
    self.parent = None
    self.left_child = None
    self.right_child = None
    self.height = 0 

def breadth_first_traversal(self):
  self.height = 1
  to_do = [self.root]
  if (self.root == None):
    return to_do
  output = []
  current_height = self.height
  output.append([str(node) for node in to_do])

  while (to_do):
    done = []
    current = to_do.pop(0)
    if (current.height > current_height):
      current_height  = 1
    if (current.left_child):
      current.left_child.height = current_height   1 
      to_do.append(current.left_child)
      done.append(current.left_child)
    elif (not current.left_child):
      done.append(None)
    if (current.right_child):
      current.right_child.height = current_height   1 
      to_do.append(current.right_child)
      done.append(current.right_child)
    elif (not current.right_child):
      done.append(None) 
    output.append([str(node) for node in done])

  print(output)
  return output
  

Вывод прямо сейчас таков:

 [['7'], ['5', '9'], ['None', '6'], ['8', 'None'], ['None', 'None'], ['None', 'None']]
  

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

Одна из возможностей состоит в том, чтобы найти все узлы, включая хранение листьев None , вместе с глубинами каждого узла, а затем сгруппировать по глубинам:

Для простоты я создал двоичное дерево, которое можно легко инициализировать с помощью kwargs , вместе с методом обхода дерева и предоставления значений глубины выполнения:

 from itertools import groupby

class Node:
  def __init__(self, **kwargs):
     self.__dict__ = {i:kwargs.get(i, None) for i in ['left', 'right', 'value']}
  def get_depths(self, _count = 0):
    yield [_count, self.value]
    if self.left is not None:
      yield from self.left.get_depths(_count 1)
    else:
      yield [_count 1, None]
    if self.right is not None:
      yield from self.right.get_depths(_count 1)
    else:
      yield [_count 1, None]

tree = Node(value=7, left=Node(value=5, right=Node(value=6)), right=Node(value=9, left=Node(value=8)))
flattened = [[c for _, c in b] for _, b in groupby(sorted(list(tree.get_depths()), key=lambda x:x[0]), key=lambda x:x[0])]
  

Вывод:

 [[7], [5, 9], [None, 6, 8, None], [None, None, None, None]]
  

Поскольку вы работаете с бинарным деревом поиска, имеет смысл, что результаты объединяются с массивом в виде кортежей.

Если вы хотите объединить массивы на основе их относительной глубины, тогда вам потребуется реализовать функцию агрегатора, которая продолжает добавлять элементы в список до тех пор, пока глубина не увеличится, после чего список сохраняется и очищается для следующего набора.

В качестве альтернативы, вы могли бы передать полученный результат вспомогательной функции, которая просто объединяет элементы так, как вы хотите.

Редактировать 1: Следующее должно работать; однако я это не тестировал. Я просто переместился done за while пределы цикла, чтобы он не инициализировался повторно после каждой итерации. Кроме того, я добавляю только done в output , когда глубина увеличивается, потому что это момент, когда нет других элементов для обработки.

 class Node(object):
  def __init__(self, key, value=None):
    self.key = key
    self.value = value
    self.parent = None
    self.left_child = None
    self.right_child = None
    self.height = 0 

def breadth_first_traversal(self):
  self.height = 1
  to_do = [self.root]
  if (self.root == None):
    return to_do
  output = []
  current_height = self.height
  output.append([str(node) for node in to_do])
  done = []

  while (to_do):
    current = to_do.pop(0)
    if (current.height > current_height):
      current_height  = 1
      output.append([str(node) for node in done])
      done = []
    if (current.left_child):
      current.left_child.height = current_height   1 
      to_do.append(current.left_child)
      done.append(current.left_child)
    elif (not current.left_child):
      done.append(None)
    if (current.right_child):
      current.right_child.height = current_height   1 
      to_do.append(current.right_child)
      done.append(current.right_child)
    elif (not current.right_child):
      done.append(None) 

  print(output)
  return output