c++ - 用 vector 表示和遍历一棵 n 叉树

Question

我已经实现了一个 n 叉树(更具体地说，一个 trie 树)，我想知道是否有一种方法可以将它作为一个 vector 来表示和遍历。使用二叉树是微不足道的(请参阅 this question )，但我似乎找不到使用 n 叉树执行此操作的方法。我的最终目标是将 vector 表示的树存储到一个文件中，对其进行 mmap 并执行快速查找，而无需将其有效地加载到内存中。
将 trie 与 mmap-ped 指针一起使用而不是分配其内部结构来在磁盘上存储 trie 的有效方法也很棒。

谢谢。

Answer 1

如果您有一棵树，其中每个节点 n 恰好有 k 个子节点，那么您可以将节点 n 的子节点放在数组中的 k*n+m 位置，其中 m 介于 0 和 k-1 之间。如果每个节点都有 k 个或更少的子节点，这也会起作用，但如果很多节点的子节点少于 k 个，它将使用比所需更多的内存。我知道将树存储为节点具有不同数量子节点的数组的唯一其他方法是存储辅助数组，其中对于每个节点，您将偏移量存储到原始数组中以找到该节点的子节点，然后您可以要么还存储每个节点的子节点数，要么简单地查找下一个节点的子节点的偏移量以确定该节点有多少个子节点。