Проблемы с рекурсивными вызовами при построении структуры данных Tree

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

Вот мой код.

class Node:
    def __init__(self, data, children=list()):
        self.data = data
        self.children = children

    def __eq__(self, node):
        return self.data == node.data

    def __str__(self):
        return self.data

    def __repr__(self):
        return self.data

    def write_xtl(self, node, out_file, level=0):
        gen2 = self.traverse(node)
        for child in gen2:
            out_file.write(child.data)

    def traverse(self, node, path=list()):
        yield self
        for n in self.children:
            for m in traverse(n, path):
                yield m

    def find(self, node):
        if self == node:
            return self
        else:
            for child in self.children:
                return child.find(node)

    def add(self, node, value):
        entry_point = self.find(node)
        if entry_point:
            #print ("Found %s in %s") % (value.data.rstrip(), node.data.rstrip())
            #print ("\tentry_point is %s") % (entry_point.data)
            entry_point.children.append(value)
        else:
            print ("Could not find %s") % (value)

Вот мой тестовый файл:

from xtensiltree import tree
root = tree.Node("root\n")
header = tree.Node("header\n")
orderHeader = tree.Node("orderHeader\n")
date = tree.Node("date\n")
notes = tree.Node("notes\n")
address = tree.Node("address\n")
contacts = tree.Node("contacts\n")

root.add(root, header)
root.add(header, orderHeader)
root.add(orderHeader, date)
root.add(orderHeader, notes)
root.add(orderHeader, address)
root.add(address, contacts)

outfile = open("ooutput.xtl", "w")
root.write_xtl(root, outfile)
outfile.close()

Заранее спасибо.


python-2.7 tree tail-recursion
person qream    schedule 13.05.2014    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Вот пример того, как должен выглядеть метод find.

def find(self, node):
    if self == node:
        return self
    elif self.children != []:
        for child in self.children:
            found = child.find(node)
            if found:
                return found
    return None

По сути, это означает: если текущий узел — это то, что мы ищем, то вернуть его. Если нет, и у текущего узла есть дочерние элементы, которые ищут их. Если он был найден в одном из дочерних элементов, он будет возвращен, в противном случае возвращается None.

person Tiero    schedule 13.05.2014
comment
К сожалению, это тоже не работает с моим кодом. Я пробовал различные итерации моего метода find и пытался увеличить предел рекурсии. Не знаю, почему максимальная глубина рекурсии достигается все время. - person qream; 13.05.2014

arrow_upward
0
arrow_downward

Моя проблема была с моим методом init().

def инициализация(я, данные, дети=список()):

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

В свою очередь, любые рекурсивные функции будут продолжаться вечно.

Спасибо за помощь Тиеро.

person qream    schedule 13.05.2014