Trie迭代器，後綴排序

Question

我需要實現一個trie的迭代器。比方說，我有

a 
    /\ 
    b c 
    /\ 
d e 

如果當前iterator.state =「ABD」，我想有iterator.next.state =「安倍」，那麼「交流」。在每個級別，節點按字典順序排序（例如，在級別2上，c在b之後）。這也應該發生在log（n）時間，其中n是節點的數量。

我能想到的一個解決方案是：考慮一個特殊情況，每個分支具有相同的高度。我認爲一個相當酷的實現是爲每個「級別」維護一棵平衡的樹。在詢問：「在abd之後跟隨什麼字符串」時，可以在與第三級關聯的樹中搜索大於「b」的第一個元素，給出「abe」。

但是，由於必須創建樹木，這可能不切實際。

Answer 1

如果我正確理解問題，則迭代器狀態可能是當前字符串和指向當前位置的指針。然後，移動到下一個元素：

1. 如果您當前的位置有一個兄弟，將它和當前字符串與當前位置的字符替換最後一個字符。

2. 否則，刪除最後一個字符並上去樹。如果你試圖從根開始，那麼你就完成了。否則，轉到步驟1

因此，例如，當你在ABD（在你的例子），當前字符串是「ABD」和指針指向「d」。要移動到下一個元素，將字符串更改爲「ab」，移動到兄弟節點（'e'）並將其添加到字符串中，產生「abe」。之後，你會上升，因爲沒有兄弟姐妹，然後到b的兄弟姐妹，產生正確的下一個值'ac'。

正如你所看到的，最壞的情況下，這些步驟中的每一步都需要一直回到根，才能找到兄弟姐妹;那是你要求的日誌。