如何使用Python获取树的叶节点？

Question

嗨,我是OOP的新手,所以在阅读本文时请记住这一点.

我有一个简单的Python树实现(见下面的代码).

class TreeNode(object):
    def __init__(self, data):
        self.data = data
        self.children = []

    def add_child(self, obj):
        self.children.append(obj)

class Tree:
    def __init__(self):
        self.root = TreeNode('ROOT')

    def preorder_trav(self, node):
        if node is not None:
            print node.data
            if len(node.children) == 0:
                print "("+ node.data + ")"
                for n in node.children:
                    self.preorder_trav(n)

if __name__ == '__main__':
    tr = Tree()
    n1 = tr.root
    n2 = TreeNode("B")
    n3 = TreeNode("C")
    n4 = TreeNode("D")
    n5 = TreeNode("E")
    n6 = TreeNode("F")

    n1.add_child(n2)
    n1.add_child(n3)
    n2.add_child(n4)
    n2.add_child(n5)
    n3.add_child(n6)

    tr.preorder_trav(n1)

我现在需要的是实现一个获取Leaf Nodes的方法.术语叶节点是指没有子节点的节点.

我想知道如何制作get_leaf_nodes()方法.

我想到了一些解决方案

1. 制作方法self.leaf_nodes = []内部__init__.通过这个我知道它只会被这个树实例看到.
2. 使类成员 leaf_nodes = [] 上面的__init__方法.通过这个我知道所有树实例将能够看到leaf_nodes列表.

上面的解决方案将使我在我的类中创建一个leaf_nodes列表,以便该get_leaf_nodes()方法可以使用.我要找的是只有一个get_leaf_nodes()方法可以在我的树上进行计算并返回一个列表.

例如在C中我们将调用malloc()然后我们可以返回指向调用的函数的指针get_leaf_nodes().

Answer 1

在python中,您可以使用内部函数来收集叶节点,然后返回它们的列表.

def get_leaf_nodes(self):
    leafs = []
    def _get_leaf_nodes( node):
        if node is not None:
            if len(node.children) == 0:
                leafs.append(node)
            for n in node.children:
                _get_leaf_nodes(n)
    _get_leaf_nodes(self.root)
    return leafs

如果你想要一个更干净的 OOP方法,你可以为叶子集合创建一个额外的私有方法:

def get_leaf_nodes(self):
    leafs = []
    self._collect_leaf_nodes(self.root,leafs)
    return leafs

def _collect_leaf_nodes(self, node, leafs):
    if node is not None:
        if len(node.children) == 0:
            leafs.append(node)
        for n in node.children:
            self._collect_leaf_nodes(n, leafs)

这是我用Java做的方式.