二叉树的所有元素列表

Question

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

节点Class

class Node:
    def __init__(self, val):
        self.value = val
        self.left = None
        self.right = None

遍历方法return二叉树中的所有元素

    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 方法必须 return 二叉树中的所有元素，但我只得到树的第一个值。

示例：

elements: 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 的 return 值执行任何操作），除了顶部递归调用 return仅是根元素。

试试这个实现：

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

二叉树的所有元素列表

List of all elements of Binary Tree

python

algorithm

binary-tree

节点Class

二叉树

问题：