天天看點
傳回

HihoCoder 1014 : Trie樹

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

它有3個基本特性：

- 根節點不包含字元，除根節點外每一個節點都隻包含一個字元。

- 從根節點到某一節點，路徑上經過的字元連接配接起來，為該節點對應的字元串。

- 每個節點的所有子節點包含的字元都不相同。

應用

  • 串的快速檢索

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

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

  • “串”排序

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

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

  • 最長公共字首

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

代碼實作

Java

packagecom.suning.search.test.tree.trie;

public class Trie{
private int SIZE=;
private TrieNode root;  //字典樹的根

Trie(){     //初始化字典樹 
root=new TrieNode();
}

private class TrieNode{     //字典樹節點
    private int num;            //有多少單詞通過這個節點,即節點字元出現的次數
    private TrieNode[] son;     //所有的兒子節點
    private boolean isEnd;      //是不是最後一個節點
    private char val;           //節點的值

    TrieNode(){
    num=;
    son=new TrieNode[SIZE];
    isEnd=false;
    }
}

//建立字典樹
public void insert(String str){     //在字典樹中插入一個單詞
    if(str==null||str.length()==){
    return;
    }
    TrieNode node=root;
    char[]letters=str.toCharArray();
    for(inti=,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()==){
        return-;
    }
    TrieNode node=root;
    char[]letters=prefix.toCharArray();
    for(inti=,len=prefix.length();i<len;i++){
        int pos=letters[i]-'a';
        if(node.son[pos]==null){
            return ;
        } 
        else{
            node=node.son[pos];
        }
    }
    return node.num;
}

//在字典樹中查找一個完全比對的單詞.
public boolean has(Stringstr){
    if(str==null||str.length()==){
        return false;
    }
    TrieNode node=root;
    char[]letters=str.toCharArray();
    for(inti=,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[];
int allocp=;

/*初始化*/
void InitTrieRoot(TrieNode* *pRoot)
{
    *pRoot=NULL;
}

/*建立新結點*/
TrieNode* CreateTrieNode()
{
    int i;
    TrieNode *p;
    p=&Memory[allocp++];
    p->nCount=;
    for(i=;i<MAX;i++)
    {
        p->next[i]=NULL;
    }
    return p;
}

/*插入*/
void InsertTrie(TrieNode* *pRoot,char *s)
{
    inti,k;
    TrieNode*p;
    if(!(p=*pRoot))
    {
        p=*pRoot=CreateTrieNode();
    }
    i=;
    while(s[i])
    {
        k=s[i++]-'a';//确定branch
        if(!p->next[k])
            p->next[k]=CreateTrieNode();
                p->next[k]->nCount++;
        p=p->next[k];
    }
}

//查找
int SearchTrie(TrieNode* *pRoot,char *s)
{
    TrieNode *p;
    int i,k;
    if(!(p=*pRoot))
    {
        return0;
    }
    i=;
    while(s[i])
    {
        k=s[i++]-'a';
        if(p->next[k]==NULL) return ;
        p=p->next[k];
    }
    return p->nCount;
}

C++

#include<cstring>
#include<iostream>
#include<conio.h>
usingnamespacestd;
namespacetrie
{
    template<classT,size_tCHILD_MAX>
    /*
    ParameterT:Typeofreserveddata.
    ParameterCHILD_MAX:Sizeofarryofpointerstochildnode.
    */
    structnod
    {
        Treserved;
        nod<T,CHILD_MAX>*child[CHILD_MAX];
        nod()
        {
            memset(this,,sizeof*this);
        }
        ~nod()
        {
            for(unsignedi=;i<CHILD_MAX;i++)
            deletechild[i];
        }
        voidTraversal(char*str,unsignedindex)
        {
            unsignedi;
            for(i=;i<index;i++)
                cout<<str[i];
            cout<<'\t'<<reserved<<endl;
            for(i=;i<CHILD_MAX;i++)
            {
                if(child[i])
                {
                    str[index]=i;
                    child[i]->Traversal(str,index+);
                }
            }
            return;
        }
    };

    template<classT,size_tCHILD_MAX=>
    /*
    ParameterT:Typeofreserveddata.
    ParameterCHILD_MAX:Sizeofarryofpointerstochildnode.
    */
    classtrie
    {
        private:
        nod<T,CHILD_MAX>root;
        public:
        nod<T,CHILD_MAX>*AddStr(char*str);
        nod<T,CHILD_MAX>*FindStr(char*str);
        boolDeleteStr(char*str);
        voidTraversal()
        {
            charstr[];
            root.Traversal(str,);
        }
    };

    template<classT,size_tCHILD_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]=newnod<T,CHILD_MAX>;
        now=now->child[*str];
    }while(*(++str)!='\0');
    returnnow;
}

template<classT,size_tCHILD_MAX>
nod<T,CHILD_MAX>*trie<T,CHILD_MAX>::FindStr(char*str)
{
    nod<T,CHILD_MAX>*now=&root;
    do
    {
        if(now->child[*str]==NULL)
        returnNULL;
        now=now->child[*str];
    }while(*(++str)!='\0');
    returnnow;
}

template<classT,size_tCHILD_MAX>
booltrie<T,CHILD_MAX>::DeleteStr(char*str)
{
    nod<T,CHILD_MAX>**nods=newnod<T,CHILD_MAX>*[strlen(str)];
    intsnods=;
    nod<T,CHILD_MAX>*now=&root;
    nods[]=&root;
    do
    {
        if(now->child[*str]==NULL)
        return false;
        nods[snods++]=now=now->child[*str];
        }while(*(++str)!='\0');
        snods--;
        while(snods>)
        {
            for(unsignedi=;i<CHILD_MAX;i++)
                if(nods[snods]->child[i]!=NULL)
                    returntrue;
            deletenods[snods];
            nods[--snods]->child[*(--str)]=NULL;
        }
        return true;
    }
}
intmain()
{
    //TestProgram
    trie::trie<int>tree;
    while()
    {
        cout<<"1foraddastring"<<endl;
        cout<<"2forfindastring"<<endl;
        cout<<"3fordeleteastring"<<endl;
        cout<<"4fortraversal"<<endl;
        cout<<"5forexit"<<endl;
        charstr[];
        switch(getch())
        {
        case'1':
            cin.getline(str,);
            cout<<"Thisstinghasexistedfor"<<tree.AddStr(str)->reserved++<<"times."<<endl;
        break;
        case'2':
            cin.getline(str,);
            trie::nod<int,>*find;
            find=tree.FindStr(str);
            if(!find)
                cout<<"Nofound."<<endl;
            else
                cout<<"Thisstinghasexistedfor"<<find->reserved<<"times."<<endl;
        break;
        case'3':
            cin.getline(str,);
            cout<<"Theactionis"<<(tree.DeleteStr(str)?"Successful.":"Unsuccessful.")<<endl;
        break;
        case'4':
            tree.Traversal();
        break;
        case'5':
            return ;
        }
    }
    return ;
}
hihocoder trie樹
上一篇: 代碼評審該如何做
下一篇: [Trie]hihoCoder 1014 Trie樹

繼續閱讀