Как распечатать все слова в 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, "");
}

Демо

Также возможно сохранить строку, представляющую полное слово в каждом узле во время построения, так как у вас уже есть полное слово в вашем put метод (если вы не беспокоитесь об использовании памяти).

---

Обратите внимание, что этот / ваш код не позволяет отображать слова в значение 0 - один из способов справиться с этим - использовать Integer вместо intтогда вы можете использовать != null проверить конец слова.