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

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

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

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 и др.), особенно для использования с проектами, управляемыми базами данных, где эффективность важнее всего. Я вообще не использую базу данных, а только простые объекты в памяти.

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

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

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

7
задан orokusaki 6 June 2011 в 04:33
поделиться