package tiretree;
public class TireTree {// Baidu搜索用到的數(shù)據(jù)結(jié)構(gòu)
private Node root;//根節(jié)點(diǎn)
public TireTree() {
root = new Node(); // 構(gòu)造：Tree下面的Node
}
public void insert(String str) {
Node t = root;
for (int i = 0; i < str.length(); i++) {// i change , and t change
// 自己定義了一套規(guī)則，每一次都是26個(gè)位置對(duì)應(yīng)到26個(gè)字母
if (t.nodes[str.charAt(i) - 'a'] == null) {// 如果不存在該位置
Node node = new Node();
t.nodes[str.charAt(i) - 'a'] = node;// 把新建的node位置賦給這個(gè)值->t.nodes[str.charAt(i) - 'a']
}
t = t.nodes[str.charAt(i) - 'a'];
}
t.isStr = true;// 令插入的最后一個(gè)字符為true
}
public boolean find(String str) {
// Node t = new Node();//root是TireTree構(gòu)造出來的梁厉，這個(gè)root可以應(yīng)用在find中去判斷
Node t = root;
for (int i = 0; i < str.length() && t != null; i++) {// t != null ---->>對(duì)應(yīng)的這個(gè)節(jié)點(diǎn)不為空
t = t.nodes[str.charAt(i) - 'a'];// 循環(huán)遍歷
}
return (t != null && t.isStr);// 最后一位不為空且標(biāo)志位為true爸舒，isStr：避免樹中有abcde盾戴，abc也蒙混過關(guān)了
}
private class Node {// 代表每一個(gè)節(jié)點(diǎn)（一個(gè)字符）
boolean isStr; // 字符串末尾的標(biāo)志
Node[] nodes; // Node[26]數(shù)組
Node() {
isStr = false;
nodes = new Node[26];
}
}
public static void main(String[] args) {
TireTree tireTree = new TireTree();
tireTree.insert("abc");
tireTree.insert("abc");
tireTree.insert("bcd");
tireTree.insert("cdefg");
tireTree.insert("aaaaa");
System.out.println("abc:" + tireTree.find("abc"));
System.out.println("abd:" + tireTree.find("abd"));
System.out.println("abcd:" + tireTree.find("abcd"));
System.out.println("abcd:" + tireTree.find("ab"));
System.out.println("bc:" + tireTree.find("bc"));
System.out.println("bcd:" + tireTree.find("bcd"));
System.out.println("cdefg:" + tireTree.find("cdefg"));
System.out.println("aaaaa:" + tireTree.find("aaaaa"));
}
}
運(yùn)行結(jié)果為：
abc:true
abd:false
abcd:false
abcd:false
bc:false
bcd:true
cdefg:true
aaaaa:true
