字典樹

性質

它有3個基本性質：

根節點不包含字元，除根節點外每一個節點都只包含一個字元；從根節點到某一節點，路徑上經過的字元連線起來，為該節點對應的字元串；每個節點的所有子節點包含的字元都不相同。

基本操作

其基本操作有：查找、插入和刪除,當然刪除操作比較少見。

實現方法

搜尋字典項目的方法為：

(1) 從根結點開始一次搜尋；

(2) 取得要查找關鍵字的第一個字母，並根據該字母選擇對應的子樹並轉到該子樹繼續進行檢索；

(3) 在相應的子樹上，取得要查找關鍵字的第二個字母,並進一步選擇對應的子樹進行檢索。

(4) 疊代過程……

(5) 在某個結點處，關鍵字的所有字母已被取出，則讀取附在該結點上的信息，即完成查找。

其他操作類似處理

套用

串的快速檢索

給出N個單詞組成的熟詞表，以及一篇全用小寫英文書寫的文章，請你按最早出現的順序寫出所有不在熟詞表中的生詞。

在這道題中，我們可以用數組枚舉，用哈希，用字典樹，先把熟詞建一棵樹，然後讀入文章進行比較，這種方法效率是比較高的。

“串”排序

給定N個互不相同的僅由一個單詞構成的英文名，讓你將他們按字典序從小到大輸出

用字典樹進行排序，採用數組的方式創建字典樹，這棵樹的每個結點的所有兒子很顯然地按照其字母大小排序。對這棵樹進行先序遍歷即可。

最長公共前綴

對所有串建立字典樹，對於兩個串的最長公共前綴的長度即他們所在的結點的公共祖先個數，於是，問題就轉化為當時公共祖先問題。

代碼實現

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;//節點的值        TrieNode()        {            num=1;            son=new TrieNode[SIZE];            isEnd=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.son[pos]=newTrieNode();                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.isEnd)        {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);        }    }}

字典樹

基本介紹

性質