时间戳

首页 > 解决方案 > 遍历二叉树的递归列表问题

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

问题描述

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

我想将每个分支的最终叶子（即两个孩子 == None 的每个节点）添加到列表中，然后返回列表。我正在使用“搜索”功能和助手“search_base”功能来执行此操作。

通过调试器，我看到“搜索”函数中的列表确实包含我想要的元素。但是，当它在 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)

标签： pythonrecursionbinary-tree

解决方案

问题是在

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))

推荐阅读