鍵樹的定義

鍵樹聽起來高端，其實(shí)也沒有想象中的那么膩害呛每，他其實(shí)就像字典一樣踩窖，有個根root，然后根下面有你存放的字母晨横，字母下面還有字母洋腮，就像查字典的過程，例如下圖手形，我查CAO啥供，先查C，然后查叁幢，最后查O，下面有個$標(biāo)識符坪稽，標(biāo)志這個單詞結(jié)束了曼玩。

鍵樹示例圖

鍵樹代碼的實(shí)現(xiàn)

鍵樹的主要構(gòu)成是next節(jié)點(diǎn)集合 和 標(biāo)識符鳞骤。每次查詢相當(dāng)于多叉樹，找到最后標(biāo)識符截止黍判。代碼是借鑒書本的豫尽，使用次數(shù)不多，不熟練顷帖，如有不當(dāng)之處美旧，希望指正。代碼也放在了github上

代碼主要分幾個部分贬墩，Trie樹的插入榴嗅，銷毀，查找陶舞。
其中插入部分的代碼：先獲取root根節(jié)點(diǎn)嗽测，開始逐個遍歷傳入的單詞每個字母，如果該字母在這個節(jié)點(diǎn)的next數(shù)組中已經(jīng)存在肿孵，則向下移動location = location->next[word-'a'];*唠粥，如果不存在，則傳建一個節(jié)點(diǎn)停做，添加到next數(shù)組中晤愧。
下面是查找部分：和插入部分類似，不停的遍歷蛉腌，遍歷出來以后檢查location是不是空官份，且是不是遍歷到了結(jié)尾。

//
//  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樹：節(jié)點(diǎn)中不設(shè)數(shù)據(jù)域
 每個節(jié)點(diǎn)有個標(biāo)志位表示是否是一個字符串（到字符串的末尾）
 每個節(jié)點(diǎn)保存其子女的節(jié)點(diǎn)指針
 */
struct Trie_node{
    bool isStr;                 // 記錄此處是否構(gòu)成一個串
    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){  // 不存在則新建立一個節(jié)點(diǎn)
                Trie_node *temp = new Trie_node();
                location->next[*word-'a'] = temp;
            }
            location = location->next[*word-'a'];   // 指針向下移動
            word++;
        }
        location->isStr = true;                     // 到達(dá)底部眉抬，標(biāo)記為一個串
    }
    
    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;
}