在完整树的深度优先遍历和深度优先遍历之间转换的函数 [英] Functions to convert between depth first and breadth first traversals of a complete tree

问题描述

问题：考虑一个完整的k级树，其中包含l个层，节点以其在广度优先遍历中的等级标记。按照标签在深度优先遍历中的遍历顺序计算标签列表。

Problem: Consider a complete k-ary tree with l levels, with nodes labelled by their rank in a breadth first traversal. Compute the list of labels in the order that they are traversed in the depth first traversal.

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

For example, for a binary tree with 3 levels, the required list is: [0 1 3 7 8 4 9 10 2 5 11 12 6 13 14]

一种方法是实际构造一个树结构并将其遍历两次；第一个遍历是广度优先，在运行时将节点标记为0,1,2，..。第二个遍历是深度优先，随行时会报告标签0、1、3、7..。

One way to do this is to actually construct a tree structure and traverse it twice; The first traversal is breadth first, labelling the nodes 0,1,2,.. as you go. The second traversal is depth first, reporting the labels 0,1,3,7,.. as you go.

我对避免在内存中构造树的方法感兴趣。我意识到这样一棵树的大小可以与输出的大小相提并论，但是我希望该解决方案将允许流式输出（即不需要完全存储在内存中的输出）。

I'm interested in a method that avoids constructing a tree in memory. I realize that the size of such a tree is comparable to the size of the output, but I'm hoping that the solution will allow for a "streaming" output (ie one that needs not be stored entirely in memory).

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

I am also interested in the companion problem; start with a tree labelled according to a depth first traversal and generate the labels of a breadth first traversal. I imagine that the solution to this problem will be, in some sense, dual to the first problem.

推荐答案

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

You don't actually need to construct the tree. You can do the depth first traversal using just the BFS labels instead of pointers to actual nodes.

使用BFS位置标签表示k元树中的节点：

Using BFS position labels to represent the nodes in k-ary tree:

• 根是 0


• 第一个任何节点 n 的子节点为 k * n + 1


• 节点 n 的同级节点（如果有）为 n + 1

• The root is 0
• The first child of any node n is k*n + 1
• The right sibling of a node n, if it has one, is n+1

在代码中看起来像这样：

in code it looks like this:

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顺序排列的数组元素，并且通过对索引执行这些操作来遍历树。

This is actually used all the time to represent a binary heap in an array -- the nodes are the array elements in BFS order, and the tree is traversed by performing these operations on indexes.

这篇关于在完整树的深度优先遍历和深度优先遍历之间转换的函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！