左孩子右兄弟的字典树

一般写的字典树都是双数组的形式，但是当字符的数量很多时，就会占用大量的内存，初始化操作也会变慢。这时，就可以用左孩子右兄弟的写法，来以时间换空间。

下面是自己写的一个：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxnode=100000;

struct Trie
{
    char ch[maxnode];
    int left[maxnode],right[maxnode],cnt;
    bool flag[maxnode];

    Trie(){}
    void init()
    {
        cnt=1;
        left[0]=right[0]=ch[0]=0;
        flag[0]=false;
        //memset(flag,false,sizeof(flag));
    }

    void insert(const char* str)
    {
        int len=strlen(str),u=0,j;
        for(int i=0;i<len;i++)
        {
            for(j=left[u];j;j=right[j])
            {
                if(ch[j]==str[i]) break;
            }
            if(j==0)///a new node
            {
                j=cnt++;
                left[j]=0;ch[j]=str[i];
                flag[j]=false;
                right[j]=left[u];
                left[u]=j;
            }
            u=j;
        }
        flag[j]=true;
    }

    bool query(const char* str)
    {
        int len=strlen(str),u=0,j;
        for(int i=0;i<len;i++)
        {
            for(j=left[u];j;j=right[j])
            {
                if(ch[j]==str[i]) break;
            }
            if(j==0) return false;
            u=j;
        }
        return flag[j];
    }

}tree;

int main()
{
    char dic[200];
    int d;
    tree.init();
    while(cin>>d>>dic)
    {
        if(d==1)
        {
            tree.insert(dic);
        }
        else if(d==2)
        {
            cout<<tree.query(dic)<<endl;
        }
    }
    return 0;
}