使用 O(1) 空间以 BFS 方式打印二叉树

Question

我想知道是否可以在仅使用 O(1) 空间的情况下以广度优先顺序打印二叉树？

困难的部分是，我们必须使用额外的空间来记住要遍历的下一个级别，并且该空间随着 n 的增加而增长。

由于我们没有对时间部分进行任何限制，也许有一些低效（就时间而言）的方法可以实现这一目标？

有什么想法吗？

Answer 1

这将取决于一些更细粒度的定义，例如边缘是否有反向链接。然后就很容易了，因为您只需沿着树上的反向链接即可。否则，我无法立即想出一种没有 O(lg 节点数) 空间的方法，因为您至少需要记住“上面”的节点。

更新

哦等等，当然可以通过时空交易在 O(1) 空间 中完成。无论您想要在哪里进行反向链接，您都可以保存您的位置并执行 BFS，跟踪最近的节点，直到找到您的节点。然后备份到最近访问的节点并继续。

问题是，空间复杂度为 O(1)，时间复杂度为 O(n^2)。

另一个更新

假设我们已经到达节点 n_i，并且想要到达该节点的父节点，我们将其称为 wlg n_j。我们已经识别出显着的根节点n_0。

修改呼吸优先搜索算法，以便当它遵循有向边 (n_x,n_y) 时，存储传出或“传入”节点。因此，当您遵循 (n_x,n_y) 时，您将保存 n_x。

当您从 n_0 再次启动 BFS 时，可以保证（假设它确实是一棵树）在某个点，您将转换边 (n_j,n_i)。那时你会发现你回到了n_i。您已经存储了 n_j，因此您知道反向边是 (n_i,n_j)。

因此，您只需两个额外的单元即可获得单个回溯，一个用于 n_0，一个用于“已保存”节点。这是 O(1)

我不太确定 O(n^2) ——现在已经很晚了，而且这是艰难的一天，所以我不想写证明。我确定它是 O((|N|+|E|)^2) 其中 |N|和|E|分别是顶点集和边集的大小。

Answer 2

一个有趣的特殊情况是堆。

来自 heapq 文档：

堆是二叉树，每个父节点的值都小于
大于或等于其任何子级。该实现使用数组
其中 heap[k] <= heap[2*k+1] 且 heap[k] <= heap[2*k+2] 对于所有 k ,
从零开始计数元素。为了便于比较，不存在
元素被认为是无限的。一个有趣的属性
堆的特点是它的最小元素始终是根，heap[0]。 [弗朗索瓦·皮纳德的解释]

树在内存中的表示方式（数组的索引）：

                               0

              1                                 2

      3               4                5               6

  7       8       9       10      11      12      13      14

15 16   17 18   19 20   21 22   23 24   25 26   27 28   29 30

在这种情况下，数组中的节点已经以广度优先顺序存储。

for value in the_heap:
    print(value)

空间中的 O(1)。

Answer 3

我知道这严格来说不是问题的答案，但是可以使用 O(d) 空间以广度优先顺序访问树的节点，其中 d 是树的深度，通过递归迭代加深深度优先搜索 （IDDFS）。当然，堆栈需要空间。对于平衡树，d = O(lg n)，其中 n 是节点数。老实说，如果没有 @Charlie Martin 建议的反向链接，我真的不知道如何在恒定的空间中做到这一点。

Answer 4

很容易实现递归方法来获取给定级别的树的所有节点。因此，我们可以计算树的高度并获得所有节点和每个级别。这是树的层序遍历。但是，时间复杂度是O(n^2)。下面是 Java 实现（源代码）。

class Node 
{ 
    int data; 
    Node left, right; 
    public Node(int item) 
    { 
        data = item; 
        left = right = null; 
    } 
} 

class BinaryTree 
{ 
    Node root; 

    public BinaryTree() 
    { 
        root = null; 
    } 

    void PrintLevelOrder() 
    { 
        int h = height(root); 
        int i; 
        for (i=1; i<=h; i++) 
            printGivenLevel(root, i); 
    } 

    int Height(Node root) 
    { 
        if (root == null) 
           return 0; 
        else
        { 
            int lheight = height(root.left); 
            int rheight = height(root.right); 

        } 
    } 

    void PrintGivenLevel (Node root ,int level) 
    { 
        if (root == null) 
            return; 
        if (level == 1) 
            System.out.print(root.data + " "); 
        else if (level > 1) 
        { 
            printGivenLevel(root.left, level-1); 
            printGivenLevel(root.right, level-1); 
        } 
    }
}