Python: 递归不迭代列表的所有元素

Question

我有以下方法，其中 self 包含如下数据结构

self.place = "India"
self.children = ["Tamil Nadu", "Karnataka"]
self.parent

方法

    def get_node(self, value):
        if value is None:
            return self

        if self.place == value:
            return self

        for node in self.children:
            if node.place == value:
                return node
            elif len(node.children) > 0:
               return node.get_node(value)

因此，通过递归，我在所有可能的子节点上迭代，以通过 return node.get_node(value) 找到我正在寻找的节点，但我观察到，迭代是通过“泰米尔纳德邦”而不是“卡纳塔克邦”发生的。

我明白了，它获取了列表的第一个元素，然后从那里继续，但没有返回到列表的第二个元素。

这是递归的预期行为还是我做错了什么？

完整代码（以备测试需要）

class TreeNode:

    def __init__(self, place):
        self.place = place
        self.children = []
        self.parent = None

    def add_child(self, child):
        child.parent = self
        self.children.append(child)

    def print_tree(self):

        prefix = ""
        if self.parent is None:
            print(self.place)
        else:
            prefix = prefix + (" " * self.get_level() * 3)
            prefix = prefix + "|__"
            print(prefix + self.place)

        for child in self.children:
            child.print_tree()
    def get_level(self):
        level = 0
        p = self.parent
        while p:
            level = level + 1
            p = p.parent
        return level

    def get_node(self, value):
        if value is None:
            return self

        if self.place == value:
            return self

        for node in self.children:
            if node.place == value:
                return node
            elif len(node.children) > 0:
               return node.get_node(value)

    def tree_map(self, nodes):
        for node in nodes:
            self.add_child(TreeNode(node))


def build_places():

    root = TreeNode("Global")

    india = TreeNode("India")
    usa = TreeNode("USA")

    root.add_child(india)
    root.add_child(usa)

    india_nodes = ["Gujarat" ,"Karnataka"]
    gujarath_nodes = [ "Ahmedabad", "Baroda"]
    karnataka_nodes = ["Bangalore", "Mysore"]
    usa_nodes = ["New Jersey", "California"]
    newjersey_nodes = ["Princeton", "Trenton"]
    california_nodes = ["San Franciso", "Mountain View", "Palo Alto"]

    for node in india_nodes:
        india.add_child(TreeNode(node))
    for node in usa_nodes:
        usa.add_child(TreeNode(node))

    gujarath_node = root.get_node("Gujarat")
    print(gujarath_node.place)
    for node in gujarath_nodes:
        gujarath_node.add_child(TreeNode(node))
    karnataka_node = root.get_node("Karnataka")
    print(karnataka_node.place)
    return root


if __name__ == "__main__":
    root = build_places()
    root.print_tree()

Answer 1

问题是在你的循环中你总是在它的第一次迭代中退出循环（当节点至少有一些children）。您应该只在成功时退出，而不是在递归调用未成功返回时退出。

因此将循环更改为：

        for node in self.children:
            if node.place == value:
                return node
            elif len(node.children) > 0:
                result = node.get_node(value)
                if result:
                    return result

其次，您在此函数的开头有一个奇怪的基本情况。我会替换这个：

        if value is None:
            return self

有：

        if value is None:
            return None

...因为在那种情况下你没有寻找价值：那么（在我看来）return 节点实例（可能有任何价值 - 你没有验证）。 return None 或删除整个 if 块而不以特殊方式处理 None 似乎更一致。

Python: 递归不迭代列表的所有元素

Python: Recursion not iterating all elements of the list

python

tree

recursion

data-structures

方法

完整代码（以备测试需要）