Все пути дерева

Question

Как можно продолжить перечисление всех путей в дереве с помощью рекурсии?

Я называю это в оболочке:

t = Tree(1) 
t2 = Tree(2) 
t7 = Tree(7), t2.children = [t7] 
t5 = Tree(5) 
t9 = Tree(9) 
t8 = Tree(8) 
t5.children = [t8, t9] 
t.children = [t5, t2] 

В основном я сделал это дерево выглядит так:

 1 
/ \ 
    2 5 
    | /\ 
    7 9 8 

Я хочу вернуть следующие пути в списке:

[[1, 2, 7], [1, 5, 9], [1, 5, 8]] 

В целом я могу составить список, это просто найти способ получить конкретный путь, который я изо всех сил пытаюсь сделать! Поблагодарили бы за любую помощь!

Answer 1

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

class Tree: 
    def __init__(self, value): 
     self.value = value 
     self.children = [] 


def get_paths(t, paths=None, current_path=None): 
    if paths is None: 
     paths = [] 
    if current_path is None: 
     current_path = [] 

    current_path.append(t.value) 
    if len(t.children) == 0: 
     paths.append(current_path) 
    else: 
     for child in t.children: 
      get_paths(child, paths, list(current_path)) 
    return paths 


t = Tree(1) 
t2 = Tree(2) 
t7 = Tree(7) 
t2.children = [t7] 
t5 = Tree(5) 
t9 = Tree(9) 
t8 = Tree(8) 
t5.children = [t9, t8] 
t.children = [t2, t5] 

print get_paths(t) 

Выход:

[[1, 2, 7], [1, 5, 9], [1, 5, 8]] 

@Shashank спасибо за угадывание возможной структуры Tree

Answer 2

Здесь есть способ сделать это с помощью полностью неизменные объектами, кортежами, и никаких аргументов, помимо дерева. Вместо использования измененного списка для хранения состояния мы просто передаем значения, привязанные к вершине, по цепочке. get_paths обязан возвращать кортеж кортежей каждый раз.

class Tree: 
    def __init__(self, value): 
     self.value = value 
     self.children =() 


def get_paths(t): 
    if t.children: 
     return tuple((t.value,) + path 
      for child in t.children 
       for path in get_paths(child)) 
    else: 
     return ((t.value,),) 


t = Tree(1) 
t2 = Tree(2) 
t3 = Tree(3) 
t4 = Tree(4) 
t5 = Tree(5) 
t6 = Tree(6) 
t7 = Tree(7) 
t8 = Tree(8) 
t9 = Tree(9) 
t.children = (t2, t5) 
t2.children = (t7,) 
t5.children = (t9, t8) 
t9.children = (t6,t3,t4) 

print(get_paths(t)) 

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

Чтобы преобразовать его в список структуры списков, вы можете просто сделать:

paths = [list(path) for path in get_paths(t)] 

Или просто заменить все кортежи в функции со списками, и вы хорошо идти!