我正在实现一个级别顺序简洁特里，我希望给定节点不能跳回他的父节点。
我尝试了几种等级/级别的组合，但我无法理解这个......
我使用这篇文章作为基础文档： http ://stevehanov.ca/blog/index.php?id=120
它解释了如何遍历孩子，但不解释如何向上。
感谢这个麻省理工学院讲座（http://www.youtube.com/watch?v=1MVVvNRMXoU）我知道这是可能的（在 15:50 所述的恒定时间内），但演讲者只解释二进制特里（例如：使用公式 select1(floor(i/2)) )。
我怎么能在 k-ary trie 上做到这一点？
好吧，我不知道是什么select1()，但另一部分 ( floor(i/2)) 看起来就像你在嵌入数组的二叉树中使用的技巧，就像这里描述的那样。您将除以 2，因为每个父级恰好有 2 个子级 -> 每个级别使用父级空间的两倍。
如果您在每个节点中没有相同数量的子节点（除了叶子和可能具有较少子节点的节点），则不能使用此技巧。
如果您想知道任何给定节点的父节点，则需要在每个节点中添加指向父节点的指针。
但是，由于树通常从根开始遍历并向下遍历，因此通常要做的是将指向路径节点的指针存储在数组中。在任何给定点，当前节点的父节点都是数组中的前一个元素。这样您就不需要在每个节点中添加指向父节点的指针。
我想我找到了答案。Guy Jacobson 的这篇论文在第 3.2 节 Level-order 一元度数序列中对其进行了解释。
父母（x）{选择1（排名0（x））}
节省空间的静态树和图 http://www.cs.cmu.edu/afs/cs/project/aladdin/wwwlocal/compression/00063533.pdf
只要你不像我一样搞乱你的节点编号，这项工作就很好。