Trie에서 모든 단어를 어떻게 출력합니까?

Question

나는 을 가지고있다. 3 차 검색 나무 (Trie) 나는 그 안에 모든 단어를 인쇄하고 싶다.

아래에있는 현재 구현을 사용하여 어떻게이 문제를 해결할 수 있습니까? 트리에 새 단어를 추가하는 표준 put 방법이 있습니다. 순차적 탐색을 사용하여 단어를 인쇄하려했지만 함수를 정확히 완료하는 방법이 확실하지 않습니다. 각 노드는 하나의 문자를 저장하기 때문에 당신의 통과를 수행 할 때 루트에서 경로에 의해 정의 된 접두사를 나타내는 (당신이 효율적으로하려는 경우, 또는 모두 StringBuilder를)

class TST { 
    private Node root; 

    public void put(String key, int value) { 
     root = put(root, key, value, 0); 
    } 

    private Node put(Node node, String key, int value, int index) { 
     char c = key.charAt(index); 

     if(node == null){ 
      node = new Node(c); 
     } 

     if(c < node.character){ 
      node.left = put(node.left, key, value, index); 
     }else if(c > node.character){ 
      node.right = put(node.right, key, value, index); 
     }else if(index < key.length()-1){ 
      node.middle = put(node.middle, key, value, index+1); 
     }else{ 
      node.value = value; 
     } 

     return node; 
    } 

    public Integer get(String key) { 
     Node node = get(root, key, 0); 

     if (node == null) { 
      return null; 
     } 

     return node.value; 
    } 

    public Node get(Node node, String key, int index) { 
     if(node == null) { 
      return null; 
     } 

     char c = key.charAt(index); 

     if (c < node.character) { 
      return get(node.left, key, index); 
     } else if (c > node.character) { 
      return get(node.right, key, index); 
     } else if(index < key.length() -1) { 
      return get(node.middle, key, index); 
     } else { 
      return node; 
     } 
    } 

    public void inorderTraversal(Node node) { 
     System.out.print(node.character + ":" + node.value + " "); 

     if(node.left != null) { 
      inorderTraversal(node.left); 
     } 
     if(node.middle != null) { 
      inorderTraversal(node.middle); 
     } 

     if(node.right != null) { 
      inorderTraversal(node.right); 
     } 
    } 

    public void traverse() { 
     inorderTraversal(root); 
    } 
} 

public class Main { 
    public static void main(String[] args) { 
     TST tst = new TST(); 
     tst.put("This",3); 
     tst.put("There",4); 
     tst.put("Them",5); 
     tst.put("High",6); 
     System.out.println(tst.get("T")); 
     tst.traverse(); 
    } 
} 

class Node { 
    public char character; 
    public Node left, right, middle; 
    public int value; 

    public Node(char character) { 
     this.character = character; 
    } 
} 

Answer 1

, 당신은 문자열 함께 전달해야 .

3 진 검색 트리의 정의에 따라 중간 노드로 이동할 때만이 접두어에 추가해야합니다.

구현 예 :

public void inorderTraversal(Node node, String word) { 
    // handle end of word 
    if (node.value != 0) { 
     System.out.println(word + node.character + ": " + node.value); 
    } 

    if(node.left != null) { 
     inorderTraversal(node.left, word); 
    } 

    if (node.middle != null) { 
     inorderTraversal(node.middle, word + node.character); 
    } 

    if(node.right != null) { 
     inorderTraversal(node.right, word); 
    } 
} 

public void traverse() { 
    inorderTraversal(root, ""); 
} 

Demo.

put 메서드에서 완전한 단어를 이미 가지고 있기 때문에 (메모리 사용에 대해 걱정하지 않는다면) 건설 중에 각 노드에 전체 단어를 나타내는 String을 저장할 수도 있습니다. 이/당신의 코드는 0 값으로 매핑 단어를 허용하지 않습니다

---

주 -이를 해결하는 방법은 다음의 종료를 확인하기 위해 != null을 사용할 수 있습니다, 대신 int의 Integer을 사용하는 것입니다 단어.