algorithm - 我怎样才能将树制作成二维数组

Question

我正在尝试将树数据结构制作成二维数组。我正在尝试用这样的 for 循环来做。childs() 函数返回子节点数组。

void makeArray(a 1_level_a)
{
    for(2_level_a : 1_level_a.childs())
    {
        for(3_level_a : 2_level_a.childs())
        {

        }
    }
}

我该怎么做？有什么建议吗？

Answer 1

您可以逐行编写数组。以下代码假定树的深度只有 3:

array[0][0] = 1_level_a;
int last_index = 0;

for (2_level_a : 1_level_a.childs()) {
    array[1][last_index] = 2_level_a;
    for (3_level_a : 2_level_a.childs()) {
        array[2][last_index] = 3_level_a;
        last_index++;
    }
    if (2_level_a.childs().size() == 0) {
        last_index++;
    }
}

如果需要处理更大深度的树，可以使用递归:

int writeTree(node, depth, last_index) {
    array[depth][last_index] = node;
    for (child : node.childs()) {
        last_index = writeTree(child, depth + 1, last_index);
    }
    if (node.childs().size() == 0) {
        last_index++;
    }
    return last_index;
}

writeTree(1_level_a, 0, 0);

请注意，这与上述算法相同，但上述算法假设深度为 3 的节点没有子节点。