我需要实现一个trie的迭代器。假设我有
a
/
b c
/
d e
如果当前迭代器。state="abd"，我希望有iterator.next。State ="abe"，然后是"ac"。在每一层，节点按字典顺序排序(例如，在第2层，c在b之后)。这应该在log(n)时间内完成，其中n是节点数。
我能想到的一个解决方案是:考虑一个特殊的情况，当每个分支都有相同的高度。我认为一个很酷的执行方法是为每个"关卡"维持一个平衡的树。在问:"abd之后是什么字符串"时，当定位在b上时，可以在与第三层相关的树中搜索第一个比"b"大的元素，得到"abe"。
然而，这可能是不切实际的，因为必须创建树。
如果我理解正确的话，迭代器状态可以是当前字符串和指向树中当前位置的指针。然后，移动到下一个元素:
-
如果你的当前位置有兄弟位置，移动到它，用当前位置的字符替换当前字符串中的最后一个字符。
-
else，删除最后一个字符并向上移动树。如果你想从根结点往上走，就完了。
所以，例如当你在abd(在你的例子中)，当前字符串是"abd"，指针指向"d"。要移动到下一个元素，将字符串更改为"ab"，移动到兄弟节点("e")并将其添加到字符串中，产生"abe"。在那之后，你将上升，因为没有兄弟，然后到b的兄弟，产生正确的下一个值'ac'。
正如你所看到的，在最坏的情况下，每一步都需要在找到兄弟节点之前一直回到根节点;这就是你要求的log(n)