c# - 在列表中水平返回二叉树

Question

如何在列表中水平返回二叉搜索树？是否可以递归？

预期列表:8、3、10、1、6、14、4、7、13

[编辑] 由于索引，我设法在一个数组中完成它，因为我们知道节点 i 的左儿子将是 2i+1，而右节点将是 2i+2。不过，我不知道如何使用列表来做到这一点。

Answer 1

您需要使用呼吸优先搜索。在伪代码中:

BreadthFirstSearch(Node root):

    create empty list L
    create empty queue Q

    Q.enqueue(root)

    while Q is not empty:
        current = Q.dequeue()

        L.append(current)
        if current.left is not null:
            Q.enqueue(current.left)
        if current.right is not null:
            Q.enqueue(current.right)

    return L

或者，递归地做

BreadthFirstSearch(Queue Q, List L):
    if Q is empty:
        return

    current = Q.dequeue()
    L.append(current)

    if current.left is not null:
        Q.enqueue(current.left)
    if current.right is not null:
        Q.enqueue(current.right)

    BreadthFirstSearch(Q, L)

对于第二种方法，您可以这样调用它:

ConvertBSTToList(Node root):
    create empty queue Q
    create empty list L

    Q.enqueue(root)
    BreadthFirstSearch(Q,L)

    return L