Как найти связанные узлы в дереве (не бинарном)?

#python

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

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

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

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 часа, возможно, глаз замылился, извините. Буду рад, если
кто-то поправит.