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

Question

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

我想将每个分支(即两个子节点 == 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)

Answer 1

问题是在

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

Answer 2

由于search修改了列表，因此它不需要返回任何内容，search_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

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

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)