算法 - 将嵌套数据转换为普通数据

Question

我有以下嵌套数据结构:

Node 1  
  |--- Node 11  
       |--- Node 111
  |--- Node 12  
       |--- Node 121  
       |--- Node 122  
       |--- Node 123  
  |--- Node 13  
       |--- Node 131  
Node 2  
  |--- Node 21  
       |--- Node 211
       |--- Node 212
etc.  

我正在尝试编写一种算法，将其转换为“普通”二维矩阵，如下所示:

| 1  | 11  | 111 |  
| 1  | 12  | 121 |  
| 1  | 12  | 122 |  
| 1  | 12  | 123 |  
| 1  | 13  | 131 |  
| 2  | 21  | 211 |  
| 2  | 21  | 212 |  
etc.

但是，我在高效地执行此操作时遇到了一些麻烦，因为我不能只遍历树并填充矩阵:如您所见，由于冗余数据，矩阵的单元数多于树的节点数在除最后一列之外的所有列中。

请注意，就像在示例中一样，树的所有叶子都将具有相同数量的父节点，即:相同的“嵌套深度”，因此我不需要考虑较短的分支。

我确信已经有一个算法可以正确地做到这一点，但我不知道这个特定问题是如何被调用的，所以我找不到它。谁能帮帮我？

Answer 1

我不确定这有什么具体的名称，也许是“树扁平化”，但我想有几种方法可以使树扁平化。你可以用这样的东西来做(伪代码，因为没有语言标签):

proc flatten_tree(tree : Node<Int>) : List<List<Int>>
    matrix := []
    flatten_tree_rec(tree, [], matrix)
    return matrix
endproc

proc flatten_tree_rec(tree : Node<Int>, current : List<Int>, matrix : List<List<Int>>)
    current.append(tree.value)
    if tree.is_leaf()
        matrix.append(current.copy())
    else
        for child in tree.children()
            flatten_tree(child, current, matrix)
        loop
    endif
    current.remove_last()
endproc

如果您需要生成一个需要预分配的实际矩阵，您需要两次传递，一次计算叶子和深度的数量，另一次实际填充矩阵:

proc flatten_tree(tree : Node<Int>) : List<List<Int>>
    leafs, depth := count_leafs_and_depth(tree, 0)
    matrix := Matrix<Int>(leafs, depth)
    flatten_tree_rec(tree, [], matrix, 0)
    return matrix
endproc

proc count_leafs_and_depth(tree : Node<Int>, base_depth : Int) : Int
    if tree.is_leaf()
        return 1, base_depth + 1
    else
        leafs := 0
        depth := 0
        for child in tree.children()
            c_leafs, c_depth := count_leafs_and_depth(child, base_depth + 1)
            leafs += c_leafs
            depth = max(c_depth, depth)
        loop
        return leafs, depth
    endif
endproc

proc flatten_tree_rec(tree : Node<Int>, current : List<Int>, matrix : Matrix<Int>, index : Int)
    current.append(tree.value)
    if tree.is_leaf()
        matrix[index] = current
        index += 1
    else
        for child in tree.children()
            index = flatten_tree(child, current, matrix, index)
        loop
    endif
    current.remove_last()
    return index
endproc