Wie drucke ich alle Wörter in einem Trie aus?

Question

Ich habe eine Ternary Suche Baum (Trie) und ich möchte alle Wörter darin ausdrucken.

Wie gehe ich über diese aktuelle Implementierung, die ich unten habe? Ich habe eine Standard put Methode, um neue Wörter zum Baum hinzuzufügen. Ich habe versucht, die Wörter mit einer In-Order-Traversierung zu drucken, aber ich bin mir nicht sicher, wie genau ich die Funktion vervollständige.

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

Da jeder Knoten nur ein einzelnes Zeichen speichert, müssen Sie entlang einer Schnur passieren (oder String, wenn Sie versuchen, effizient zu sein), die das Präfix durch den Pfad von der Wurzel definiert, wenn Ihr Traversal tun .

Gemäß der Definition eines ternären Suchbaums sollten Sie nur an dieses Präfix anhängen, wenn Sie zum mittleren Knoten gehen.

Eine beispielhafte Implementierung:

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.

Es ist auch möglich, die Zeichenkette zu speichern, die das vollständige Wort an jedem Knoten während der Konstruktion darstellt, da Sie bereits das vollständige Wort in Ihrer put Methode haben (wenn Sie sich nicht um die Speichernutzung sorgen).

---

Beachten Sie, dass dieser/Code nicht für die Zuordnung von Worten läßt auf einen Wert 0 - eine Möglichkeit, das zu lösen ist Integer zu verwenden, anstatt int, dann können Sie != null verwenden für das Ende überprüfen von ein Wort.