字典树（tire）

一、什么是树？

这样的？，是它也是树，只不过是现实生活中的树罢了，只要学过编程的都知道在，计算机的世界里也有树，树在计算机里是这样的

与其说像一颗树不是说像树根，因为看得出来它是从上往下延申的，树在计算机中的用途也很广泛，什么排序啊，查找啊，索引，…… 当然查找搜索还是用得最多的。
看看树的官方定义：
树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。

二、实现一颗简单的树

• 实现一颗树还不简单，首先剖析树的结构，无非就是一个树节点，他打下面又有很多和它相连的子树，说得这么绕，看一看图就明白了：

每种颜色都可以单独拿出来做一棵树对吧，就算是只有一个节点它也能成为一颗树，这不就是突破口吗。树里又有多个树，那么就可以定义一个结构：

typedef struct TreeNode{
	struct TreeNode* children[INFINITE]; 
}*Tree;

一颗简单的树就来了，当然这里的无限大是闹着玩的，最重要的还是理解概念。在内存当中这棵树有是怎么个样子呢，请看下图：

这些小方格也就代表这计算机中的内存空间，可以看到是一个内存空间就存放了一棵树，可以这样说吧。
树的种类有很多，上面这就是最为普通的树了，甚至他连一个存放数据的空间都没有，还有一种树是最为常见的，那就是二叉树，二叉树继承了树的特性，但自己又有一些更为特殊的性值。二叉树，听名字，就带有一个二，这个二的含义是什么呢，也就是一个二叉树节点下至多允许有两个节点，他的结构是这样的：

看到它的这种结构，马上就可以知道它定义起来比树还要简单，它的孩子树量已经被限制，至多也才两个，无非就似乎左边一个孩子，右边一个孩子。那么就可以定义出它的结构了：

typedef struct BinaryTreeNode{
	DataType data;
	struct BinaryTreeNode* leftChild;
	struct BinaryTreeNode* rightChild;
}*BinaryTree;

在代码中可以看到，我们除了定义了两个孩子节点外，还多定义了一个用于存放数据的空间，我们既然使用树结构那必然是要拿来满足自己的需求的吧，不可能就拿来看吧；
代码看了我们又来看看他在计算机内存当中的存储方式吧：

这样应该就很清楚了，#代表的就是NULL也就是没有指向，计算机世界无非就只有两种状态，0或者1，这部就撞到了二叉树的怀里了吗，二叉树的用途即为广泛，排序，编码，决策，等等等等无不和二叉树相关，有时间我会再出一期二叉树的相关博文。

今天的主角 Tire——字典树

有了前面的一些树的铺垫，想必现在再来理解字典树的概念应该会容易许多，字典树是个什么东西呢，其实它的结构就是一个普通的树型结构，当然肯定会有些许不一样，它能拿来干什么呢？不妨我们来看一个需求如何

需求内容：现在你有一个装有单词的列表，我手里有一个单词，你能快速找出这个单词是否存在于你的列表当中吗

可能很多下伙伴都，马上会想到这种思路吧，你的代码或许是这样的：

bool wordIsExisted(vector<string> wordList,string targetWord){
	for(int i=0;i<wordList.size();i++){
		if(wordList.at(i) == targetWord){
			return true	
		}
	} 
return false;
}

这里为了简便是直接使用 == 号来进行判断的，其程序内部其实还是是将两个字符串对应位置上的字符逐一进行比较的，所以这里可以很容易的算到上面的这个程序的时间复杂度在O(n2)；
如果单词列表中的单词比较短，单词数量比较少使用上面这种方法当然可行，但是如果单词的数量，和长度都大得恐怖呢，我们以每次比较一个字符的时间需要1s来算（当然这里只是度量一下，肯定不会这么慢的），我的单词列表的数量有10000个，每个单词的长度都是10000，而且我们要查找的单词还在列表中的最后一个，那么这里需要花销的时间就是10000×10000×1s
也就是1亿秒（3年左右才能跑完）这无疑是致命的。
那么聪明的前辈们，便研究出来了一种结构，就是标题所提到的字典树
来先上图：

就是这种结构，其中每个红色的节点表示代表此处到root根节点之间存在一个单词，不难看我们每次我们要找单词是否存在，都是从root节点开始寻找。

就比如说我要寻找 he 这个单词，那么我先将指针指向root节点处，探寻其的孩子中是否存在有 h 这个字符，如果有那我就把指针指向h节点处，然后下面再从 h 节点下探寻其孩子单中又是否存在e节点，这时发现有，我们又把指针指向e节点，这时发现我们要寻找的单词已经扫到末尾，然后最后判断此节点是否为红色也就是（是否为单词，最后输出结果为true；
可能话说得不是那么明白，还是看下面图理解比较快：

这样就明白了工作原理，下面来看一下代码实现过程：

#include<iostream>

using namespace std;


typedef struct TireNode{
    char c;
    bool isWord;
    TireNode* child[26];
}*Tire;

void insertWord(Tire t,string word){
    if(t==nullptr){return;}
    for(char w: word){              
        if(t->child[w-'a']){        // 判断是否存在此字母
            t = t->child[w-'a'];    // 跳至下一个节点
        }
        else{
            Tire node = (Tire) malloc(sizeof(TireNode));
            *node = {w,false,{nullptr}};        // 写c千万别忘了初始化血的教训
            t = t -> child[w - 'a'] = node;
        }
    }
    t->isWord = true;
}

bool findWord(Tire t,string word){
    for(char w:word){
        if(t->child[w-'a']){        // 判断当前字母是否存在
            t = t->child[w-'a'];
        }
        else{
            return false;
        }
    }
    return t->isWord;
}


int main(){
    Tire t =  (Tire) malloc(sizeof(TireNode));
    *t = {'\r',false,{nullptr}};
    insertWord(t, "he");
    insertWord(t,"she");
    insertWord(t,"her");
    cout << boolalpha;
    cout << findWord(t,"his") << endl;
    cout << findWord(t,"he") << endl;
    cout << findWord(t,"her") << endl;
}