基本介紹
- 中文名：字典樹
- 外文名：trie tree
- 別名：單詞查找樹
- 類型：樹形結構
- 基本操作：查找、插入和刪除
性質,基本操作,實現方法,套用,串的快速檢索,“串”排序,最長公共前綴,代碼實現,Python,Java,C語言,C++,
性質
它有3個基本性質：
基本操作
其基本操作有：查找、插入和刪除,當然刪除操作比較少見。
實現方法
搜尋字典項目的方法為：
(1) 從根結點開始一次搜尋；
(2) 取得要查找關鍵字的第一個字母，並根據該字母選擇對應的子樹並轉到該子樹繼續進行檢索；
(3) 在相應的子樹上，取得要查找關鍵字的第二個字母,並進一步選擇對應的子樹進行檢索。
(4) 疊代過程……
(5) 在某個結點處，關鍵字的所有字母已被取出，則讀取附在該結點上的信息，即完成查找。
其他操作類似處理
套用
串的快速檢索
在這道題中，我們可以用數組枚舉，用哈希，用字典樹，先把熟詞建一棵樹，然後讀入文章進行比較，這種方法效率是比較高的。
“串”排序
給定N個互不相同的僅由一個單詞構成的英文名，讓你將他們按字典序從小到大輸出
用字典樹進行排序，採用數組的方式創建字典樹，這棵樹的每個結點的所有兒子很顯然地按照其字母大小排序。對這棵樹進行先序遍歷即可。
最長公共前綴
對所有串建立字典樹，對於兩個串的最長公共前綴的長度即他們所在的結點的公共祖先個數，於是，問題就轉化為當時公共祖先問題。
代碼實現
Python
class Trie:
# 初始化
def __init__(self):
self.root = {}
self.end = "#"
# 添加單詞
def add(self, word: str):
node = self.root
for char in word:
node = node.setdefault(char, {})
node[self.end] = None
# 搜尋單詞是否存在
def search(self, word):
node = self.root
for char in word:
if char not in node:
return False
node = node[char]
return self.end in node
Java
packagecom.suning.search.test.tree.trie;
public class Trie
{
private int SIZE=26;
private TrieNode root;//字典樹的根
Trie() //初始化字典樹
{
root=new TrieNode();
}
private class TrieNode //字典樹節點
{
private int num;//有多少單詞通過這個節點,即由根至該節點組成的字元串模式出現的次數
private TrieNode[] son;//所有的兒子節點
private boolean isEnd;//是不是最後一個節點
private char val;//節點的值
private boolean haveSon;
TrieNode()
{
num=1;
son=new TrieNode[SIZE];
isEnd=false;
haveSon=false;
}
}
//建立字典樹
public void insert(String str) //在字典樹中插入一個單詞
{
if(str==null||str.length()==0)
{
return;
}
TrieNode node=root;
char[]letters=str.toCharArray();
for(int i=0,len=str.length(); i<len; i++)
{
int pos=letters[i]-'a';
if(node.son[pos]==null)
{
node.haveSon = true;
node.son[pos]=new TrieNode();
node.son[pos].val=letters[i];
}
else
{
node.son[pos].num++;
}
node=node.son[pos];
}
node.isEnd=true;
}
//計算單詞前綴的數量
public int countPrefix(Stringprefix)
{
if(prefix==null||prefix.length()==0)
{
return-1;
}
TrieNode node=root;
char[]letters=prefix.toCharArray();
for(inti=0,len=prefix.length(); i<len; i++)
{
int pos=letters[i]-'a';
if(node.son[pos]==null)
{
return 0;
}
else
{
node=node.son[pos];
}
}
return node.num;
}
//列印指定前綴的單詞
public String hasPrefix(String prefix)
{
if (prefix == null || prefix.length() == 0)
{
return null;
}
TrieNode node = root;
char[] letters = prefix.toCharArray();
for (int i = 0, len = prefix.length(); i < len; i++)
{
int pos = letters[i] - 'a';
if (node.son[pos] == null)
{
return null;
}
else
{
node = node.son[pos];
}
}
preTraverse(node, prefix);
return null;
}
// 遍歷經過此節點的單詞.
public void preTraverse(TrieNode node, String prefix)
{
if (node.haveSon)
{
for (TrieNode child : node.son)
{
if (child!=null)
{
preTraverse(child, prefix+child.val);
}
}
return;
}
System.out.println(prefix);
}
//在字典樹中查找一個完全匹配的單詞.
public boolean has(Stringstr)
{
if(str==null||str.length()==0)
{
return false;
}
TrieNode node=root;
char[]letters=str.toCharArray();
for(inti=0,len=str.length(); i<len; i++)
{
intpos=letters[i]-'a';
if(node.son[pos]!=null)
{
node=node.son[pos];
}
else
{
return false;
}
}
return node.isEnd;
}
//前序遍歷字典樹.
public void preTraverse(TrieNodenode)
{
if(node!=null)
{
System.out.print(node.val+"-");
for(TrieNodechild:node.son)
{
preTraverse(child);
}
}
}
public TrieNode getRoot()
{
return this.root;
}
public static void main(String[]args)
{
Trietree=newTrie();
String[]strs= {"banana","band","bee","absolute","acm",};
String[]prefix= {"ba","b","band","abc",};
for(Stringstr:strs)
{
tree.insert(str);
}
System.out.println(tree.has("abc"));
tree.preTraverse(tree.getRoot());
System.out.println();
//tree.printAllWords();
for(Stringpre:prefix)
{
int num=tree.countPrefix(pre);
System.out.println(pre+""+num);
}
}
}
C語言
#define MAX 26//字元集大小
typedef struct TrieNode
{
int nCount;//記錄該字元出現次數
struct TrieNode* next[MAX];
}TrieNode;
TrieNode Memory[1000000];
int allocp=0;
/*初始化*/
void InitTrieRoot(TrieNode* *pRoot)
{
*pRoot=NULL;
}
/*創建新結點*/
TrieNode* CreateTrieNode()
{
int i;
TrieNode *p;
p=&Memory[allocp++];
p->nCount=1;
for(i=0;i<MAX;i++)
{
p->next[i]=NULL;
}
return p;
}
/*插入*/
void InsertTrie(TrieNode* *pRoot,char *s)
{
int i,k;
TrieNode*p;
if(!(p=*pRoot))
{
p=*pRoot=CreateTrieNode();
}
i=0;
while(s[i])
{
k=s[i++]-'a';//確定branch
if(!p->next[k])
p->next[k]=CreateTrieNode();
else
p->next[k]->nCount++;
p=p->next[k];
}
}
//查找
int SearchTrie(TrieNode* *pRoot,char *s)
{
TrieNode *p;
int i,k;
if(!(p=*pRoot))
{
return0;
}
i=0;
while(s[i])
{
k=s[i++]-'a';
if(p->next[k]==NULL) return 0;
p=p->next[k];
}
return p->nCount;
}
C++
#include <cstring>
#include <iostream>
#include <conio.h>
using namespace std;
namespace trie
{
template <class T, size_t CHILD_MAX>
/*
Parameter T: Type of reserved data.
Parameter CHILD_MAX: Size of the array of pointers to childnode.
*/
struct nod
{
T reserved;
nod<T, CHILD_MAX> *child[CHILD_MAX];
nod()
{
memset(this, 0, sizeof *this);
}
~nod()
{
for (unsigned i = 0; i < CHILD_MAX; i++)
delete child[i];
}
void Traversal(char *str, unsigned index)
{
unsigned i;
for (i = 0; i < index; i++)
cout << str[i];
cout << '\t' << reserved << endl;
for (i = 0; i < CHILD_MAX; i++)
{
if (child[i])
{
str[index] = i;
child[i]->Traversal(str, index + 1);
}
}
return;
}
};
template <class T, size_t CHILD_MAX = 127>
/*
Parameter T: Type of reserved data.
Parameter CHILD_MAX: Size of the array of pointers to childnode.
*/
class trie
{
private:
nod<T, CHILD_MAX> root;
public:
nod<T, CHILD_MAX> *AddStr(char *str);
nod<T, CHILD_MAX> *FindStr(char *str);
bool DeleteStr(char *str);
void Traversal()
{
char str[100];
root.Traversal(str, 0);
}
};
template <class T, size_t CHILD_MAX>
nod<T, CHILD_MAX> * trie<T, CHILD_MAX>::AddStr(char *str)
{
nod<T, CHILD_MAX> *now = &root;
do
{
if (now->child[*str] == NULL)
now->child[*str] = new nod<T, CHILD_MAX>;
now = now->child[*str];
}
while (*(++str) != '\0');
return now;
}
template <class T, size_t CHILD_MAX>
nod<T, CHILD_MAX> *trie<T, CHILD_MAX>::FindStr(char *str)
{
nod<T, CHILD_MAX> *now = &root;
do
{
if (now->child[*str] == NULL)
return NULL;
now = now->child[*str];
}
while (*(++str) != '\0');
return now;
}
template <class T, size_t CHILD_MAX>
bool trie<T, CHILD_MAX>::DeleteStr(char *str)
{
nod<T, CHILD_MAX> **nods = new nod<T, CHILD_MAX> *[strlen(str)];
int snods = 1;
nod<T, CHILD_MAX> *now = &root;
nods[0] = &root;
do
{
if (now->child[*str] == NULL)
return false;
nods[snods++] = now = now->child[*str];
}
while (*(++str) != '\0');
snods--;
while (snods > 0)
{
for (unsigned i = 0; i < CHILD_MAX; i++)
if (nods[snods]->child[i] != NULL)
return true;
delete nods[snods];
nods[--snods]->child[*(--str)] = NULL;
}
return true;
}
} // namespace trie
int main()
{
//TestProgram
trie::trie<int> tree;
while (1)
{
cout << "1 for add a string" << endl;
cout << "2 for find a string" << endl;
cout << "3 for delete a string" << endl;
cout << "4 for traversal" << endl;
cout << "5 for exit" << endl;
char str[100];
switch (getch())
{
case '1':
cout << "Input a string: ";
cin.getline(str, 100);
cout << "This string has existed for " << tree.AddStr(str)->reserved++ << " times." << endl;
break;
case '2':
cout << "Input a string: ";
cin.getline(str, 100);
trie::nod<int, 127> *find;
find = tree.FindStr(str);
if (!find)
cout << "No found." << endl;
else
cout << "This string has existed for " << find->reserved << " times." << endl;
break;
case '3':
cout << "Input a string: ";
cin.getline(str, 100);
cout << "The action is " << (tree.DeleteStr(str) ? "Successful." : "Unsuccessful.") << endl;
break;
case '4':
cout << "Traversal the tree: " << endl;
tree.Traversal();
break;
case '5':
cout << "Exit." << endl;
return 0;
}
}
return 0;
}
