Получите все полные root -листные пути через древовидную структуру в Python - PullRequest
Новая
       16

Получите все полные root -листные пути через древовидную структуру в Python

0 голосов
/ 20 марта 2020

Я пытаюсь адаптировать этот ответ двумя способами:

  • Я хочу сделать функцию обхода методом класса, а
  • Я хочу вызов traverse для получения списка всех root путей к листам (списка списков) в дереве

Первое изменение было тривиальным, второе - с которым я борюсь. Вот мое определение класса: 

class createnode:
    """ thanks to https://stackoverflow.com/a/51911296/1870832"""
    def __init__(self,nodeid):
        self.nodeid=nodeid
        self.child=[]

    def __str__(self):
        print(f"{self.nodeid}")

    def traverse(self, path = []):
        path.append(self.nodeid)
        if len(self.child) == 0:
            #print(path)
            yield path
            path.pop()
        else:
            for child in self.child:
                child.traverse(path)
            path.pop()

Я создаю дерево с: 

ROOT_NODE = 0
root = createnode(ROOT_NODE)
lvl1 = [createnode(1), createnode(2), createnode(3)]
root.child += lvl1

root.child[0].child += [createnode(4), createnode(5)]
root.child[1].child += [createnode(6), createnode(7)]
root.child[2].child += [createnode(8), createnode(9)]

Требуемый вывод для печати всех полных root -листных путей (например, с кодом ниже) 

paths = root.traverse()
for p in paths:
    print(p)

: 

[0, 1, 4]
[0, 1, 5]
[0, 2, 6]
[0, 2, 7]
[0, 3, 8]
[0, 3, 9]

Ответы [ 2 ]

2 голосов
/ 20 марта 2020

Вам нужно посмотреть на рекурсивный генератор.

Я исправил ваш установочный код: 

class createnode:
    """ thanks to https://stackoverflow.com/a/51911296/1870832"""
    def __init__(self,nodeid):
        self.nodeid=nodeid
        self.child=[]

    def __str__(self):
        print(f"{self.nodeid}")

    def traverse(self, path = None):
        if path is None:
            path = []
        path.append(self.nodeid)
        if len(self.child) == 0:
            yield path
            path.pop()
        else:
            for child in self.child:
                yield from child.traverse(path)
            path.pop()

ROOT_NODE = 0
root = createnode(ROOT_NODE)
children = [createnode(32), createnode(5)]

root.child += children

paths = root.traverse()
for p in paths:
    print(p)

Вывод: 

[0, 32]
[0, 5]
1 голос
/ 20 марта 2020

У меня пока нет опыта с доходностью, но я бы сделал это так: 

class createnode:
    """ thanks to https://stackoverflow.com/a/51911296/1870832"""
    def __init__(self,nodeid):
        self.nodeid=nodeid
        self.child=[]

    def __str__(self):
        print(f"{self.nodeid}")

    def traverse(self, path = []):
        path.append(self.nodeid)
        if len(self.child) == 0:
            print(path)
            path.pop()
        else:
            for child in self.child:
                child.traverse(path)
            path.pop()
ROOT_NODE = 0
root = createnode(ROOT_NODE)
lvl1 = [createnode(1), createnode(2), createnode(3)]
root.child += lvl1

root.child[0].child += [createnode(4), createnode(5)]
root.child[1].child += [createnode(6), createnode(7)]
root.child[2].child += [createnode(8), createnode(9)]

root.traverse()

[0, 1, 4]

[0, 1, 5 ]

[0, 2, 6]

[0, 2, 7]

[0, 3, 8]

[0, 3 , 9]

...