如何使用 Thread 运行() 实现 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() 方法的实现，因为我不确定如何 "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 中的所有字符串。

如何使用 Thread 运行() 实现 Trie 迭代器

How to implement a Trie Iterator with Thread run()

java

multithreading

thread-safety

trie