Python - Вопрос обхода дерева - PullRequest
Новая
       6

Python - Вопрос обхода дерева

6 голосов
/ 06 июня 2011

Мне тяжело с обходом дерева, и поэтому избегайте его, как чумы ... обычно.

У меня есть класс, который вроде (немного упрощенная версия здесь, но функциональното же самое) как: 

class Branch(object):
    def __init__(self, title, parent=None):
        self.title = title
        self.parent = parent

У меня есть словарь из набора Branch экземпляров, названия каждого из которых являются ключами: 

tree = {'Foo Branch': foo, 'Sub-Foo Branch': sub_foo, 'Bar Branch': bar}

Теперь я знаючто существуют сложные алгоритмы для обеспечения эффективного обхода (например, MPTT и др.), особенно для использования в проектах на основе баз данных, где эффективность важнее всего.Я вообще не использую базу данных, только простые объекты в памяти.

Учитывая title из Branch, мне нужно получить list всех потомков этой ветви (потомков), дети дети, так далее) от tree, поэтому:

  1. Вы все еще рекомендовали бы использовать сложный (для моего безалкогольного мозга:) алгоритм, такой как MPTT дляэффективность в моем случае, или есть простой способ добиться этого в одной функции?
  2. Если да, то какую из них вы бы порекомендовали, зная, что я не использую базу данных?
  3. Может лиВы приводите пример, или это намного больше, чем я думаю?

Примечание : Это не домашнее задание.Я не в школе.Я действительно так плохо разбираюсь в алгоритмах.Я использовал Django MPTT для проекта, который требовал деревьев, хранящихся в БД ... но все еще не очень хорошо это понимал.

1 Ответ

6 голосов
/ 06 июня 2011

http://en.wikipedia.org/wiki/Depth-first_search

http://en.wikipedia.org/wiki/Tree_traversal

Вы проходите следующим образом в два прохода:

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

  • Второй проход: вызвать модифицированную версию алгоритма на узле запроса, но на этот раз, когда вы посещаете узел, выведите его (или добавьте его к нелокальной переменной аккумулятора).

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

nodes = tree.values()
for node in nodes:
    if node.parent:
        if not hasattr(node.parent, 'children'):
            node.parent.children = []
        node.parent.children +=[ node ]

Теперь мы можем перейти к нашему примеру: 

def traverse(root, callback):
    """
        Peform callback on all nodes in depth-first order
        e.g. traverse(root, lambda x:print(x))
    """
    yield root, callback(root)
    for child in root.children:
        traverse(child)

def getAllDescendents(title):
    queryNode = titlesToNodes[title]  #what you call 'tree'
    for node,blah in traverse(queryNode, lambda x:None):
        yield node
...