遍历二叉树递归中的列表问题

Question

我尝试使用递归遍历二叉树。每个树要么有两个子树，要么没有子树（即，为子树保留的字段==无）

我想将每个分支（即两个子节点==无的每个节点）的最后叶子添加到一个列表中，并返回该列表。我使用“搜索”功能和助手“搜索库”功能来实现这一点。

通过调试器，我看到“search”函数中的列表确实包含我希望它显示的元素。但是，当它在search_base函数中返回时，结果似乎是一个空列表。

我非常困惑，如果有任何帮助，我将不胜感激。非常感谢。

class Node:
    def __init__(self, data, pos = None, neg = None):
        self.data = data
        self.positive_child = pos
        self.negative_child = neg   

class Diagnoser:
    def __init__(self, root):
        self.root = root

    def search_base(self):
        leaf_list=[]
        current = self.root
        return self.search(current, leaf_list)

    def search(self, current, leaf_list):
        if(current.positive_child == None):
            leaf_list.append(current)
            return leaf_list
        else:
            self.search(current.positive_child, leaf_list)
            self.search(current.negative_child, leaf_list)


if __name__ == "__main__":

    # Manually build a simple tree.
    #                cough
    #          Yes /       \ No
    #        fever           healthy
    #   Yes /     \ No
    # influenza   cold

    flu_leaf = Node("influenza", None, None)
    cold_leaf = Node("cold", None, None)
    inner_vertex = Node("fever", flu_leaf, cold_leaf)
    healthy_leaf = Node("healthy", None, None)
    root = Node("cough", inner_vertex, healthy_leaf)

    diagnoser = Diagnoser(root)
    leaf_list = diagnoser.search_base()
    print(leaf_list[0].data)

Answer 1

这里有一个完全简单的解决方案，没有副作用：

class Node:
    def __init__(self, data, pos=None, neg=None):
        self.data = data
        self.positive_child = pos
        self.negative_child = neg

    def leaves(self):
        if self.positive_child is self.negative_child is None:
            return [self]
        else:
            return (self.positive_child.leaves() +
                    self.negative_child.leaves())


if __name__ == "__main__":
    # Manually build a simple tree.
    #                cough
    #          Yes /       \ No
    #        fever           healthy
    #   Yes /     \ No
    # influenza   cold

    flu_leaf = Node("influenza", None, None)
    cold_leaf = Node("cold", None, None)
    inner_vertex = Node("fever", flu_leaf, cold_leaf)
    healthy_leaf = Node("healthy", None, None)
    root = Node("cough", inner_vertex, healthy_leaf)
    for leaf in root.leaves():
        print(leaf.data)

Answer 2

由于search修改列表，因此它不需要返回任何内容，search\u base只需返回修改后的列表即可。

class Diagnoser:
    def __init__(self, root):
        self.root = root

    def search_base(self):
        leaf_list = []
        current = self.root
        self.search(current, leaf_list)
        return leaf_list

    def search(self, current, leaf_list):
        if current.positive_child is None:
            leaf_list.append(current)
        else:
            self.search(current.positive_child, leaf_list)
            self.search(current.negative_child, leaf_list)

此外，您需要检查两个孩子是否都失踪，即。

if current.positive_child is None and current.negative_child is None:

Answer 3

问题是在

self.search(current.positive_child, leaf_list)
self.search(current.negative_child, leaf_list)

这些语句的返回值不会被保存或返回，因此这里函数给出None。此外，传递到这两个语句中的leaf_list是相同的，即它们不会被连接起来。在递归函数中，为了保证安全，最好不要有副作用。应该是：

 def search(self, current, leaf_list=[]):
        if(current.positive_child == None):
            return [current]
        else:
            return (self.search(current.positive_child, leaf_list)
                    + self.search(current.negative_child, leaf_list))