/**
* 給定一個固定電話號碼，找出這個號碼對應的區(qū)域。固定電話號碼都是以0開始的多位數(shù)字，可以通過給定電話號碼的前綴找出對已ing的區(qū)域
* 如：
* 0995：新疆：托克遜縣
* 0856：貴州：銅仁
* 0775：廣西：玉林
* 可以采用數(shù)字搜索樹算法快速查找電話號碼前綴。*/
public final class TrieNode {
protected TrieNode[] children;//孩子節(jié)點
protected char splitChar;//分隔字符
protected String area;//電話所屬地區(qū)信息
protected TrieNode(char splitchar){
children=new TrieNode[10];
area=null;
this.splitChar=splitchar;
}
/**
* 加載詞，形成數(shù)字搜索樹
* param:string輸入的電話號碼
* param:root樹根
* area:所在區(qū)域*/
void addWord(String string, TrieNode root,String area){
TrieNode tNode=root;
//第一個字符都是0，作為根節(jié)點
for(int i=1;i<string.length();i++){
char c0=string.charAt(i);
int ind=Integer.parseInt(string.substring(i, i+1));
TrieNode tempNode=tNode.children[ind];
if(null==tempNode){
tempNode=new TrieNode(c0);
}
if(i==string.length()-1){
tempNode.area=area;
}
tNode.children[ind]=tempNode;
tNode=tempNode;
}
}
/**
* 查詢的過程對于查詢詞來說，從前往后一個字符一個字符的匹配。對于Trie樹來說，是從根節(jié)點往下匹配的過程。
* 從給定電話號碼搜索前綴的方法如下：*/
public String search(String tel,TrieNode root){
TrieNode tNode=root;
for(int i=1;i<tel.length();i++){
tNode=tNode.children[(tel.charAt(i)-'0')];
if(null!=tNode.area){
return tNode.area;
}
}
//沒找到
return null;
}
}
public class TrieTreeTest {
public static void main(String args[]){
TrieNode root=new TrieNode('0');
root.addWord("0995", root, "新疆：托克遜縣");
root.addWord("0856", root, "貴州：銅仁");
root.addWord("0775", root, "廣西：玉林");
String result=root.search("0775", root);
System.out.println("0775:"+result);
result=root.search("0856", root);
System.out.println("0856:"+result);
}
}
最后編輯于 ：
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。
