二叉树的所有元素列表

Question

作为初学者，我一直在尝试在 python 中实现二叉树。并且已经可以成功实现很多，只有一个问题是我无法返回traverse()二叉树中所有元素 ( ) 的列表。我在这里使用两个类，Node并且BinaryTree.节点类class Node:    def __init__(self, val):        self.value = val        self.left = None        self.right = NoneTraverse 方法返回二叉树中的所有元素。    def traverse(self): #<-- Problem here        tree_elements = []        if self.left != None:            self.left.traverse()        tree_elements.append(self.value)        #debug        print(self.value, end=" ")        if self.right != None:            self.right.traverse()        return tree_elements    def addNode(self, node):        if node.value < self.value and node.value != self.value:            if self.left == None:                self.left = node            else:                self.left.addNode(node)        elif node.value > self.value and node.value != self.value:            if self.right == None:                self.right = node            else:                self.right.addNode(node)    def search(self, val):        if val == self.value:            return "Found"        elif val < self.value:            if self.left != None:                return self.left.search(val)            else:                return "Not Found "        elif val > self.value:            if self.right != None:                return self.right.search(val)            else:                return "Not Found"二叉树class BinaryTree:    def __init__(self):        self.root = None    def addVlaue(self, val):        node = Node(val)        if self.root == None:            self.root = node        else:            self.root.addNode(node)     def search(self, val):         if self.root == None:             return False         else:             return self.root.search(val)    def traverse(self):         if self.root == None:             return "no data"        else:            return self.root.traverse()问题：traverse方法必须返回二叉树中的所有元素，但我只得到树的第一个值。例子：元素：100 18 46 5 65 5 31 71 94 43 #在树中输入树的输出：5 18 31 43 46 65 71 94 100 #预期输出[100] #树的输出

Answer 1

该tree_elements列表需要沿着递归调用进行，沿途收集每个节点。换句话说，它必须作为参数传递给traverse调用（调用traverse根节点时除外）。

否则，在每次遍历调用中都会创建并丢弃一个新列表（因为在其递归期间您从未对其返回值做任何事情traverse），除了仅返回根元素的顶级递归调用。

试试这个实现：

def traverse(self, tree_elements=None):

    if tree_elements is None:

        tree_elements = []

   if self.left != None:

        self.left.traverse(tree_elements=tree_elements)

    tree_elements.append(self.value)

    if self.right != None:

        self.right.traverse(tree_elements=tree_elements)

    return tree_elements