在列表中水平返回二叉树

Question

您如何 return 在列表中水平放置二叉搜索树？是否可以递归？

预期名单：8、3、10、1、6、14、4、7、13

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

Answer 1

您需要使用 breath-first 搜索。在伪代码中：

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

Answer 2

或者您可以进行深度优先搜索并记录每个节点的级别，然后在结果中使用 LINQ 查询

DisplayNodeVert(Node8).OrderBy(n=>n.Level).Select(n=>n.Content)

在列表中水平返回二叉树

Returning a binary tree horizontally in a list

c#

algorithm

binary-search-tree