1

我有一个三元搜索树（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;
    }
}
4

1 回答 1

1

由于每个节点只存储一个字符，因此在进行遍历时，您需要传递一个字符串（或 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, "");
}

演示。

也可以在构造过程中在每个节点存储表示完整单词的字符串，因为您的put方法中已经有了完整的单词（如果您不担心内存使用情况）。

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

于 2017-12-27T15:00:16.457 回答