学步园

Trie字典树

哈希的一个变种
原理类似于字典的查找 如一个集合里面有

"ab", "abc", "abd", "ca", "cd", "ef", "ha", "hai","hag" "hk"
我要查找"hag"

   画图解题很肿要

  dictionary : { "ab", "abc", "abd", "ca", "cd", "ef", "ha", "hai","hag" "hk" }
   trie_tree:
                       root
                      / |\ \
                     a  c e h
                    /  /| | |\
                   b  a d f a k
                  /|       /|  
                 c d      i g

定义结构：

struct trie{
    struct trie *next[KIND];
    int chldnum;      //number of child
    char v;         // flag to judge whether it is complete
                    //also the number of same string
};

创建字典树：

void createTrie(const char *str)
{
    int id = 0, len = 0, i;
    struct trie *p, *q;
    len = strlen(str);
    p = root;

    for ( i = 0; i < len; i++ )
    {
        id = str[i] - 'a';  //hash
        if ( p->next[id] == NULL )
        {
        /*  first time  appear  */
            q = (struct trie*)malloc(sizeof(struct trie));  //create child
            memset(q, 0, sizeof(struct trie));
            q->chldnum = 1;
            p->next[id] = q;
            p = p->next[id];    //go to child
        }
        else
        {
            p->next[id]->chldnum++;
            p = p->next[id];  //go to child
        }
    }

    p->v++;
    return;
}

查找：

int findTrie(char *str)
{
    int id = 0, len = 0, i;
    struct trie* p;

    p = root;
    len = strlen(str);
    for ( i = 0; i < len; i++ )
    {
        id = str[i] - 'a';  //hash: id is hash address. str[i] is key.
        if ( id < 0 || id >= KIND ) // deal with invalid input
            return 0;
        p = p->next[id];
        if ( p == NULL )
            return 0;       //str is not in the dictionary
    }
    if ( p->v > 0 )
        return 1;  //dictionary has str
    else
        return 0;
}

释放树

写到这里，我想说任何递归都可以写成非递归的形式，

因为递归返回时，在栈里面保存了返回的地址；同理，如果我们定义一个带父结点的链表，就可以实现非递归了

int dealwithTrie(struct trie* T)
{
    int i;
    if ( T == NULL )
        return 0;
    for ( i = 0; i < KIND; i++ )
    {
        if ( T->next[i] != NULL )
            dealwithTrie(T->next[i]);
    }
    free(T);
    T = NULL;

    return 0;
}

完整代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define KIND    26
#define MAX     10
#define MAXSTR  32

struct trie{
    struct trie *next[KIND];
    int chldnum;      //number of child
    char v;         // flag to judge whether it is complete
                    //also the number of same string
};

struct trie *root;

void createTrie(const char *str)
{
    int id = 0, len = 0, i;
    struct trie *p, *q;
    len = strlen(str);
    p = root;

    for ( i = 0; i < len; i++ )
    {
        id = str[i] - 'a';  //hash
        if ( p->next[id] == NULL )
        {
        /*  first time  appear  */
            q = (struct trie*)malloc(sizeof(struct trie));  //create child
            memset(q, 0, sizeof(struct trie));
            q->chldnum = 1;
            p->next[id] = q;
            p = p->next[id];    //go to child
        }
        else
        {
            p->next[id]->chldnum++;
            p = p->next[id];  //go to child
        }
    }

    p->v++;
    return;
}

int findTrie(char *str)
{
    int id = 0, len = 0, i;
    struct trie* p;

    p = root;
    len = strlen(str);
    for ( i = 0; i < len; i++ )
    {
        id = str[i] - 'a';  //hash: id is hash address. str[i] is key.
        if ( id < 0 || id >= KIND ) // deal with invalid input
            return 0;
        p = p->next[id];
        if ( p == NULL )
            return 0;       //str is not in the dictionary
    }
    if ( p->v > 0 )
        return 1;  //dictionary has str
    else
        return 0;
}

int dealwithTrie(struct trie* T)
{
    int i;
    if ( T == NULL )
        return 0;
    for ( i = 0; i < KIND; i++ )
    {
        if ( T->next[i] != NULL )
            dealwithTrie(T->next[i]);
    }
    free(T);
    T = NULL;

    return 0;
}

/*  dictionary : { "ab", "abc", "abd", "ca", "cd", "ef", "ha", "hai","hag" "hk" }
*   trie_tree:
*                       root
*                      / |\ \
*                     a  c e h
*                    /  /| | |\
*                   b  a d f a k
*                  /|       /|  
*                 c d      i g
*/

int main()
{
    int i;
    char buffer[MAXSTR];
    char *dictionary[MAX] = {"ca",
                            "cd",
                            "abc",
                            "ab",
                            "abd",
                            "ef",
                            "ha",
                            "hai",
                            "hag",
                            "hk"
                            };

    root = (struct trie*)malloc(sizeof(struct trie));
    memset(root, 0, sizeof(struct trie));

    printf("#system start,init trie tree\n");
    for ( i = 0; i < MAX; i++ )
    {
        createTrie(dictionary[i]);
    }
    sleep(1);
    while ( buffer[0] != 'q' ) {
        memset(buffer, 0, MAXSTR);
        printf("#");
        scanf("%s", buffer);
        printf("************finding**********\n");
        sleep(2);
        if ( findTrie(buffer) )
            printf("#Result:%s is in the dictionary!\n", buffer);
        else
            printf("#Result:%s is not in the dictionary!\n", buffer);
    }
        
    dealwithTrie(root);

    return 0;
}