Trie 字典树

Trie树即字典树，一种用于快速检索的多叉树数据结构。

核心思想

空间换时间。利用字符串的公共前缀来降低查询时间开销从而提高效率

基本性质

1. 根节点不包含字符，其余节点都只包含一个字符
2. 从根节点到某一节点的路径上所有的字符连接起来即为对应字符串
3. 每个节点的所有子节点包含的字符都不相同

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

#define MAX_CHILD 26

typedef struct Node {
    int count;
    struct Node *child[MAX_CHILD];
} Node, *TrieNode;

Node* createNode() {
    Node *node = (Node*) malloc(sizeof(Node));
    memset(node,0,sizeof(Node));
    return node;
}

void insertNode(TrieNode root, char *str) {
    if(root == NULL || *str=='\0') {
        return ;
    }
    Node *t = root;
    char *p = str;
    while(*p!='\0') {
        if(t->child[*p-'a'] == NULL) {
            Node *tmp = createNode();
            t->child[*p-'a'] = tmp;
        }
        t = t->child[*p-'a'];
        p++;
    }
    t->count++;
}

void search(TrieNode root, char *str) {
    if(root == NULL || *str=='\0') {
        printf("trie is empty or str is null\n");
        return ;
    }
    Node *t = root;
    char *p = str;  
    while(*p!='\0') {
        if(t->child[*p-'a'] != NULL) {
            t = t->child[*p-'a'];
            p++;
        } else {
            break;
        }
    }
    if(*p=='\0' && t->count != 0) {
        printf("has result\n");
    } else {
        printf("no result\n");
    }
}

void deleteNode(TrieNode root) {
    for(int i = 0;i < MAX_CHILD; i++) {
        if(root->child[i] != NULL) {
            deleteNode(root->child[i]);
        }
    }
    free(root);
}

int main() {
    TrieNode root = NULL;
    root = createNode();
    char str[20];
    for(int i = 0;i < 3; i++) {
         printf("input %d\n", i);
         scanf("%s", str);
         insertNode(root, str);   
    }
    for(int i = 0;i < 3; i++) {
         printf("search %d\n", i);
         scanf("%s", str);
         search(root, str);;
    }
    return 0;
}