二叉树的所有元素列表

Question

作为初学者，我一直在尝试在 python 中实现二叉树。并且已经可以成功实现很多，只有一个问题是我无法返回traverse()二叉树中所有元素 ( ) 的列表。我在这里使用两个类，Node并且BinaryTree.

节点类

class Node:

    def __init__(self, val):

        self.value = val

        self.left = None

        self.right = None

Traverse 方法返回二叉树中的所有元素。

    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):&nbsp; &nbsp; if tree_elements is None:&nbsp; &nbsp; &nbsp; &nbsp; tree_elements = []&nbsp; &nbsp;if self.left != None:&nbsp; &nbsp; &nbsp; &nbsp; self.left.traverse(tree_elements=tree_elements)&nbsp; &nbsp; tree_elements.append(self.value)&nbsp; &nbsp; if self.right != None:&nbsp; &nbsp; &nbsp; &nbsp; self.right.traverse(tree_elements=tree_elements)&nbsp; &nbsp; return tree_elements