java - 打印树组件

Question

我是 java 的新手，我想创建一个非常简单的“单词完成”程序。我将阅读字典文件并递归地将单词添加到节点数组(大小为 26)中。我相信我已经成功地做到了这一点，但我不确定如何完成并打印比赛。为了测试，我现在只是通过调用函数插入 2 个单词。一旦一切正常，我将添加读取文件并从 word 中删除垃圾的方法。

例如:如果单词“test”和“tester”在树中并且用户输入“tes”，它应该显示“test”和“tester”。

如果有人能告诉我如何完成并打印匹配项(如果有的话)，我将不胜感激。完整代码如下。

谢谢

Answer 1

你实现了什么 is called "trie" .您可能想查看现有的实现。

您用来存储子节点的称为哈希表，您可能希望使用标准实现并避免自己实现它，除非您有非常非常具体的理由这样做。您的实现有一些限制(例如字符范围)。

---

我认为，您的代码在方法 has 中有一个错误:

...
else if (letter[val].flag==true || word.length()==1) {
    return true;
}

如果该方法旨在在存在以 word 开头的字符串时返回 true，则它不应检查 flag。如果只有完全匹配才必须返回 true，则不应检查 word.length()。

最后，解决您的问题:这不是最佳解决方案，但最简单的解决方案是创建一个方法，该方法接受一个字符串并返回一个与该字符串匹配的节点，以及一个由节点中的所有单词组成的方法。像这样(未经测试):

class Tree {

    ...
    public List<String> matches(CharSequence prefix) {
        List<String> result = new ArrayList<>();
        if(r != null) {
            Node n = r._match(prefix, 0);
            if(n != null) {
                StringBuilder p = new StringBuilder();
                p.append(prefix);
                n._addWords(p, result);
            }
        }
        return result;
    }
}

class Node {

    ...
    protected Node _match(CharSequence prefix, int index) {
        assert index <= prefix.length();
        if(index == prefix.length()) {
            return this;
        }
        int val = prefix.charAt(index) - 'a';
        assert val >= 0 && val < letter.length;
        if (letter[val] != null) {
            return letter[val].match(prefix, index+1);
        }
        return null;
    }

    protected void _addWords(StringBuilder prefix, List<String> result) {
        if(this.flag) {
            result.add(prefix.toString());
        }    
        for(int i = 0; i<letter.length; i++) {
            if(letter[i] != null) {
                prefix.append((char)(i + 'a'));
                letter[i]._addWords(prefix, result);
                prefix.delete(prefix.length() - 1, prefix.length());
            }
        }
    }
}