试着写了下字典树，发觉这玩意别的不说，拿来作为递归练习真心有用，中间各种细节也是想了很久，代码实现的很简陋，而且还有很大的优化空间，以后再补充了

定义节点

头文件

#ifndef TRIENODE_H
#define TRIENODE_H

#include
#include
#include
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
#include

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 &ret);
// 删除一个单词，静默吞噬错误异常
void remove(char *word);
// 清空字典树
void clear();
// 检查字典树是否为空
bool empty();
// 获取匹配前缀的前n个匹配项
int match(char *word, int n, vector &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 &ret);
static int getWords(TrieNode *root, vector &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 &ret);
static int matchR(TrieNode *root, char *word, int w, int n, vector &ret);

private:
TrieNode *root;
};

#endif // TRIE_H