使用一维向量实现非二叉树的算法？

Question

树的每个节点可能有任意数量的 child 。我需要一种方法来构造和遍历此类树，但要使用一维向量或列表来实现它们。

Answer 1

如果你只能使用一个向量(没有在问题中指定)，并且节点不应该包含它自己的列表，只有一些指针(向量中的地址)，那么你可以试试这个:

1. 每个节点保存其兄弟节点的地址
2. 给定后的第一个节点(如果它不是它的兄弟)是 child ，指针指向第二个 child ，依此类推
3. 每个 child 都有自己的 child

所以对于这样的树:

A
| \
B  E ___
|\  \ \ \
C D  F G H

你的矢量看起来像:

idx:    0 1 2 3 4 5 6 7
nodes:  A B C D E F G H
next:   _ 4 3 _ _ 6 7 _

其中_是空指针

编辑:
另一种方法:

1. 每个节点保存其子节点占用的vector中区域的地址
2. children 挨在一起
3. 向量中存在空节点，标记兄弟组结束

对于这种方法，给定的树看起来像:

idx:    0 1 2 3 4 5 6 7 8 9 A B
nodex:  A _ B E _ C D _ F G H _
child:  2   5 8   _ _   _ _ _

这样你就可以很容易地找到任何随机给定节点的子节点并重新组织数组而无需移动所有元素(只需将子节点复制到表尾，更新指针并将下一个子节点添加到表尾)