python - 如何递归遍历树并在python中创建访问节点列表

Question

我已经定义了一个类 Tree，它包含如下所示的 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，我只定义了一个父节点。但是，我想编写一个 Tree 方法，它给我一个名为 targetNodeName 的目标节点的所有父节点的列表(输出列表还应该包括 targetNodeName 本身)。为此，我编写了一个递归函数，该函数在构建名为 results 的列表时进行迭代，直到找到没有父节点的节点(即根节点)。

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

尽管它打印出正确的父节点列表——注意函数中的“调试”打印命令——(即 ['N7', 'N3', 'N1'])，该函数返回 None，这意味着我我放弃了这个功能，没有任何返回。我该如何解决这个问题？

Answer 1

使用 is 检查值是否等于 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)