struct Node{ // trie树构建成一个二叉树，左儿子右兄弟，而非传统的父节点含26个子树的树，不过我觉得这也不像二叉树了，不信你把父节点连同他的右子树以及右子树的右子树放在一条直线上看一下
    char c;
    int key;
    Node *l, *r; // l 是 c 匹配成功后的下一个匹配开始，r 是 c 匹配失败后下一个匹配的字符
};

Node *root;  // trie tree

int search(char word[])
{
    int pos = 0;
    if (root == NULL){
        root = new Node;
        root->key = 0;
        root->l = root->r = NULL;
        root->c = word[pos];
    }
    Node * p = root, *father = root;
    Node ** pre = NULL;  // pre  指针的指针相当重要，他记录上一次是从父亲的哪个子树开始的,

    while (word[pos] != '\0'){
        if (p == NULL){ //printf("new Node:%c\n", word[pos]);
            p = new Node;
            p->key = 0;
            p->l = p->r = NULL;
            p->c = word[pos++];
            (*pre) = p; // printf("pre new:%x\n", *pre);
            father = p;
            pre = &(p->l); //错在的这里啊，当一个新的节点创建好后，就应该从下一个节点，即左子树开始检测，则记录相应位置的pre也要更改
                           // pre  指针的指针,相当重要，他记录上一次是从父亲的哪个子树开始的
            p = p->l;
        }
        else if (word[pos] == p->c){ // printf("Next l Node:%c\n", word[pos]);
            pre = &(p->l);  // pre标明是从哪个子树开始的
            father = p;
            p = p->l;
            ++pos;
        }
        else if (word[pos] != p->c){  // printf("Next r Node:%c  %c\n", word[pos], p->c);
            pre = &(p->r);   // pre标明是从哪个子树开始的
            father = p;
            p = p->r;
        }
        else{
           // return printf("Error\n");
           while (1) printf("Error\n");;
        }
    }
    
    if (father->key == 0){
        father->key = key++;
    }
    return father->key;
}