从后缀树构建后缀数组。当节点有两个以上的孩子时，访问访问

Question

从音符：

不难观察到后缀数组 $ \ texttt {sa} $ 文本 $ \ texttt {t} $ 可以从其后缀树中获取 $ \ texttt {st} $ 通过执行订单访问：每次叶子是 遇到，存储在本叶中的后缀索引被写入 后缀数组 $ \ texttt {sa} $ ;每次内部节点U是 遇到，其关联的值被写入数组 $ \ texttt {lcp} $ 。

当节点有两个以上的孩子时，您如何进行Inorder访问？

让我们说你访问最左边的孩子，然后访问节点，然后是另一个最左边的孩子。然后你再次访问节点？

sa 在指针数组到后缀，排列词典。

lcp 包含两个连续后缀之间的最长的常见前缀 $ \ text {spe} _ {sa [i]} \ text {and} \ text {spec} _ {sa [i + 1]} $ 。

\ $代表一个小于每个其他字符的char。

与每个节点相关联的值是到目前为止拼写的前缀的长度。

叶子代表后缀的指标。如果t=香蕉\ $，则叶子3代表Nana \ $（t [3,7]）

在图像中有什么应该是后缀树，但我认为由于边缘应该根据其标签和边缘标记为“\ $”的边缘，因此应该是左边的最左边的叶子的错误边缘。

在模拟算法时，首先访问节点7（使用树的固定版本），然后root，所以你有

SA = [7, ...]
lcp = [0, ...]

.

然后让我们说你继续使用u的访问权。 当您返回root时，您是否在lcp 中再次插入值0？或者你是第一次访问root的时候吗？

Answer 1

如果节点具有 $ l $ 子项，则使用 $ l \ geq 2 $ 在INORDER期间访问您必须对待第一个 $ l-1 $ 儿童作为左节点，并且您必须访问父倍数（$ l-1 $ ）次，编写多次LCP数组内的前缀的长度。

，应用于图像中的树，会产生正确的：

SA = [7, 6, 4, 2, 1, 5, 3]
lcp = [0, 1, 3, 0, 0, 2]

.

请记住，带有叶子7标记为“$”的边缘应该是最左边的。