How do I print all the words out in a Trie?

java algorithm data-structures ternary-search-tree

972 观看

1回复

0 作者的声誉

I have a Ternary Search Tree (Trie) and I want to print out all of the words in it.

How do I go about this using this current implementation that I have below? I have a standard put method to add new words to the tree. I was attempting to print the words using an in-order traversal, but I'm unsure how exactly to complete the function.

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;
    }
}
作者: user9145291 的来源 发布者: 2017 年 12 月 27 日

回应 (1)


0

46540 作者的声誉

决定

Since each node only stores a single character, you need to pass along a String (or StringBuilder, if you're trying to be efficient) representing the prefix defined by the path from the root when doing your traversal.

As per the definition of a ternary search tree, you should only append to this prefix when going to the middle node.

An example implementation:

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.

It's also possible to store the String representing the full word at each node during construction, since you already have the complete word in your put method (if you're not worried about the memory usage).


Note that this / your code doesn't allow for mapping words to a 0 value - one way to deal with that is to use Integer instead of int, then you can use != null to check for the end of a word.

作者: Dukeling 发布者: 27.12.2017 03:00
32x32