arrays - 如何用一维数组表示非二叉树？

Question

一种使用一维数组表示非二叉树的方法

当节点数量有限且数量较少时，我们可以使用一维数组来表示二叉树而索引 i 处的节点有两个儿子，索引为 2*i 和 2*i+1。我可以使用一维数组以相同的方式存储非二叉树吗(当一个节点有两个以上的儿子时)？我想用这种方式来存储一棵最多有 3 个儿子的树，其中节点的索引是 i，它的儿子在 3*i、3*i + 1 和 3*i + 2.. 但是这样做，我我留下了很多空的(未使用的)数组单元格。有没有更好的办法？

Answer 1

这是一种将所有节点打包到一维数组中的解决方案。

每个节点由可变数量的数组单元格组成。该节点的第一个单元格是其子节点的计数 C。接下来的 C 个单元格包含数组中其子节点的第一个单元格的索引。

例如:

Indexes: 0 1 2 3 4
Values:  2 3 4 0 0

是一个有 3 个节点的图； 1 个节点有 2 个子节点。第一个节点位于单元格索引 0 处，其值为 2，即其子节点的数量。接下来的 2 个值是子节点的索引，3 和 4。索引 3 和 4 处的单元格的值为 0，因为它们没有子节点。