如何使用Python获取树的叶子节点? [英] How to get leaf nodes of a tree using Python?

问题描述

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

Hi there I am new to OOP so have this in mind while you are reading this.

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

I have a simple Python tree implementation(see below code).

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)

我现在需要的是实现一种使叶子节点恢复原状的方法.术语叶子节点是指没有子节点的节点.

What I need now is to implement a method for getting Leaf Nodes back. By the term leaf node I mean a node that has no children.

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

I am wondering how to make a get_leaf_nodes() method.

我想到的一些解决方案是

Some solutions come to my mind are

1. 在__init__方法内制作一个self.leaf_nodes = [].通过这样做，我知道只有该树实例才能看到它.
2. 使类成员leaf_nodes = []在__init__方法之上.通过这样做，我知道所有树实例都将能够看到leaf_nodes列表.

1. Making a self.leaf_nodes = [] inside the __init__ method. By making this I know it will be seen only by this tree instance.
2. Making a class member leaf_nodes = [] above __init__ method. By making this I know all tree instances will be able to see leaf_nodes list.

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

The above solutions will cause me to create a leaf_nodes list inside my class so the get_leaf_nodes() method could use. What I am looking for is to only have a get_leaf_nodes() method that will do the computation on my tree and will return a list.

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

For example in C we would call malloc() and then we could return the pointer to the function that called the get_leaf_nodes().

推荐答案

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

In python you can use an internal function to collect the leaf nodes and then return the list of them.

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

如果您想要一种更 clean 的OOP方法，则可以为叶子的收集创建一个额外的私有方法:

If you want a more clean OOP approach you can create an extra private method for the collection of leafs:

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中执行此操作的方式.

This is the way I'd do it in Java.

这篇关于如何使用Python获取树的叶子节点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！