我如何打印 Trie 中的所有单词？

Question

我有一个三元搜索树 (Trie)，我想打印出其中的所有单词。

我如何使用下面的当前实现来解决这个问题？我有一个标准的 put 方法来向树中添加新词。我试图使用中序遍历打印单词，但我不确定如何完成该功能。

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

由于每个节点仅存储一个字符，因此您需要传递一个 String（或 StringBuilder，如果您想要高效），表示在进行遍历时从根开始的路径定义的前缀。

根据三元搜索树的定义，您应该只在转到中间节点时附加此前缀。

示例实现：

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 方法中拥有完整的单词（如果您不担心内存使用）。

请注意，此/您的代码不允许将单词映射到 0 值 - 一种处理方法是使用 Integer 而不是 int，然后您可以使用 != null 检查单词的结尾。

我如何打印 Trie 中的所有单词？

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

java

algorithm

data-structures

ternary-search-tree