键树的定义

键树听起来高端，其实也没有想象中的那么腻害，他其实就像字典一样，有个根root，然后根下面有你存放的字母，字母下面还有字母，就像查字典的过程，例如下图，我查CAO，先查C，然后查，最后查O，下面有个$标识符，标志这个单词结束了。

键树示例图

键树代码的实现

键树的主要构成是next节点集合和标识符。每次查询相当于多叉树，找到最后标识符截止。代码是借鉴书本的，使用次数不多，不熟练，如有不当之处，希望指正。代码也放在了github上

代码主要分几个部分，Trie树的插入，销毁，查找。
其中插入部分的代码：先获取root根节点，开始逐个遍历传入的单词每个字母，如果该字母在这个节点的next数组中已经存在，则向下移动location = location->next[word-'a'];*，如果不存在，则传建一个节点，添加到next数组中。
下面是查找部分：和插入部分类似，不停的遍历，遍历出来以后检查location是不是空，且是不是遍历到了结尾。

//
//  main.cpp
//  Page276_Trie树
//
//  Created by 李林 on 2017/2/8.
//  Copyright © 2017年 lee. All rights reserved.
//

#include <iostream>
using namespace std;

const int branchNum = 26;
/*
 Trie树：节点中不设数据域
 每个节点有个标志位表示是否是一个字符串（到字符串的末尾）
 每个节点保存其子女的节点指针
 */
struct Trie_node{
    bool isStr;                 // 记录此处是否构成一个串
    Trie_node *next[branchNum]; // 指向各个子树的指针
    Trie_node() : isStr(false) {
        memset(next, NULL, sizeof(next));
    }
};

class Trie{
public:
    Trie(){
        root = new Trie_node();
    }
    
    void insert(const char* word){
        Trie_node *location = root;
        while(*word){
            if(location->next[*word-'a'] == NULL){  // 不存在则新建立一个节点
                Trie_node *temp = new Trie_node();
                location->next[*word-'a'] = temp;
            }
            location = location->next[*word-'a'];   // 指针向下移动
            word++;
        }
        location->isStr = true;                     // 到达底部，标记为一个串
    }
    
    bool search(char* word){
        Trie_node *location = root;
        while(*word && location){
            location = location->next[*word-'a'];
            word++;
        }
        return (location != NULL && location->isStr);
    }
    
    void deleteTrie(Trie_node *root){
        for(int i=0; i<branchNum; i++){
            if(root->next[i] != NULL)
                deleteTrie(root->next[i]);
        }
        delete root;
    }
    
    Trie_node* getTrie(){
        return root;
    }
    
private:
    Trie_node *root;
};

int main(int argc, const char * argv[]) {
    
    Trie tree;
    tree.insert("hello");
    tree.insert("world");
    bool result = tree.search("world");
    printf("%d", result); 
    
    return 0;
}