遞歸字遍歷

Question

我在這裏發現了同樣的問題Traversing a trie to get all words，但它是用於Perl的，我只熟悉Java。 my trie結構是純整數數組，其中前26個整數是根，每個整數具有firstChild索引，它是子數組元素的索引（最多25個最高位），列表結束位標誌，結束標誌位，字位標誌，字母索引從1到26（最低5位）。 我可以遞歸打印一個字CAGE如果我通過了2（用於字母c根索引）作爲參數

private void oneWord(int node) { 
     System.out.print(getChar(Trie[node])); 
     if (getEOL(Trie[node]) != 1) { 
      oneWord(getFirstChild(Trie[node])); 
     } 
    } 

或一個共同的開始和不同的結局等YARDELLOW單詞碼和黃色（通過24作爲參數）

private void DFTSearch(int node) { 
    System.out.print(getChar(Trie[node])); 
    if (getFirstChild(Trie[node]) != 0) { 
     for (int i = 0; i < getSiblingsNum((getFirstChild(Trie[node])); i++) { 
      DFTSearch(getFirstChild(Trie[node]) + i); 
     } 
    } 
} 

，但不能做到這一點與所有單詞（（我已經試過這並使其返回一個字符串，而沒有得到任何成功（剛獲得的一個第一封信字符串 請幫助使用遞歸打印的方法（還有什麼更好 - 返回字符串數組）我的特里將會有這樣的話。 這不是一個家庭作業，我是自學的））

Answer 1

你可能會分享一些你的代碼和輸入數據，以便更好地理解你正在嘗試做什麼？

關於的堆棧溢出討論可能有用的Java中的Trie數據結構：Trie data structures - Java。我發現以下鏈接（來自其中一個答案）非常有用：https://forums.oracle.com/forums/thread.jspa?messageID=8787521。

編輯：從https://forums.oracle.com/forums/thread.jspa?messageID=8787521和Java tree data-structure?幫助下，我創建了下面的代碼：

public Stack<List<Character>> createTreeAndGetAllWords() { 
    // Create the tree. 
    final Tree<Character> rootTree = new Tree<Character>('*'); 
    final Tree<Character> cTree = rootTree.addChild(new Tree<Character>('c')); 
    final Tree<Character> aTree = cTree.addChild(new Tree<Character>('a')); 
    aTree.addChild(new Tree<Character>('r')); 
    aTree.addChild(new Tree<Character>('t')); 
    final Tree<Character> dTree = rootTree.addChild(new Tree<Character>('d')); 
    final Tree<Character> oTree = dTree.addChild(new Tree<Character>('o')); 
    oTree.addChild(new Tree<Character>('g')); 
    // Traverse the tree. 
    return getAllWords(rootTree); 
} 

private Stack<List<Character>> getAllWords(final Tree<Character> tree) { 
    final Stack<List<Character>> listStack = new Stack<List<Character>>(); 
    for (final Tree<Character> child : tree.getChildren()) { 
     listStack.push(new ArrayList<Character>()); 
     traverseSubtree(child, listStack); 
    } 
    return listStack; 
} 

private void traverseSubtree(final Tree<Character> tree, final Stack<List<Character>> listStack) { 
    final List<Character> currentWord = listStack.pop(); 
    if (tree.hasChildren()) { 
     for (final Tree<Character> child : tree.getChildren()) { 
      final List<Character> extendedWord = new ArrayList<Character>(currentWord); 
      extendedWord.add(tree.getValue()); 
      listStack.push(extendedWord); 
      traverseSubtree(child, listStack); 
     } 
    } else { 
     currentWord.add(tree.getValue()); 
     listStack.push(currentWord); 
    } 
} 



public class Tree<T> { 
    private T value; 
    private List<Tree<T>> children; 

    public Tree(T value) { 
     this.value = value; 
     this.children = new ArrayList<Tree<T>>(); 
    } 

    public T getValue() { 
     return value; 
    } 

    public boolean hasChildren() { 
     return children.size() > 0; 
    } 

    public Tree<T> addChild(Tree<T> child) { 
     children.add(child); 
     return child; 
    } 

    public List<Tree<T>> getChildren() { 
     return children; 
    } 
} 

當我打電話createTreeAndGetAllWords，它返回我的預期爲字符的三個列表的話：[C，A，R] ， [下大雨]。

for (final List<Character> word : createTreeAndGetAllWords()) { 
    System.out.println("word = " + word); 
} 

乾杯，暴走