TireTree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
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"));

}

}

运行结果为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
abc:true

abd:false

abcd:false

abcd:false

bc:false

bcd:true

cdefg:true

aaaaa:true

作者:有奶喝先森
链接:http://www.jianshu.com/p/88bb88051730
來源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。