4

в данный момент хочу понять как найти все связанные узлы в дереве.

Вот примерный код:

class Tree:

    def __init__(self, root, subtrees=None):
        self.root = root
        self.subtrees = subtrees[:] if subtrees else []


    def con(self, v1, v2):
        # base cases
        if v1 and v2 is None:
            return []
        elif self.root is None:
            return []
        elif v1 == v2:
            return [v1]
        else:
            path = []
            for subtree in self.subtrees:
                path += subtree.con(v1, v2)
            return path

Как пройтись рекурсией по всем элементам дерева? Потому что в моем коде только по ветвям проходит, и из-за этого ответ в виде пустого списка. Я не могу понять как найти узлы вместе с корнем.

Output должен быть в роде:

t1 = Tree(2, [Tree(5)])

t2 = Tree(4, [Tree(6), Tree(7)])

t = Tree(1, [t1, t2])

print(t.con(5,4))

5, 2, 1, 4

1
  • 2
    Добавьте пример входных данных, как происходит инициализация класса и что должно получиться на выходе? 10 июл 2018 в 6:53

1 ответ 1

4
class Tree:

    def __init__(self, root, subtrees=None):
        self.root = root
        self.subtrees = subtrees[:] if subtrees else []

    def con(self, v1, v2, path = []):
        if (v1 is None and v2 is None) or (self.root is None):
            return []
        elif v1 == v2:
            return [v1]
        elif self.root != v1 and self.root != v2:
            path.append(self.root);
            for sub in self.subtrees:
                sub.con(v1, v2, path)
        elif self.root == v1:
            path.append(v1)
        elif self.root == v2:
            path.append(v2)
        return path

Ну вот что-то в таком духе (извините, я не понял, важен ли вам порядок следования элементов, если что, можно подумать, как переделать).

Суть такая: мы запускаем рекурсию из корня дерева и идем по всем поддеревьям, запускаю рекурсию от них, пока не встретим нужную нам вершину, попутно записывая все вершины в path.

У этого подхода есть явный минус: t.con(5, 1) выдаст просто 1

Поэтому давайте кое-что поменяем:

class Tree:

    parent = None

    def __init__(self, root, subtrees=None):
        self.root = root
        self.subtrees = subtrees[:] if subtrees else []
        if subtrees:
            for sub in subtrees:
                sub.parent = self;

    def find(self, path = []):
        if self.root is None:
            return path
        else:
            if not (self.root in path): path.append(self.root)
            if self.parent: self.parent.find(path)

    def con(self, v1, v2, path = []):
        if (v1 is None and v2 is None) or (self.root is None):
            return []
        elif v1 == v2:
            return [v1]
        elif self.root != v1 or self.root != v2:
            for sub in self.subtrees:
                sub.con(v1, v2, path)
        if self.root == v1:
            self.find(path)
        elif self.root == v2:
            self.find(path)
        return path

Будем хранить предка каждого поддерева. В рекурсии же мы сперва опустимся до нужных корней, а от них запустим другую рекурсию до самого верха, и именно вторая рекурсия будет прописывать path.

Но и тут есть проблема: t.con(5, 2) выведет [5, 2, 1] вместо [5, 2] Поэтому я написал вот такой костыль:

class Tree:

    parent = None

    def __init__(self, root, subtrees=None):
        self.root = root
        self.subtrees = subtrees[:] if subtrees else []
        if subtrees:
            for sub in subtrees:
                sub.parent = self;

    def find(self, v1, v2, path = [], first = False):
        if self.root is None:
            return path
        else:
            if not (self.root in path): 
                path.append(self.root)
            else:
                return path
            if self.parent and (self.root != v1 and self.root != v2 or first): 
                self.parent.find(v1, v2, path)

    def con(self, v1, v2, path = [], par = False):
        if (v1 is None and v2 is None) or (self.root is None):
            return []
        elif v1 == v2:
            return [v1]

        if self.root == v1:
            if par: 
                self.find(v1, v2, path, True)
                if self.root != v1 or self.root != v2:
                    for sub in self.subtrees:
                        sub.con(v1, v2, path, True)
            else:
                if self.root != v1 or self.root != v2:
                    for sub in self.subtrees:
                        sub.con(v1, v2, path, False)
                self.find(v1, v2, path, True)

        elif self.root == v2:
            if par: 
                self.find(v1, v2, path, True)
                if self.root != v1 or self.root != v2:
                    for sub in self.subtrees:
                        sub.con(v1, v2, path, True)
            else:
                if self.root != v1 or self.root != v2:
                    for sub in self.subtrees:
                        sub.con(v1, v2, path, False)
                self.find(v1, v2, path, True)

        elif self.root != v1 or self.root != v2:
            for sub in self.subtrees:
                sub.con(v1, v2, path, False)


        return path

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

Может, костыль можно оставить, но как-то перемешать элементы кода и получится компактнее, но я пишу это уже почти 2 часа, возможно, глаз замылился, извините. Буду рад, если кто-то поправит.

2
  • Спасибо большое! Выглядит очень занятно. Все-таки с бинарными деревьями намного легче все это находить.
    – User007
    10 июл 2018 в 14:40
  • Пожалуйста. Думаю, есть некое плюс-минус "эталонное" решение лучше моего, но я не смог найти каких-то конкретных алгоритмов на эту тему. 10 июл 2018 в 14:49

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.