用C语言实现字典树

前言

前段时间，面试百度人工智能部门的测试开发岗的时候，面试官给了我一道算法题：有一堆数据，都是由英文字母构成的，设计一个算法去存储这些数据。我一想，那不就是考字典树嘛，简单啦，我参加ACM校赛的时候看过大神队友实现过。大概的思想都能理解，但是由于自己没有亲自实现过，所以当面试官问我具体要怎么实现的时候，我就特别着急，明明思路很清晰，但是细节却连接不起来，于是就打算面试后自己实现一遍！

简介

在谈实现之前，我想先谈谈字典树整体的思想和存在的价值。

字典树，顾名思义，就是用树的结构去存储单词。比如，我要存储单词ant和apple，就可以采取下图的多叉树结构去实现，其中可以看到，他们公用A节点，看是上去似乎节省了空间（实际上并没有，下面会解释），和形成了<strong>有序</strong>的分组。

字典树图解

假如不使用这种结构存储，那么采取朴素的方法，也就是用一个数组，把单词存进去，然后还需要满足数组内的单词不重复，我们可以比较一下这两种方法的时间复杂度。
<strong>假设每个单词平均有M个字母，共有N个单词</strong>

操作	朴素算法	字典树
插入	O(N)	O(M)
查找	O(N)	O(M)
删除	O(N)	O(M)

显然当需要存储的数据量越庞大或者数据的操作越频繁，字典树的优势越明显，它的时间复杂度只与单词的长度有关！这个算法可以应用在词频分析，信息检索，字符串匹配等方面。

实现

1. 定义结构体

typedef struct node {
    struct node* children[SUB_NODE_COUNT];
    int flag;
    char character;
} Node;

定义树节点的数据包含三部分

所含字母
子节点指针
是否能终结

从这个定义的结构体可以看出，其实字典树并没有节省存储空间。<code>sizeof(Node)</code>的结果是216bytes，当然因为data packing对齐的关系，有一些多余padding，但是就算设置<code>#pragma pack (1)</code>，消除padding，那<code>sizeof(Node)</code>也有213bytes，相比之下，一个char只需要1byte，所以并没有节省空间。
<code>int flag</code>这个变量是为了区分该节点与其祖先节点能否成为一个单词。比如ant和an分别都能成为独立的单词，所以n和t节点的<code>flag</code>都应该设置<code>TRUE</code>，但是orange和ora就不一样，因为ora不能成为一个单词，所以这里的a节点的<code>flag</code>应该设置<code>FALSE</code>

2. 插入函数

Node* create_node(char c, int flag) {
    Node* n = malloc(sizeof(Node));
    n->character = c;
    n->flag = flag;
    for (int i = 0; i < SUB_NODE_COUNT; i++) {
        n->children[i] = NULL;
    }
    return n;
}

int append_node(Node* n, char c) {

    Node* child_ptr =  n->children[c-'a'];
    if (child_ptr) {
        return FALSE;
    }
    else {
        n->children[c-'a'] = create_node(c, FALSE);
        return TRUE;
    }
}

int add_word(Node* root, char* str) {
    char c = *str;
    Node* ptr = root;
    int flag = TRUE;
    while(c != '\0') {
        if (!append_node(ptr, c)) {
             flag = FALSE;
        }
        ptr = ptr->children[c-'a'];
        c = *(++str);
    }
    if (!ptr->flag) {
        flag = FALSE;
        ptr->flag = TRUE;
    }
    return !flag;
}

这个函数的功能，将单词插入树中，假如目标单词已经存在于树中，则返回<code>FALSE</code> , 否则就能成功插入，返回<code>TRUE</code>。插入的过程比较简单，只要单词字母对应的节点存在，则继续往下查询，否则就创建新节点，然后在最后的一个字母的节点把<code>flag</code>改为<code>FALSE</code>;

3. 查找函数

int check(Node* root, char* word) {
    Node* ptr = root;
    int len = strlen(word);
    for (int i = 0; i < len; i++) {
        if (!ptr) {
            printf("\"%s\" isn't in the Dictionary!\n", word);
            return FALSE;
        }
        ptr = ptr->children[word[i]-'a'];
    }
    if (ptr && ptr->flag) {
        printf("\"%s\" is in the Dictionary!\n", word);
        return TRUE;
    } else {
        printf("\"%s\" isn't in the Dictionary!\n", word);
        return FALSE;
    }

}

这个函数也比较简单，就不多解释了。

4. 遍历函数

void traversal(Node* root, char* str) {

    if (!root) {
        return;
    }

    int len_of_str = strlen(str);
    char* new_str = malloc(len_of_str+1);
    strcpy(new_str, str);
    new_str[len_of_str] = root->character;

    if (root->flag) {
        //输出
        char* str_for_print = malloc(len_of_str+2);
        strcpy(str_for_print, new_str);
        str_for_print[len_of_str+1] = '\0';
        printf("%s\n", str_for_print);
        free(str_for_print);
    }

    for (int i = 0; i < SUB_NODE_COUNT; i++) {
        traversal(root->children[i], new_str);
    }
    free(new_str);
}

很显然，这里用深度优先遍历比较合适，因为这是根据单词字母的组成来垂直扩展多叉树的。对于深度优先算法，递归是最能偷懒的方法啦！深度遍历的过程中，只要遇到<code>flag</code>等于<code>TRUE</code>，跟祖先节点构成单词输出，那就OK啦。

5. 删除函数

int isLeave(Node* root) {
    for (int i = 0; i < SUB_NODE_COUNT; i++) {
        if (root->children[i]) {
            return FALSE;
        }
    }
    return TRUE;
}

int delete_word(Node* root, char* word) {
    int len = strlen(word);
    int first_index = word[0] - 'a';
    if (!root->children[first_index]) {
        return FALSE;
    }
    if (len == 1) {
        if (root->children[first_index]->flag) {
            if (isLeave(root->children[first_index])) {
                free(root->children[first_index]);
                root->children[first_index] = NULL;
            } else {
                root->children[first_index]->flag = FALSE;
            }
            return TRUE;
        } else {
            return FALSE;
        }
    }
    int flag = delete_word(root->children[first_index], word+1);
    if (isLeave(root->children[first_index]) && !root->children[first_index]->flag) {
        free(root->children[first_index]);
        root->children[first_index] = NULL;
    }
    return flag;
}

删除函数相对难一点。我看网上很多人实现字典树的时候都没有实现这个函数。
其实删除一个单词最直接的方法就是把最后一个字母的<code>flag</code>改为<code>FALSE</code>就可以了。但是只是这样做的话，随着越来越频繁的操作，会产生很多多余的节点，性能不能达到最佳，所以这个函数需要完成两件事。

判断删除的单词是否存在，假如不存在则返回<code>FALSE</code>。
删除多余的节点。

节点必须同时满足以下两点才能定义为多余的节点。

没有子节点（叶子节点）
<code>flag</code>等于<code>FALSE</code>

6. 完整的实现

我只是简单地写了几个用例来测试，如若发现bug，欢迎来喷！
/*
============================================================================
Name : Dictionary.c
Author : Matthew1994
Version :
Copyright : Your copyright notice
Description : Dictionary Tree in C, Ansi-style
============================================================================
*/

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

#define TRUE 1
#define FALSE 0

#define SUB_NODE_COUNT 26

typedef struct node {
    struct node* children[SUB_NODE_COUNT];
    int flag;
    char character;
} Node;

Node* create_node(char c, int flag) {
    Node* n = malloc(sizeof(Node));
    n->character = c;
    n->flag = flag;
    for (int i = 0; i < SUB_NODE_COUNT; i++) {
        n->children[i] = NULL;
    }
    return n;
}

int append_node(Node* n, char c) {

    Node* child_ptr =  n->children[c-'a'];
    if (child_ptr) {
        return FALSE;
    }
    else {
        n->children[c-'a'] = create_node(c, FALSE);
        return TRUE;
    }
}

int add_word(Node* root, char* str) {
    char c = *str;
    Node* ptr = root;
    int flag = TRUE;
    while(c != '\0') {
        if (!append_node(ptr, c)) {
             flag = FALSE;
        }
        ptr = ptr->children[c-'a'];
        c = *(++str);
    }
    if (!ptr->flag) {
        flag = FALSE;
        ptr->flag = TRUE;
    }
    return !flag;
}

void traversal(Node* root, char* str) {

    if (!root) {
        return;
    }

    int len_of_str = strlen(str);
    char* new_str = malloc(len_of_str+1);
    strcpy(new_str, str);
    new_str[len_of_str] = root->character;

    if (root->flag) {
        //输出
        char* str_for_print = malloc(len_of_str+2);
        strcpy(str_for_print, new_str);
        str_for_print[len_of_str+1] = '\0';
        printf("%s\n", str_for_print);
        free(str_for_print);
    }

    for (int i = 0; i < SUB_NODE_COUNT; i++) {
        traversal(root->children[i], new_str);
    }
    free(new_str);
}

int check(Node* root, char* word) {
    Node* ptr = root;
    int len = strlen(word);
    for (int i = 0; i < len; i++) {
        if (!ptr) {
            printf("\"%s\" isn't in the Dictionary!\n", word);
            return FALSE;
        }
        ptr = ptr->children[word[i]-'a'];
    }
    if (ptr && ptr->flag) {
        printf("\"%s\" is in the Dictionary!\n", word);
        return TRUE;
    } else {
        printf("\"%s\" isn't in the Dictionary!\n", word);
        return FALSE;
    }

}

int isLeave(Node* root) {
    for (int i = 0; i < SUB_NODE_COUNT; i++) {
        if (root->children[i]) {
            return FALSE;
        }
    }
    return TRUE;
}

int delete_word(Node* root, char* word) {
    int len = strlen(word);
    int first_index = word[0] - 'a';
    if (!root->children[first_index]) {
        return FALSE;
    }
    if (len == 1) {
        if (root->children[first_index]->flag) {
            if (isLeave(root->children[first_index])) {
                free(root->children[first_index]);
                root->children[first_index] = NULL;
            } else {
                root->children[first_index]->flag = FALSE;
            }
            return TRUE;
        } else {
            return FALSE;
        }
    }
    int flag = delete_word(root->children[first_index], word+1);
    if (isLeave(root->children[first_index]) && !root->children[first_index]->flag) {
        free(root->children[first_index]);
        root->children[first_index] = NULL;
    }
    return flag;
}

int main(void) {
    Node *root = create_node('$', FALSE);

    //测试add_ word函数
    add_word(root, "abc");
    add_word(root, "abcd");
    add_word(root, "world");
    add_word(root, "nnaiodnf"); 
    traversal(root, "");

    //测试check函数 
    check(root, "abc");
    check(root, "abcd");

    //测试delete_word函数
    delete_word(root, "abe");
    check(root, "abe");

    return EXIT_SUCCESS;
}

最后编辑于：2017.12.05 01:13:11

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,445评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,889评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,047评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,760评论 1赞 276
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,745评论 5赞 367
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,638评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,011评论 3赞 398
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,669评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,923评论 1赞 299
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,655评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,740评论 1赞 330
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,406评论 4赞 320
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,995评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,961评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,197评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,023评论 2赞 350
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,483评论 2赞 342