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

Question

树的每个节点可能具有任意数量的子节点.我需要一种方法来构造和遍历这些树,但是使用一维向量或列表来实现它们.

Answer 1

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

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

所以对于像这样的树:

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. 每个节点都保存其子节点占用的向量中的区域地址
2. 孩子们彼此相邻
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   _ _   _ _ _

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