Как рекурсивно пройти дерево и создать список посещенных узлов в питоне

Question

Я определил дерево класса, который состоит из списка TreeNodes, как показано ниже:

class Tree(object): 
    def __init__(self, name, nodes): 
     self.name = name 
     self.nodes = nodes 

class TreeNode(object): 
    def __init__(self, name, parent): 
     self.name = name 
     self.parent = parent 

Как вы можете видеть, для каждого TreeNode I только определить один родительский узел. Однако я хочу написать метод Tree, который дает мне список всех родительских узлов целевого узла с именем targetNodeName (список вывода также должен включать имя targetNodeName). Для этого я написал рекурсивную функцию, которая выполняет итерацию до тех пор, пока не будет найден узел без родителя (т. Е. Корневой узел) при построении списка, называемого результатами.

def allParents(self, targetNodeName, results): 
    currentNode = next((node for node in self.nodes if node.name == targetNodeName)) 
    results.append(currentNode.name) 
    if (currentNode.parent == None): 
     print results 
     return results 
    else: 
     return results.append(self.allParents(currentNode.parent, results)) 

Однако моя рекурсивная функция не работает должным образом. Я приведу пример, когда я сначала определяю трехуровневое дерево с 7 узлами, а затем вызываю метод allParents для получения всех родительских узлов узла «N7», т. Е. ['N7', 'N3', 'N1'].

# create nodes 
myTreeNodes = [] 
myTreeNodes.append(TreeNode(name = 'N1', parent = None)) 
myTreeNodes.append(TreeNode(name = 'N2', parent = 'N1')) 
myTreeNodes.append(TreeNode(name = 'N3', parent = 'N1')) 
myTreeNodes.append(TreeNode(name = 'N4', parent = 'N2')) 
myTreeNodes.append(TreeNode(name = 'N5', parent = 'N2')) 
myTreeNodes.append(TreeNode(name = 'N6', parent = 'N3')) 
myTreeNodes.append(TreeNode(name = 'N7', parent = 'N3')) 

myTree = Tree(name = 'ST1', nodes = myTreeNodes) 

a = myTree.allParents(targetNodeName = 'N7', results = []) 
print a 

> ['N7', 'N3', 'N1'] 
> None 

Хотя он печатает правильный список родительских узлов -Примечание-х отладки "команду печати в FUNCTION- (т.е. [«N7»,«N3»,«N1»]), функция возвращает None , что означает, что я потерял функцию, и ничего не вернулось. Как я могу это исправить?

Answer 1

Использовать является для проверки того, равна ли значение None или нет. В allParents метод может быть упрощена следующим образом:

def allParents(self, targetNodeName): 
    currentNode = next(node for node in self.nodes 
         if node.name == targetNodeName) 
    if currentNode.parent is None: 
     return [currentNode.name] 
    else: 
     return [currentNode.name] + self.allParents(currentNode.parent) 

Answer 2

Выполнение метода с использованием debugger очень полезно при разработке пути, который принимает код.

Используя это, я вижу, что метод изначально следует за веткой else, это только дочерний вызов self.allParents, который вызывает оператор печати. Проблема заключается в results.append, который всегда возвращает None, а не список.

a = [] 
b = a.append(3) 
assert a == [3] 
assert b is None 

Самым простым решением было бы разделить строку в исходный results.append, а затем return results.