Итеративная печать модели дерева

Question

У меня есть дерево таких узлов:

class Node:
    next        # the next node or None
    prev        # the previous node or None
    parent      # the parent or None
    children[]  # ordered list of child nodes
    columns[]   # a list of data. Currently only holdt the 
                # string representation of the node in the model.

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

- 0
-- 0:0
--- 0:0:0
--- 0:0:1
---- 0:0:1:0
---- 0:0:1:1
--- 0:0:2
-- 0:1
- 1

Но вот что он делает print:

- 0
-- 0:0
-- 0:1
-- 0
- 1
--- 0:0:0
--- 0:0:1
--- 0:0:2
-- 0:1
-- 0
- 1
--- 0:0:1
---- 0:0:1:0
---- 0:0:1:1
--- 0:0:2
-- 0
---- 0:0:1:0
---- 0:0:1:1
--- 0:0:2
---- 0:0:1:1
---- 0:0:1:1

Вот код, который я написал:

def print_tree(from_path):
    nodelist = []
    root_node = model.get_iter(from_path)
    nodelist.append((root_node, 0)) # the second item in the tuple is the indentation

    while nodelist:
        node = nodelist[0][0]
        indent = nodelist[0][1]
        del(nodelist[0])
        print("{0} {1}".format("-" * indent, node.columns[0])) 

        if node.children:
            child = node.children[0]
            nodelist.append((child, indent +1))

            while child.next:
                nodelist.append((child.next, indent +1))
                child = child.next
        if node.next:
            next = node.next
            nodelist.append((next, indent))

Любая помощь очень ценится.

Answer 1

Как отмечает mgibsonbr, поскольку вы храните родительский указатель, это можно сделать итеративно, отслеживая только текущий узел (и его отступ):

def print_tree(from_path):

    node, indent = model.get_iter(from_path), 0

    while node:

        if indent:           # don't print the root
            print "-" * indent, node.columns[0]

        if node.children:    # walk to first child before walking to next sibling
            node = node.children[0]
            indent += 1
        elif node.next:      # no children, walk to next sibling if there is one
            node = node.next
        else:
            # no children, no more siblings: find closet ancestor w/ more siblings
            # (note that this might not be the current node's immediate parent)
            while node and not node.next:
                node = node.parent
                indent -= 1
            node = node and node.next            

Вы можете превратить это в генератор, заменив строку print на yield indent, node.

Мне пришлось смоделировать некоторые тестовые данные, чтобы отладить это. Вот что у меня есть, на случай, если кто-то еще захочет поиграть. Я рассматривал корень как неспособный иметь братьев и сестер (нет причин, по которым он не может иметь next и хранить данные в columns, но тогда вы захотите, чтобы ваши отступы начинались с 1).

class Node(object):
    def __init__(self, parent=None, sib=None, value=""):
        self.parent   = parent
        self.prev     = sib
        self.next     = None
        self.children = []
        self.columns  = [str(value)]
    def child(self, value):
        child = Node(self, None, value)
        if self.children:
            self.children[-1].next = child
            child.prev = self.children[-1]
        self.children.append(child)
        return child
    def sib(self, value):
        return self.parent.child(value)

class model(object):
    @staticmethod
    def get_iter(_):

        root = Node()

        root.child("0").child("0:0").child("0:0:0").sib("0:0:1") \
            .child("0:0:1:0").sib("0:0:1:0").parent.sib("0:0:2")
        root.children[0].child("0:1").parent.sib("1")

        return root

Answer 2

Поскольку каждый узел имеет ссылку на своего родителя, я думаю, что вы можете пройти по всему дереву, сохраняя в памяти только один узел за раз.У меня возникли проблемы с пониманием вашего кода (в частности, как каждый узел загружается в память), поэтому я опубликую свое предложение в псевдокоде:

def visit(node,indent):
    # Load your node data
    print("{0} {1}".format("-" * indent, node.columns[0])) # Do something with your data
    # Unload your node data
    if len(node.children) > 0 :
        return (node.children[0], indent+1) # Visit the first child, if there is one
    while node.next is None: # If no sibling, your parent is done
        node = node.parent
        indent -= 1
        if node is None: # Root node reached, end the traversal
            return None
    return (node.next, indent) # Visit your next sibling, if there is one

cursor = (root_node, 0)
while cursor is not None:
    cursor = visit(*cursor)

Если сам узел должен быть загружен динамически(т. е. next, prev, parent и children содержат только путь к данным другого узла, а не ссылку на объект Node), скажите мне, и я обновлю ответ (просто нужнонемного поменять места для погрузки / выгрузки).Конечно, если выгрузка - это просто вопрос оставления объекта в сборщике мусора, это еще проще ...