反饋

字典樹

又稱單詞查找樹，Trie樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用於統計，排序和保存大量的字符串（但不僅限於字符串），所以經常被搜索引擎系統用於文本詞頻統計。它的優點是：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。

中文名: 字典樹
外文名: trie tree

別名: 單詞查找樹
類型: 樹形結構
基本操作: 查找、插入和刪除

字典樹性質

它有3個基本性質：

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

字典樹基本操作

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

字典樹實現方法

搜索字典項目的方法為：

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

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

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

(4) 迭代過程……

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

其他操作類似處理

字典樹應用

字典樹串的快速檢索

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

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

字典樹“串”排序

給定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;
}