algorithm - 在完整树的深度优先和广度优先遍历之间转换的函数

Question

问题:考虑一棵具有 l 层的完整 k 元树，节点在广度优先遍历中由其等级标记。按照深度优先遍历中遍历标签的顺序计算标签列表。

例如，对于具有 3 个级别的二叉树，所需的列表是:[0 1 3 7 8 4 9 10 2 5 11 12 6 13 14]

一种方法是实际构造一个树结构并遍历它两次；第一次遍历是广度优先，将节点标记为 0,1,2,..。第二次遍历是深度优先，边走边报告标签 0,1,3,7,..。

我对一种避免在内存中构建树的方法很感兴趣。我意识到这种树的大小与输出的大小相当，但我希望该解决方案将允许“流式”输出(即不需要完全存储在内存中的输出)。

我也对伴生问题感兴趣；从根据深度优先遍历标记的树开始，并生成广度优先遍历的标签。我想这个问题的解决方案在某种意义上与第一个问题是双重的。

Answer 1

您实际上不需要构建树。您可以仅使用 BFS 标签而不是指向实际节点的指针来进行深度优先遍历。

使用BFS位置标签表示k叉树中的节点:

• 根是0
• 任何节点 n 的第一个 child 是 k*n + 1
• 节点 n 的右兄弟节点(如果有的话)是 n+1

在代码中它看起来像这样:

class Whatever
{
    static void addSubtree(List<Integer> list, int node, int k, int levelsleft)
    {
        if (levelsleft < 1)
        {
            return;
        }
        list.add(node);
        for (int i=0; i<k; i++)
        {
            addSubtree(list, node*k+i+1, k, levelsleft-1);
        }
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        int K = 2, LEVELS = 4;
        ArrayList<Integer> list = new ArrayList<>();
        addSubtree(list, 0, K, LEVELS);
        System.out.println(list);
    }
}

这实际上一直用来表示数组中的二叉堆——节点是 BFS 顺序的数组元素，通过对索引执行这些操作来遍历树。