如何使用线程run（）实现Trie迭代器

Question

我有一个uni分配，我需要实现一个Trie，它是节点（Node）和迭代器。

迭代器应使用StringBuffer遍历节点以维护单词的状态，并应实现Runnable接口，这意味着我必须实现run()方法！

我已经尝试过此实现：

class NodeIterator implements Iterator<String>, Runnable {
    String nextWord;
    boolean terminated;
    Thread thread;

    public NodeIterator() {
        thread = new Thread(this,"Node iterator");
        thread.start();
    }

    @Override
    public void run() {
        terminated = false;

        visit(Trie.this.root);

        synchronized (this) {
            terminated = true;
            handshake();
        }
    }

    private void visit(Node node) {

    }

    private void handshake() {
        notify();

        try {
            wait();
        } catch (InterruptedException e) {

        }
    }

    @Override
    public boolean hasNext() {
        synchronized (this) {
            if(!terminated)
                handshake();
        }

        return nextWord != null;
    }

    @Override
    public String next() {
        String word = nextWord;

        synchronized (this) {
            word = null;
        }

        return word;
    }
}

我不知道visit()方法的实现，因为我不确定如何“访问”节点，并且我不确定其余方法是否正确，因为我从未使用过线程。

我应该做些不同的事情吗？

编辑：

public class Trie implements Iterable<String> {
    Node root;

    ...

    private static class Node {
        private HashMap<Character, Node> children;
        private boolean endOfWord;

        ...
    }
}

Answer 1

实现visit()的一种方法是递归。递归方法需要跟踪到目前为止构建的字符串的前缀，并且如果找到一个以单词结尾的节点，则将其发布到现在为止已经找到的字符串。假设您无法更改visit(Node)的签名，则需要一个辅助方法：

    void visit(Node root) {
        visitRecursive("", root);
    }

    private void visitRecursive(String prefix, Node node) {
        if (node.endOfWord) {
            nextWord = prefix;
            synchronized (this) {
                handshake();
            }
        }
        for (Map.Entry<Character, Node> entry : node.children.entrySet()) {
            visitRecursive(prefix + entry.getKey(), entry.getValue());
        }
    }

我不确定您所有的多线程代码是否正确，但是最起码，这将遍历trie中存储的所有字符串。