-
Notifications
You must be signed in to change notification settings - Fork 47
/
TST.java
93 lines (87 loc) · 1.48 KB
/
TST.java
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
//基于三向单词查找树的符号表
public class TST<Value> {
private Node root;
private class Node
{
char c;
Node left, mid, right;
Value val;
}
public Value get(String key)
{
Node x = get(root, key, 0);
if(x == null)
{
return null;
}
return x.val;
}
private Node get(Node x, String key, int d)
{
if(x == null)
{
return null;
}
char c = key.charAt(d);
if(c < x.c)
{
return get(x.left, key, d);
}
else if(c > x.c)
{
return get(x.right, key, d);
}
else if(d < key.length() - 1)
{
return get(x.mid, key, d + 1);
}
else
{
return x;
}
}
public void put(String key, Value val)
{
root = put(root, key, val, 0);
}
private Node put(Node x, String key, Value val, int d)
{
char c = key.charAt(d);
if(x == null)
{
x = new Node();
x.c = c;
}
if(c < x.c)
{
x.left = put(x.left, key, val, d);
}
else if(c > x.c)
{
x.right = put(x.right, key, val, d);
}
else if(d < key.length() - 1)
{
x.mid = put(x.mid, key, val, d + 1);
}
else
{
x.val = val;
}
return x;
}
public static void main(String[] args)
{
TST<Integer> newTST = new TST<Integer>();
String[] keys= {"Nicholas", "Nate", "Jenny", "Penny", "Cynthina", "Michael"};
for(int i = 0; i < keys.length; i++)
{
newTST.put(keys[i], i);
}
for(int i = 0; i < keys.length; i++)
{
int val = newTST.get(keys[i]);
System.out.println(keys[i] + " " + val);
}
}
}