• TrieNode.java

/**

 * 給定一個(gè)固定電話號(hào)碼，找出這個(gè)號(hào)碼對(duì)應(yīng)的區(qū)域。固定電話號(hào)碼都是以0開始的多位數(shù)字，可以通過(guò)給定電話號(hào)碼的前綴找出對(duì)已ing的區(qū)域

 * 如：

 * 0995：新疆：托克遜縣

 * 0856：貴州：銅仁

 * 0775：廣西：玉林

 * 可以采用數(shù)字搜索樹算法快速查找電話號(hào)碼前綴。*/

public final class TrieNode {

    protected TrieNode[] children;//孩子節(jié)點(diǎn)

    protected char splitChar;//分隔字符

    protected String area;//電話所屬地區(qū)信息

    

    protected TrieNode(char splitchar){

        children=new TrieNode[10];

        area=null;

        this.splitChar=splitchar;

    }

    /**

     * 加載詞，形成數(shù)字搜索樹

     * param:string輸入的電話號(hào)碼

     * param:root樹根

     * area:所在區(qū)域*/

    void addWord(String string, TrieNode root,String area){

        TrieNode tNode=root;

        //第一個(gè)字符都是0，作為根節(jié)點(diǎn)

        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;

        }

    }

    /**

     * 查詢的過(guò)程對(duì)于查詢?cè)~來(lái)說(shuō)，從前往后一個(gè)字符一個(gè)字符的匹配。對(duì)于Trie樹來(lái)說(shuō)，是從根節(jié)點(diǎn)往下匹配的過(guò)程。

     * 從給定電話號(hào)碼搜索前綴的方法如下：*/

    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;

            }

        }

        //沒(méi)找到

        return null;

    }

}

• TrieTreeTest.java

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);

    }

}