TireTree

package tiretree;

public class TireTree {// Baidu搜索用到的数据结构

private Node root;//根节点

public TireTree() {

root = new Node(); // 构造：Tree下面的Node

}

public void insert(String str) {

Node t = root;

for (int i = 0; i < str.length(); i++) {// i change , and t change

// 自己定义了一套规则，每一次都是26个位置对应到26个字母

if (t.nodes[str.charAt(i) - 'a'] == null) {// 如果不存在该位置

Node node = new Node();

t.nodes[str.charAt(i) - 'a'] = node;// 把新建的node位置赋给这个值->t.nodes[str.charAt(i) - 'a']

}

t = t.nodes[str.charAt(i) - 'a'];

}

t.isStr = true;// 令插入的最后一个字符为true

}

public boolean find(String str) {

// Node t = new Node();//root是TireTree构造出来的，这个root可以应用在find中去判断

Node t = root;

for (int i = 0; i < str.length() && t != null; i++) {// t != null ---->>对应的这个节点不为空

t = t.nodes[str.charAt(i) - 'a'];// 循环遍历

}

return (t != null && t.isStr);// 最后一位不为空且标志位为true，isStr：避免树中有abcde，abc也蒙混过关了

}

private class Node {// 代表每一个节点（一个字符）

boolean isStr; // 字符串末尾的标志

Node[] nodes; // Node[26]数组

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"));

}

}

运行结果为：

abc:true

abd:false

abcd:false

abcd:false

bc:false

bcd:true

cdefg:true

aaaaa:true