java - 我们如何为后缀树中的父子关系使用链表？

Question

根据维基百科，实现后缀树时的一个重要选择是节点之间的父子关系。最常见的一种是使用称为兄弟列表的链表。

这在 Java 中是如何工作的？

Answer 1

在同级列表中，每个节点恰好有两个引用：first-child和next-sibling。这使您可以通过从 开始遍历节点的所有子节点first-child，然后跟随next-sibling直到您到达 is 的子next-sibling节点null。我不明白为什么 Java 会与任何其他编程语言有任何不同。

有趣的是，这种表示实际上与二叉树的标准表示相同，其中leftis spelledfirst-child和rightis spelled next-sibling。这说明了1-1具有相同节点数的二叉树和一般树之间的关系。（一开始可能看起来矛盾，但请注意，二叉树可能只有一个left孩子，或者只有一个right孩子，而这些被认为是不同的。相比之下，在一般树中，节点只有一种方式拥有一个孩子。

Answer 2

父节点有一个子节点列表（作为数组、双链表等）每个子节点都有一个到其父节点的链接。遍历非常简单，因为您不需要堆栈。