c - 将树展平为数组

Question

我正在寻找将树放入数组的最佳方法

这个想法是遵循这个原则：树的数组实现， 但我一直坚持如何知道哪些节点是子节点以及哪些节点处于同一级别，因为我没有使用二叉树。

我可能必须存储 ASCII，但我不能简单地允许 256 个指针的数组！

任何想法都会受到欢迎。

这样做的目的是将数组（树）发送到我的 GPU，而不是使用结构。

Answer 1

好吧，这是我的想法converting tree into an array。

取一个 size 的数组MAX_VAL，它是树中节点的总数。数组的类型应与节点的类型相同，但多了一个字段。它是其父级的索引值。您以这种方式存储每个节点。将根节点存储在第一个位置。说1。现在，该节点的子节点随后与额外的字段存储一起存储1（因为这是存储根的位置）。

在所有节点上应用此过程，您就完成了。您可以通过在每个节点上进行简单的递归调用来取回树。

希望这可以帮助。:) :)

Answer 2

如果不是近乎完美的平衡，Ahnentafel 列表就非常大。我的猜测是您的树不会平衡，因此隐式父/子指针的好处将超过成本。我从未见过非二进制 Ahnentafel 列表，但我认为这是可能的（您是在要求隐式方程吗？）。

你能为每个节点（ASCII字符+指针/索引）保留一个排序的子指针列表吗？在这种情况下，正如其他人所建议的那样，最好使用指针构造树并允许孩子成长。然后将所有节点打包到一个列表中：计算出放置节点的顺序，使用前缀和作为它们在数组中的偏移量，存储每个节点上的位置索引，最后将子列表复制到数组中（将子指针替换为可以通过跟踪指针并查询上一步中的索引来完成列表索引）。

在 CUDA 中遍历一个孩子不会是固定时间，但由于知道顺序，您可以使用二进制搜索来加快速度。