字典樹編寫筆記

試著寫了下字典樹，發覺這玩意別的不說，拿來作為遞歸練習真心有用，中間各種細節也是想了很久，代碼實現的很簡陋，而且還有很大的優化空間，以後再補充了

定義節點

頭文件

#ifndef TRIENODE_H
#define TRIENODE_H

#include <string>
#include <malloc.h>
#include <cstring>
using namespace std;

static const int MAX = 27;
static const char BASE = 'a';

struct TrieNode {
    TrieNode(const char *word);
 ~TrieNode();
    TrieNode *next[MAX];
    char *word;
    static int digit(char *word, int w);
};

#endif // TRIENODE_H

源文件

#include "trienode.h"

TrieNode::TrieNode(const char *word) {
    for (int i = 0; i < MAX; i++) {
        next[i] = NULL;
    }
 this->word = NULL;
 if (word != NULL) {
  int len = strlen(word);
  this->word = new char[len+1];
  strcpy(this->word, word);
 }
}

TrieNode::~TrieNode() {
 if (word != NULL) delete[] word;
}

int TrieNode::digit(char *word, int w) {
 // 注意：這裡默認使用0號位用於存儲字符\0，這是為了解決一個字符串
 //      是另外一個字符串的前綴的問題。
    return (word[w] == '\0') ? 0 : word[w]-BASE+1;
}

定義字典樹

頭文件

#ifndef TRIE_H
#define TRIE_H

#include "trienode.h"
#include <iostream>
#include <vector>

using namespace std;

class Trie
{
public:
    Trie();
 ~Trie();
 // 插入一個新的單詞
    void insert(char *word);
 // 打印字典樹
    void printTrie();
 // 查看是否包含某個單詞
 bool contains(char *word);
    // 查找某個單詞，返回這個單詞指針，好像沒什麼用
    const char* find(char *word);
 // 匹配單詞前綴，獲得所有匹配結果
    int match(char *word, vector<char *> &ret);
    // 刪除一個單詞，靜默吞噬錯誤異常
    void remove(char *word);
 // 清空字典樹
 void clear();
 // 檢查字典樹是否為空
 bool empty();
 // 獲取匹配前綴的前n個匹配項
 int match(char *word, int n, vector<char *> &ret);
 
private:
    static TrieNode* insertR(TrieNode *root, char *word, int w);
    static TrieNode* splitR(TrieNode *p, TrieNode *q, int w);
    static void printTrieR(TrieNode *root);
    static TrieNode* findR(TrieNode *root, char *word, int w);
 static int matchR(TrieNode *root, char *word, int w, vector<char *> &ret);
 static int getWords(TrieNode *root, vector<char *> &ret);
 static TrieNode* matchPrefixR(TrieNode *root, char *word, int w);
    static bool removeR(TrieNode *root, char *word, int w);
 static void clearR(TrieNode *root);
 static int getWords(TrieNode *root, int n, vector<char *> &ret);
    static int matchR(TrieNode *root, char *word, int w, int n, vector<char *> &ret);

private:
    TrieNode *root;
};

#endif // TRIE_H