打印二叉搜索树的层级

Question

我有一个二叉搜索树的数据结构类，这个类里面有一些节点，这些节点就像是二叉搜索树的对象。

这个类的代码太长，不能在这里全部贴出来，但基本上它是这样工作的。如果我想打印出二叉搜索树的顶部值，我会这样写：

print (self._root)

如果我想移动到树的左边（去右边也是一样，只需要把“左”换成“右”就可以了），我会这样写：

print (self._root._left)

我希望这些信息足够你帮助我解决问题。

接下来是我的问题，如果我有一个像这样的二叉搜索树：

      6
     / \
    3   8
   / \   \
  1  4   10

我想能够打印出：

6

3
8

1
4
10

我写了一个递归遍历的函数：

def traverse(self):

        a = []
        self._traverse_aux(self._root, a)   
        return a

def _traverse_aux(self, node, a):

        if node is not None:
            self._traverse_aux(node._left, a)
            a.append(node._value)
            self._traverse_aux(node._right, a)
        return

但是，这个函数打印出来的值是在一个单一的数组里：

[1, 3, 4, 6, 8, 10]

我该怎么做才能像上面那样打印出来呢？

Answer 1

最理想的情况是，你会想要用递归的方式来解决这个问题。这种遍历方式叫做广度优先遍历。

这里有一些关于二叉搜索树遍历的笔记，可能对你有帮助，虽然它们是用Java写的。

这里还有一个非常相似（可能是重复）的提问，不过它是用循环的方式来解决，而不是递归。