Python рекурсия через объекты и дочерние объекты, печать дочерних чисел глубины

Question

У меня есть простой класс с атрибутом, который может содержать список объектов того же класса

class BoxItem:
  def __init__(self, name, **kw):
      self.name = name
      self.boxItems = []
      ... #more attributes here

box1 = BoxItem('Normal Box')
box2 = BoxItem('Friendly Box')
box3 = BoxItem('Cool Box')
box4 = BoxItem('Big Box', [box1, box2]) #contains some children
example = BoxItem('Example Box', [box4,box3]) #contains another level of children

Работая с нашим «блочным» объектом-примером, я бы хотел провести маневрирование по глубине всех возможных дочерних блоков, которые он может иметь, и распечатать объекты, отформатированные так:

1 Example Box
 1.1 Big Box
  1.1.1 Normal Box
  1.1.2 Friendly Box
 1.2 Cool Box

Вкладка между ними не нужна, просто нужно четко показать формат дерева. Я могу пройтись по самим объектам и распечатать их названия, но я не могу распечатать первые числа, которые показывают отношения родитель / ребенок. (1, 1,1, 1,2 ...)

Заранее спасибо за помощь:)

Редактировать Вот с чем я работал до сих пор

def print_boxes(box_list):
  node_count = 0
  for box in box_list:
    node_count += 1
    print str(node_count)+' '+box.name #prints out the root box
    recursive_search(box,node_count)

 def recursive_search(box,node_count): #recursive automatically 
  level = 0
  for child in box.boxItems:
    level += 1
    for x in range(len(child.boxItems)):
      print x+1 #this prints out some proper numbers
    print "level: "+str(level) #experiment with level
    print child.name #prints out child box name
    recursive_search(child,node_count) #runs the function again  inside the function

Answer 1

Я думаю, что для вас может быть более полезным, если я опубликую рабочий пример того, как это сделать, вместо того, чтобы разбираться с проблемами, возникающими в коде. Таким образом, мы могли бы достичь понимания намного быстрее. Ваш код имеет правильное представление о том, что он должен отслеживать глубину по мере продвижения. Но единственное, чего не хватает, - это чувства вложенной глубины (дерева). Он знает только предыдущий node_count, а затем его текущий дочерний счет.

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

def recurse(box):

    boxes = not isinstance(box, (list, tuple)) and [box] or box

    depth = [1]

    def wrapped(box):

        depthStr = '.'.join([str(i) for i in depth])
        print "%s %s" % (depthStr, box.name)

        depth.append(1)
        for child in box.boxItems:
            wrapped(child)
            depth[-1] += 1
        depth.pop()

    for box in boxes:
        wrapped(box)
        depth[0] += 1

Пример вывода из ваших примеров:

>>> recurse(example)
1 Example Box
1.1 Big Box
1.1.1 Normal Box
1.1.2 Friendly Box
1.2 Cool Box

>>> recurse([example, example])
1 Example Box
1.1 Big Box
1.1.1 Normal Box
1.1.2 Friendly Box
1.2 Cool Box
2 Example Box
2.1 Big Box
2.1.1 Normal Box
2.1.2 Friendly Box
2.2 Cool Box

Разбить это:

Сначала мы принимаем аргумент блока и автоматически преобразуем его локально в список, если вы передали только один элемент блока. Таким образом, вы можете передать либо один блок объектов, либо их список / кортеж.

depth - наш трекер глубины. Это список целых чисел, которые мы будем наращивать и уменьшать по мере рекурсии. Начинается с 1 для первого предмета / первого уровня. Со временем это может выглядеть так: [1,1,2,3,1] в зависимости от того, как глубоко он проходит. В этом главное различие между моим и вашим кодом . Каждая рекурсия имеет доступ к этому состоянию.

Теперь у нас есть эта внутренняя wrapped функция. Он собирается взять текущий элемент box и распечатать его, а затем перебрать его дочерние элементы. Мы получаем нашу строку для печати, присоединяясь к текущему списку глубины, а затем к имени.

Каждый раз, когда мы выпадаем в дочерний список, мы добавляем начальный уровень 1 в наш список глубины, и когда мы выходим из этого дочернего цикла, мы снова его отключаем. Для каждого дочернего элемента в этом цикле мы увеличиваем этот последний элемент.

За пределами этой wrapped внутренней функции мы затем запускаем все это, перебирая наши начальные блоки, вызывая wrapped и затем увеличивая наш первый уровень.

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

Примечание об аргументах для функции

Мы могли бы также спроектировать recurse, чтобы вместо этого принимать список аргументов переменной длины вместо проверки списка. Это выглядело бы так (и избавилось бы от первой проверки boxes =):

def recurse(*boxes):
    #boxes will always come in as a tuple no matter what

>>> recurse(example)
>>> recurse(example, example, example)

И если вы изначально начинаете со списка элементов ящика, вы можете передать его, выполнив:

>>> boxes = [example, example, example]
>>> recurse(*example)    # this will unpack your list into args

Answer 2

У вас есть два варианта:

1. Отслеживайте дополнительную информацию в качестве дополнительного параметра в вашей рекурсии, например, myRecursiveFunction(..., ancestry=[])
2. Пусть каждый BoxItem отслеживает своего родителя всякий раз, когда он внедряется в BoxItem (в конструкторе __init__ установите child.parent = self для каждого дочернего элемента). Это плохо, если вы планируете использовать BoxItem более чем в одном боксе.