Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit1b48916

Browse files
committed
trie
1 parent85ab658 commit1b48916

File tree

3 files changed

+142
-0
lines changed

3 files changed

+142
-0
lines changed

‎pom.xml

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@
1919
<module>cyclefinding</module>
2020
<module>leecode</module>
2121
<module>recursion</module>
22+
<module>trie</module>
2223
</modules>
2324

2425
<dependencies>

‎trie/pom.xml

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<projectxmlns="http://maven.apache.org/POM/4.0.0"
3+
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
4+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
5+
<parent>
6+
<artifactId>learn-algorithm</artifactId>
7+
<groupId>org.example</groupId>
8+
<version>1.0-SNAPSHOT</version>
9+
</parent>
10+
<modelVersion>4.0.0</modelVersion>
11+
12+
<artifactId>trie</artifactId>
13+
14+
15+
</project>
Lines changed: 126 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,126 @@
1+
packagecom.flydean;
2+
3+
/**
4+
* @author wayne
5+
* @version Trie, 2020/11/5
6+
*/
7+
publicclassTrie {
8+
// 假如字典中的单词只有26个英文字母
9+
staticfinalintALPHABET_SIZE =26;
10+
11+
// Trie的node节点
12+
staticclassTrieNode
13+
{
14+
TrieNode[]children =newTrieNode[ALPHABET_SIZE];
15+
16+
// 这个节点是否是结束节点
17+
booleanisEndOfWord;
18+
19+
//初始化TireNode节点
20+
TrieNode(){
21+
isEndOfWord =false;
22+
for (inti =0;i <ALPHABET_SIZE;i++)
23+
children[i] =null;
24+
}
25+
}
26+
27+
staticTrieNoderoot=newTrieNode();
28+
29+
// 如果当前level中不存在，那么就会在特定的位置插入新的节点
30+
// 如果当前level中存在该字符，则从其子节点继续插入
31+
// 最后，将该叶子节点标记为isEndOfWord。
32+
staticvoidinsert(Stringkey)
33+
{
34+
intlevel;
35+
intlength =key.length();
36+
intindex;
37+
38+
TrieNodecurrentNode =root;
39+
40+
for (level =0;level <length;level++)
41+
{
42+
index =key.charAt(level) -'a';
43+
if (currentNode.children[index] ==null)
44+
currentNode.children[index] =newTrieNode();
45+
46+
currentNode =currentNode.children[index];
47+
}
48+
49+
// 将叶子节点标记为 isEndOfWord
50+
currentNode.isEndOfWord =true;
51+
}
52+
53+
// 执行搜索，也是按level来进行查询
54+
staticbooleansearch(Stringkey)
55+
{
56+
intlevel;
57+
intlength =key.length();
58+
intindex;
59+
TrieNodecurrentNode =root;
60+
61+
for (level =0;level <length;level++)
62+
{
63+
index =key.charAt(level) -'a';
64+
65+
if (currentNode.children[index] ==null)
66+
returnfalse;
67+
68+
currentNode =currentNode.children[index];
69+
}
70+
71+
return (currentNode !=null &&currentNode.isEndOfWord);
72+
}
73+
74+
//判断该节点是否有子节点
75+
staticbooleanhasChild(TrieNodecurrentNode)
76+
{
77+
for (inti =0;i <ALPHABET_SIZE;i++)
78+
if (currentNode.children[i] !=null)
79+
returntrue;
80+
returnfalse;
81+
}
82+
83+
staticTrieNoderemove(TrieNodecurrentNode,Stringkey,intlevel ){
84+
if(currentNode ==null){
85+
returnnull;
86+
}
87+
88+
intlength =key.length();
89+
90+
//正在处理最后一个字符
91+
if(level ==length){
92+
//将当前节点的标志位删除
93+
if(currentNode.isEndOfWord){
94+
currentNode.isEndOfWord=false;
95+
}
96+
//如果没有子节点，则只接受删除该节点
97+
if (!hasChild(currentNode)) {
98+
currentNode =null;
99+
}
100+
101+
returncurrentNode;
102+
}
103+
104+
// 如果不是最后一个节点，则递归调用其子节点
105+
intindex =key.charAt(level) -'a';
106+
currentNode.children[index] =
107+
remove(currentNode.children[index],key,level +1);
108+
109+
// 如果当前节点既没有子节点，也不是其他单词的结束节点，那么直接将这个节点删除即可。
110+
if (!hasChild(currentNode) &&currentNode.isEndOfWord ==false) {
111+
currentNode =null;
112+
}
113+
returncurrentNode;
114+
}
115+
116+
publicstaticvoidmain(Stringargs[])
117+
{
118+
Stringkeys[] = {"www","flydean","com","is","a",
119+
"good","website"};
120+
121+
// 构造Trie tree
122+
inti;
123+
for (i =0;i <keys.length ;i++)
124+
insert(keys[i]);
125+
}
126+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp