trietree的一个小练习

trietree又称为字典树。顾名思义，它是一种用来快速查找字符串的树形数据结构。

借用下网上的图哈~trietree结构如下：

实现方式大多为数组实现。我觉得这里需要注意的有这么几点：

1.当一个字符串很长时，必然导致该树的一个分支特别长。因此该数据结构不太适合用于字符串长度过长的情况。

2.因为是数组存储兄弟节点，因此必须根据字符的情况定义一个合适的数组大小（通常为128），以达到节省空间的目的。

3.可以用到的情况有：统计字符串出现个数，统计单词的前缀，字符串的排序等。

以下为其实现的一个小例子：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXNUM  130 
typedef struct tnode{
        int _count;                     
        struct tnode *next[MAXNUM];     //slibing nodes
}t_node;
int insert(const char* str,t_node *node){
        char *pos=str;
//      int i;
        t_node *nextnode,*curnode=node; 
        if(*pos==0) return 0;
        for(;*pos;pos++){               //util the end of the string
                if(curnode->next[*pos]==NULL){          //if not exits
                        curnode->next[*pos]=(t_node *)malloc(sizeof(t_node));
                        memset(curnode->next[*pos],0,sizeof(t_node));
                }
                nextnode=curnode->next[*pos];           //change the node
                curnode=nextnode;
        }       
        curnode->_count++;
        printf("str is :%s total:%d \n",str,curnode->_count);
        return 0;
}
void destory(t_node *node){
        int i;  
        for(i=0;i<MAXNUM;i++){
                if(node->next[i]){
                        destory(node->next[i]);
                        free(node->next[i]);    //recursion
                }
        }
}
int main(void){
        t_node root;
        char buffer[MAXNUM];
        memset(&root,0,sizeof(t_node));
        while(fgets(buffer,MAXNUM,stdin)!=NULL){
                buffer[strlen(buffer)-1]=0;
                printf("begin to handle %s\n",buffer);
                insert(buffer,&root);
        }
        destory(&root);
        return 0;
}