Trie树是保存字符串公共前缀信息的数据结构,可用于字符串多模匹配，普通的非压缩Trie树实现如下
第一种实现:每个分支节点使用map标准库容器保存前缀索引
#include <map>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <random>
using namespace std;
enum Compare_Result {EQUAL, LEFT_IS_PREFIX, RIGHT_IS_PREFIX, NOT_EQUAL};
struct TrieTreeNode //Trie树节点类型
{
enum NodeType { DATANODE, BRANCHNODE } type_flag; //节点类型标志，分支节点或存放关键字的叶节点
union
{
string key_in_trie; //叶节点关键字
map<char, TrieTreeNode*> sub_ptr; //分支节点的分支字符和对应的指向分支字符对应的子节点的指针之间的映射关系
};
TrieTreeNode(const string& k) :type_flag(NodeType::DATANODE), key_in_trie(k) {}
TrieTreeNode() :type_flag(NodeType::BRANCHNODE), sub_ptr() {}
TrieTreeNode(TrieTreeNode& be_copied)
{
switch (be_copied.type_flag)
{
case NodeType::DATANODE: new (&key_in_trie) string(be_copied.key_in_trie); break;
case NodeType::BRANCHNODE:
{
new (&sub_ptr) map<char, TrieTreeNode*>();
for (map<char, TrieTreeNode*>::iterator p = be_copied.sub_ptr.begin(); p != be_copied.sub_ptr.end(); ++p)
sub_ptr.insert(make_pair(p->first, nullptr));
}
break;
}
type_flag = be_copied.type_flag;
}
~TrieTreeNode()
{
switch (type_flag)
{
case NodeType::DATANODE: key_in_trie.~string(); break;
case NodeType::BRANCHNODE: sub_ptr.~map<char, TrieTreeNode*>(); break;
}
}
};
class TrieTree
{
public:
bool insert(const string& be_inserted) const; //Trie树中插入关键字,true成功false失败
bool deleteElem(const string& be_deleted) const; //Trie树中删除指定关键字,true成功false失败
TrieTreeNode* copy(); //拷贝Trie树，返回指向副本Trie树的指针
TrieTree() { root = new TrieTreeNode(); }
void printTrieTree(TrieTreeNode* cur, size_t offset) const;
bool isEmpty() const { return root->sub_ptr.empty(); }
TrieTreeNode* getTrieTree() const { return root; }
TrieTree(TrieTree& be_copied) { root = be_copied.copy(); }
~TrieTree();
private:
Compare_Result static strCompare(const string& left, const string& right, string::size_type& i);
TrieTreeNode* root; //Trie树根节点
};
ostream& operator<<(ostream& o, const TrieTree& be_output)
{
if (be_output.isEmpty())
{
o << "NULL" << endl;
return o;
}
be_output.printTrieTree(be_output.getTrieTree(), 0);
return o;
}
Compare_Result TrieTree::strCompare(const string& left, const string& right, string::size_type& i)
{
for (; ; ++i)
{
if (i == left.size() && i == right.size())
return Compare_Result::EQUAL;
else if (i == left.size() || i == right.size())
{
if (i == left.size())
return Compare_Result::LEFT_IS_PREFIX;
else
return Compare_Result::RIGHT_IS_PREFIX;
}
else if (left[i] != right[i])
return Compare_Result::NOT_EQUAL;
}
}
bool TrieTree::deleteElem(const string& be_deleted) const
{
TrieTreeNode* run = root;
vector<TrieTreeNode*> stack;
vector<TrieTreeNode*>::size_type index;
map<char, TrieTreeNode*>::iterator stop_branch_node;
map<char, TrieTreeNode*>::iterator leaf_father_point_to_leaf;
{
string::size_type i = 0;
while (true)
{
if (i < be_deleted.size())
{
map<char, TrieTreeNode*>::iterator it;
it = run->sub_ptr.find(be_deleted[i]);
if (it == run->sub_ptr.end())
return false;
++i;
if (run == root || run->sub_ptr.size() >= 2)
{
if (it->second->type_flag == TrieTreeNode::NodeType::BRANCHNODE)
{
index = stack.size();
stop_branch_node = it;
}
else
{
leaf_father_point_to_leaf = it;
break;
}
}
else
stack.push_back(run);
run = it->second;
}
else
{
if (run->sub_ptr.empty() || '\0' != run->sub_ptr.begin()->first)
return false;
leaf_father_point_to_leaf = run->sub_ptr.begin();
break;
}
}
if (leaf_father_point_to_leaf->first != '\0' && strCompare(be_deleted, leaf_father_point_to_leaf->second->key_in_trie, i) != Compare_Result::EQUAL)
return false;
}
delete leaf_father_point_to_leaf->second;
run->sub_ptr.erase(leaf_father_point_to_leaf);
if (run != root && run->sub_ptr.size() == 1 && run->sub_ptr.begin()->second->type_flag == TrieTreeNode::NodeType::DATANODE)
{
if (stop_branch_node->second != run)
{
for (size_t j = stack.size() - 1; j > index; --j)
delete stack[j];
delete stack[index];
}
stop_branch_node->second = run->sub_ptr.begin()->second;
delete run;
}
return true;
}
bool TrieTree::insert(const string& be_inserted) const
{
TrieTreeNode* run = root;
string::size_type i = 0;
pair<map<char, TrieTreeNode*>::iterator, bool> result;
while (run->type_flag != TrieTreeNode::NodeType::DATANODE)
{
if (i < be_inserted.size())
{
result = run->sub_ptr.insert(make_pair(be_inserted[i], new TrieTreeNode(be_inserted)));
if (result.second)
return true;
run = result.first->second;
++i;
}
else
{
if (run->sub_ptr.empty() || run->sub_ptr.begin()->first != '\0')
{
run->sub_ptr.insert(make_pair('\0', new TrieTreeNode(be_inserted)));
return true;
}
return false;
}
}
Compare_Result compare_result;
{
string::size_type start_index = i;
compare_result = strCompare(be_inserted, run->key_in_trie, i);
if (compare_result == Compare_Result::EQUAL)
return false;
result.first->second = new TrieTreeNode();
for (; start_index < i; ++start_index)
result.first = result.first->second->sub_ptr.insert(make_pair(be_inserted[start_index], new TrieTreeNode())).first;
}
if (compare_result == Compare_Result::LEFT_IS_PREFIX)
{
result.first->second->sub_ptr.insert(make_pair('\0', new TrieTreeNode(be_inserted)));
result.first->second->sub_ptr.insert(make_pair(run->key_in_trie[i], run));
}
else if (compare_result == Compare_Result::RIGHT_IS_PREFIX)
{
result.first->second->sub_ptr.insert(make_pair('\0', run));
result.first->second->sub_ptr.insert(make_pair(be_inserted[i], new TrieTreeNode(be_inserted)));
}
else
{
result.first->second->sub_ptr.insert(make_pair(run->key_in_trie[i], run));
result.first->second->sub_ptr.insert(make_pair(be_inserted[i], new TrieTreeNode(be_inserted)));
}
return true;
}
TrieTree::~TrieTree()
{
TrieTreeNode* run = root;
stack<pair<TrieTreeNode*, map<char, TrieTreeNode*>::iterator>> work_stack;
bool trace_back_flag = true;
while (true)
{
if (trace_back_flag == true)
{
if (run == root)
{
if (run->sub_ptr.begin() == run->sub_ptr.end())
{
delete root;
return;
}
}
else
{
if (run->type_flag == TrieTreeNode::DATANODE)
{
delete run;
run = work_stack.top().first;
++work_stack.top().second;
//work_stack.top().second = run->sub_ptr.erase(work_stack.top().second);
trace_back_flag = false;
continue;
}
}
work_stack.push(make_pair(run, run->sub_ptr.begin()));
run = run->sub_ptr.begin()->second;
}
else
{
if (run == root || work_stack.top().second != run->sub_ptr.end())
{
if (run == root)
{
if (work_stack.top().second == root->sub_ptr.end())
{
delete root;
return;
}
}
run = work_stack.top().second->second;
trace_back_flag = true;
}
else
{
delete run;
work_stack.pop();
run = work_stack.top().first;
++work_stack.top().second;
// work_stack.top().second = run->sub_ptr.erase(work_stack.top().second);
}
}
}
}
TrieTreeNode* TrieTree::copy()
{
TrieTreeNode* be_copied = root;
stack<pair<TrieTreeNode*, map<char, TrieTreeNode*>::iterator>> work_stack;
stack<pair<TrieTreeNode*, map<char, TrieTreeNode*>::iterator>> copy_trace_stack;
TrieTreeNode* root_of_copy = nullptr;
bool trace_back_flag = true;
while (true)
{
if (trace_back_flag == true)
{
if (be_copied == root)
{
root_of_copy = new TrieTreeNode(*be_copied);
if (be_copied->sub_ptr.begin() == be_copied->sub_ptr.end())
break;
copy_trace_stack.push(make_pair(root_of_copy, root_of_copy->sub_ptr.begin()));
}
else
{
if (work_stack.top().second != work_stack.top().first->sub_ptr.begin())
++copy_trace_stack.top().second;
copy_trace_stack.top().second->second = new TrieTreeNode(*be_copied);
if (be_copied->type_flag != TrieTreeNode::DATANODE)
copy_trace_stack.push(make_pair(copy_trace_stack.top().second->second, copy_trace_stack.top().second->second->sub_ptr.begin()));
else
{
be_copied = work_stack.top().first;
trace_back_flag = false;
continue;
}
}
work_stack.push(make_pair(be_copied, be_copied->sub_ptr.begin()));
be_copied = be_copied->sub_ptr.begin()->second;
}
else
{
if (work_stack.top().second->second->type_flag != TrieTreeNode::DATANODE)
copy_trace_stack.pop();
if (be_copied == root || ++(work_stack.top().second) != be_copied->sub_ptr.end())
{
if (be_copied == root)
{
if (++(work_stack.top().second) == root->sub_ptr.end())
break;
}
be_copied = work_stack.top().second->second;
trace_back_flag = true;
}
else
{
work_stack.pop();
be_copied = work_stack.top().first;
}
}
}
return root_of_copy;
}
void TrieTree::printTrieTree(TrieTreeNode* cur, size_t offset) const
{
if (cur->type_flag == TrieTreeNode::BRANCHNODE)
{
size_t max_length;
if (cur->sub_ptr.begin()->first == '\0')
max_length = 4;
else
max_length = 1;
for (map<char, TrieTreeNode*>::iterator run = cur->sub_ptr.begin(); run != cur->sub_ptr.end(); ++run)
{
for (size_t go = 1; go <= offset; ++go)
cout << " ";
if (run->first == '\0')
cout << "NULL";
else
{
cout << run->first;
for (size_t go = 2; go <= max_length; ++go)
cout << " ";
}
cout <<"|-" << endl;
printTrieTree(run->second, offset + 2 + max_length);
}
}
else
{
for (size_t go = 1; go <= offset; ++go)
cout << " ";
cout << "leaf:" << cur->key_in_trie << endl;
}
}
int main()
{
vector<string> test = { "bluebird", "bunting", "bobwhite", "bluejay" };
TrieTree test_obj;
for (vector<string>::iterator p = test.begin(); p != test.end(); ++p)
{
cout << "插入字符串" << *p << endl;
if (test_obj.insert(*p))
{
cout << "插入成功" << endl;
cout << "当前Trie为:" << endl << test_obj << endl;
TrieTree copy(test_obj);
cout << "当前Trie的副本为:" << endl << copy << endl;
}
else
{
cout << "插入失败" << endl;
exit(0);
}
}
cout << endl;
// TrieTreeNode *copy = test_ptr.copy();
//for (vector<string>::iterator p = test.begin(); p != test.end(); ++p)
{
cout << "删除字符串" << "bobwhite" << endl;
if (test_obj.deleteElem("bobwhite"))
{
cout << "删除成功" << endl;
cout << "当前Trie为:" << endl << test_obj << endl;
TrieTree copy(test_obj);
cout << "当前Trie的副本为:" << endl << copy << endl;
}
else
{
cout << "删除失败" << endl;
exit(0);
}
cout << "删除字符串" << "bluejay" << endl;
if (test_obj.deleteElem("bluejay"))
{
cout << "删除成功" << endl;
cout << "当前Trie为:" << endl << test_obj << endl;
TrieTree copy(test_obj);
cout << "当前Trie的副本为:" << endl << copy << endl;
}
else
{
cout << "删除失败" << endl;
exit(0);
}
}
cout << endl;
string mod = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
const int L = 9; // 随机字符串最大长度
const int r = 2; //相同长度重复次数
vector<int> LList(L);
vector<string> random_str;
for (int run = 0; run < LList.size(); ++run)
LList[run] = run + 1;
shuffle(LList.begin(), LList.end(), default_random_engine());
for (int re = 1; re <= r; ++re)
{
for (int run = 0; run < LList.size(); ++run)
{
string r;
for (int go = 1; go <= LList[run]; ++go)
{
r.append(1, mod[rand() % mod.size()]);
}
random_str.push_back(r);
}
}
for (vector<string>::iterator p = random_str.begin(); p != random_str.end(); ++p)
{
cout << "插入字符串" << *p << endl;
if (test_obj.insert(*p))
{
cout << "插入成功" << endl;
cout << "当前Trie为:" << endl << test_obj << endl;
TrieTree copy(test_obj);
cout << "当前Trie的副本为:" << endl << copy << endl;
}
else
{
cout << "插入失败" << endl;
exit(0);
}
}
cout << endl;
// TrieTreeNode *copy = test_ptr.copy();
for (vector<string>::iterator p = random_str.begin(); p != random_str.end(); ++p)
{
cout << "删除字符串" << *p << endl;
if (test_obj.deleteElem(*p))
{
cout << "删除成功" << endl;
cout << "当前Trie为:" << endl << test_obj << endl;
TrieTree copy(test_obj);
cout << "当前Trie的副本为:" << endl << copy << endl;
}
else
{
cout << "删除失败" << endl;
exit(0);
}
}
cout << endl;
random_str.clear();
for (int i = 1; i <= 7; ++i)
{
string temp(mod, 0, i);
for (int run = 1; run <= 7; ++run)
{
string r;
for (int go = 1; go <= run; ++go)
{
r.append(1, mod[rand() % mod.size()]);
}
random_str.push_back(temp + r);
}
}
cout << "测试字符串有共同前缀不相等情形" << endl;
for (vector<string>::iterator p = random_str.begin(); p != random_str.end(); ++p)
{
cout << "插入字符串" << *p << endl;
if (test_obj.insert(*p))
{
cout << "插入成功" << endl;
cout << "当前Trie为:" << endl << test_obj << endl;
TrieTree copy(test_obj);
cout << "当前Trie的副本为:" << endl << copy << endl;
}
else
{
cout << "插入失败" << endl;
exit(0);
}
}
cout << endl;
// TrieTreeNode *copy = test_ptr.copy();
for (vector<string>::iterator p = random_str.begin(); p != random_str.end(); ++p)
{
cout << "删除字符串" << *p << endl;
if (test_obj.deleteElem(*p))
{
cout << "删除成功" << endl;
cout << "当前Trie为:" << endl << test_obj << endl;
TrieTree copy(test_obj);
cout << "当前Trie的副本为:" << endl << copy << endl;
}
else
{
cout << "删除失败" << endl;
exit(0);
}
}
cout << endl;
shuffle(mod.begin(), mod.end(), default_random_engine());
for (string::size_type i = 1; i <= mod.size(); ++i)
{
string temp(mod, 0, i);
cout << "插入字符串" << mod <<"的前缀" << temp << endl;
if (test_obj.insert(temp))
{
cout << "插入成功" << endl;
cout << "当前Trie为:" << endl << test_obj << endl;
TrieTree copy(test_obj);
cout << "当前Trie的副本为:" << endl << copy << endl;
}
else
{
cout << "插入失败" << endl;
exit(0);
}
}
for (string::size_type i = 1; i <= mod.size(); ++i)
{
string temp(mod, 0, i);
cout << "删除字符串" << mod << "的前缀" << temp << endl;
if (test_obj.deleteElem(temp))
{
cout << "删除成功" << endl;
cout << "当前Trie为:" << endl << test_obj << endl;
TrieTree copy(test_obj);
cout << "当前Trie的副本为:" << endl << copy << endl;
}
else
{
cout << "删除失败" << endl;
exit(0);
}
}
return 0;
}第二种实现：分支节点使用数组保存前缀的索引
#include <map>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <random>
#include <tuple>
using namespace std;
enum Compare_Result { EQUAL, LEFT_IS_PREFIX, RIGHT_IS_PREFIX, NOT_EQUAL };
struct TrieTreeNode //Trie树节点类型
{
enum NodeType { DATANODE, BRANCHNODE } type_flag; //节点类型标志，分支节点或存放关键字的叶节点
struct BranchNode
{
vector<TrieTreeNode*> sub_ptr;
size_t num;
BranchNode() :sub_ptr(128, nullptr), num(0){}
BranchNode(const BranchNode& B) :num(B.num), sub_ptr(128, nullptr) {}
};
union
{
string key_in_trie; //叶节点关键字
BranchNode branch_ptr; //分支节点的分支字符和对应的指向分支字符对应的子节点的指针之间的映射关系
};
TrieTreeNode(const string& k) :type_flag(NodeType::DATANODE), key_in_trie(k) {}
TrieTreeNode() :type_flag(NodeType::BRANCHNODE), branch_ptr() {}
TrieTreeNode(TrieTreeNode& be_copied)
{
switch (be_copied.type_flag)
{
case NodeType::DATANODE:{ new (&key_in_trie) string(be_copied.key_in_trie); break; }
case NodeType::BRANCHNODE:{ new (&branch_ptr) BranchNode(be_copied.branch_ptr); break; }
}
type_flag = be_copied.type_flag;
}
~TrieTreeNode()
{
switch (type_flag)
{
case NodeType::DATANODE: key_in_trie.~string(); break;
case NodeType::BRANCHNODE: branch_ptr.~BranchNode(); break;
}
}
};
class TrieTree
{
public:
bool insert(const string& be_inserted) const; //Trie树中插入关键字,true成功false失败
bool deleteElem(const string& be_deleted) const; //Trie树中删除指定关键字,true成功false失败
TrieTreeNode* copy(); //拷贝Trie树，返回指向副本Trie树的指针
TrieTree() { root = new TrieTreeNode(); }
TrieTree(TrieTree& be_copied) { root = be_copied.copy(); }
void printTrieTree(TrieTreeNode* cur, size_t offset) const;
bool isEmpty() const { return root->branch_ptr.num == 0; }
TrieTreeNode* getTrieTree() const { return root; }
~TrieTree();
private:
template <typename T>
Compare_Result static strCompare(const string& left, const string& right, T i);
static size_t char_to_index(const char& ch)
{
return ch;
}
TrieTreeNode* root; //Trie树根节点
};
ostream& operator<<(ostream& o, const TrieTree& be_output)
{
if (be_output.isEmpty())
{
o << "NULL" << endl;
return o;
}
be_output.printTrieTree(be_output.getTrieTree(), 0);
return o;
}
template <typename T>
Compare_Result TrieTree::strCompare(const string& left, const string& right, T i)
{
for (; ; ++i)
{
if (i == left.size() && i == right.size())
return Compare_Result::EQUAL;
else if (i == left.size() || i == right.size())
{
if (i == left.size())
return Compare_Result::LEFT_IS_PREFIX;
else
return Compare_Result::RIGHT_IS_PREFIX;
}
else if (left[i] != right[i])
return Compare_Result::NOT_EQUAL;
}
}
bool TrieTree::deleteElem(const string& be_deleted) const
{
TrieTreeNode* run = root;
stack<TrieTreeNode*> work_stack;
size_t index;
{
string::size_type i = 0;
while (run->type_flag == TrieTreeNode::NodeType::BRANCHNODE)
{
if (i < be_deleted.size())
{
index = char_to_index(be_deleted[i]);
if (run->branch_ptr.sub_ptr[index] == nullptr)
return false;
++i;
work_stack.push(run);
run = run->branch_ptr.sub_ptr[index];
}
else
{
if (run->branch_ptr.sub_ptr[0] == nullptr)
return false;
work_stack.push(run);
run = run->branch_ptr.sub_ptr[0];
index = 0;
}
}
if (run != work_stack.top()->branch_ptr.sub_ptr[0] && strCompare(be_deleted, run->key_in_trie, i) != Compare_Result::EQUAL)
return false;
}
work_stack.top()->branch_ptr.sub_ptr[index] = nullptr;
delete run;
--work_stack.top()->branch_ptr.num;
if (work_stack.top() != root && work_stack.top()->branch_ptr.num == 1)
{
for (index = 0; index < work_stack.top()->branch_ptr.sub_ptr.size(); ++index)
{
if (work_stack.top()->branch_ptr.sub_ptr[index] != nullptr)
break;
}
if (work_stack.top()->branch_ptr.sub_ptr[index]->type_flag == TrieTreeNode::NodeType::DATANODE)
{
run = work_stack.top()->branch_ptr.sub_ptr[index];
delete work_stack.top();
work_stack.pop();
while (work_stack.top() != root)
{
if (work_stack.top()->branch_ptr.num >= 2)
{
work_stack.top()->branch_ptr.sub_ptr[char_to_index(be_deleted[work_stack.size() - 1])] = run;
return true;
}
else
{
delete work_stack.top();
work_stack.pop();
}
}
work_stack.top()->branch_ptr.sub_ptr[char_to_index(be_deleted[0])] = run;
}
}
return true;
}
bool TrieTree::insert(const string& be_inserted) const
{
TrieTreeNode* run = root;
string::size_type i = 0;
size_t index;
TrieTreeNode* father_of_leaf = nullptr;
while (run->type_flag != TrieTreeNode::NodeType::DATANODE)
{
if (i < be_inserted.size())
{
index = char_to_index(be_inserted[i]);
if (run->branch_ptr.sub_ptr[index] == nullptr)
{
run->branch_ptr.sub_ptr[index] = new TrieTreeNode(be_inserted);
++run->branch_ptr.num;
return true;
}
father_of_leaf = run;
run = run->branch_ptr.sub_ptr[index];
++i;
}
else
{
if (run->branch_ptr.sub_ptr[0] == nullptr)
{
run->branch_ptr.sub_ptr[0] = new TrieTreeNode(be_inserted);
++run->branch_ptr.num;
return true;
}
return false;
}
}
Compare_Result compare_result;
{
string::size_type start_index = i;
compare_result = strCompare<string::size_type &>(be_inserted, run->key_in_trie, i);
if (compare_result == Compare_Result::EQUAL)
return false;
father_of_leaf = father_of_leaf->branch_ptr.sub_ptr[index] = new TrieTreeNode();
for (; start_index < i; ++start_index)
{
father_of_leaf->branch_ptr.num = 1;
father_of_leaf = father_of_leaf->branch_ptr.sub_ptr[char_to_index(be_inserted[start_index])] = new TrieTreeNode();
}
}
if (compare_result == Compare_Result::LEFT_IS_PREFIX)
{
father_of_leaf->branch_ptr.sub_ptr[0] = new TrieTreeNode(be_inserted);
father_of_leaf->branch_ptr.sub_ptr[char_to_index(run->key_in_trie[i])] = run;
}
else if (compare_result == Compare_Result::RIGHT_IS_PREFIX)
{
father_of_leaf->branch_ptr.sub_ptr[0] = run;
father_of_leaf->branch_ptr.sub_ptr[char_to_index(be_inserted[i])] = new TrieTreeNode(be_inserted);
}
else
{
father_of_leaf->branch_ptr.sub_ptr[char_to_index(run->key_in_trie[i])] = run;
father_of_leaf->branch_ptr.sub_ptr[char_to_index(be_inserted[i])] = new TrieTreeNode(be_inserted);
}
father_of_leaf->branch_ptr.num = 2;
return true;
}
size_t find_next(TrieTreeNode* cur, size_t run)
{
for (; run < cur->branch_ptr.sub_ptr.size(); ++run)
{
if (cur->branch_ptr.sub_ptr[run] != nullptr)
return run;
}
}
TrieTree::~TrieTree()
{
TrieTreeNode* run = root;
stack<tuple<TrieTreeNode*, size_t, short>> work_stack;
bool trace_back_flag = true;
while (true)
{
if (trace_back_flag == true)
{
if (run == root)
{
if (run->branch_ptr.num == 0)
{
delete root;
return;
}
}
else
{
if (run->type_flag == TrieTreeNode::DATANODE)
{
delete run;
run = get<0>(work_stack.top());
if (run->branch_ptr.num != get<2>(work_stack.top()))
get<1>(work_stack.top()) = find_next(run, get<1>(work_stack.top()) + 1);
trace_back_flag = false;
continue;
}
}
work_stack.push(make_tuple(run, find_next(run, 0), 1));
run = run->branch_ptr.sub_ptr[get<1>(work_stack.top())];
}
else
{
if (run == root || get<2>(work_stack.top()) != run->branch_ptr.num)
{
if (run == root)
{
if (get<2>(work_stack.top()) == root->branch_ptr.num)
{
delete root;
return;
}
}
++get<2>(work_stack.top());
run = run->branch_ptr.sub_ptr[get<1>(work_stack.top())];
trace_back_flag = true;
}
else
{
delete run;
work_stack.pop();
run = get<0>(work_stack.top());
if (run->branch_ptr.num != get<2>(work_stack.top()))
get<1>(work_stack.top()) = find_next(run, get<1>(work_stack.top()) + 1);
}
}
}
}
TrieTreeNode* TrieTree::copy()
{
TrieTreeNode* be_copied = root;
stack<tuple<TrieTreeNode*, size_t, short>> work_stack;
stack<TrieTreeNode*> copy_trace_stack;
TrieTreeNode* root_of_copy = nullptr;
bool trace_back_flag = true;
while (true)
{
if (trace_back_flag)
{
if (be_copied->type_flag == TrieTreeNode::BRANCHNODE)
{
if (be_copied == root)
{
root_of_copy = new TrieTreeNode(*be_copied);
if (be_copied->branch_ptr.num == 0)
{
break;
}
copy_trace_stack.push(root_of_copy);
}
else
copy_trace_stack.push(copy_trace_stack.top()->branch_ptr.sub_ptr[get<1>(work_stack.top())] = new TrieTreeNode(*be_copied));
work_stack.push(make_tuple(be_copied, find_next(be_copied, 0), 1));
be_copied = be_copied->branch_ptr.sub_ptr[get<1>(work_stack.top())];
}
else
{
copy_trace_stack.top()->branch_ptr.sub_ptr[get<1>(work_stack.top())] = new TrieTreeNode(*be_copied);
be_copied = get<0>(work_stack.top());
trace_back_flag = false;
}
}
else
{
if (be_copied->branch_ptr.num != get<2>(work_stack.top()))
{
get<1>(work_stack.top()) = find_next(be_copied, get<1>(work_stack.top()) + 1);
++get<2>(work_stack.top());
be_copied = be_copied->branch_ptr.sub_ptr[get<1>(work_stack.top())];
trace_back_flag = true;
}
else
{
if (be_copied == root)
break;
work_stack.pop();
be_copied = get<0>(work_stack.top());
copy_trace_stack.pop();
}
}
}
return root_of_copy;
}
void TrieTree::printTrieTree(TrieTreeNode* cur, size_t offset) const
{
if (cur->type_flag == TrieTreeNode::BRANCHNODE)
{
size_t max_length;
if (cur->branch_ptr.sub_ptr[0] != nullptr)
max_length = 4;
else
max_length = 1;
int count = 0;
for (size_t run = 0; ; ++run)
{
if (cur->branch_ptr.sub_ptr[run] != nullptr)
{
++count;
for (size_t go = 1; go <= offset; ++go)
cout << " ";
if (run == 0)
cout << "NULL";
else
{
cout << static_cast<char>(run);
for (size_t go = 2; go <= max_length; ++go)
cout << " ";
}
cout << "|-" << endl;
printTrieTree(cur->branch_ptr.sub_ptr[run], offset + max_length + 2);
if (count == cur->branch_ptr.num)
break;
}
}
}
else
{
for (size_t go = 1; go <= offset; ++go)
cout << " ";
cout << "leaf:" << cur->key_in_trie << endl;
}
}
int main()
{
vector<string> test = { "bluebird", "bunting", "bobwhite", "bluejay" };
TrieTree test_obj;
for (vector<string>::iterator p = test.begin(); p != test.end(); ++p)
{
cout << "插入字符串" << *p << endl;
if (test_obj.insert(*p))
{
cout << "插入成功" << endl;
cout << "当前Trie为:" << endl << test_obj << endl;
TrieTree copy(test_obj);
cout << "当前Trie的副本为:" << endl << copy << endl;
}
else
{
cout << "插入失败" << endl;
exit(0);
}
}
cout << endl;
// TrieTreeNode *copy = test_ptr.copy();
//for (vector<string>::iterator p = test.begin(); p != test.end(); ++p)
{
cout << "删除字符串" << "bobwhite" << endl;
if (test_obj.deleteElem("bobwhite"))
{
cout << "删除成功" << endl;
cout << "当前Trie为:" << endl << test_obj << endl;
TrieTree copy(test_obj);
cout << "当前Trie的副本为:" << endl << copy << endl;
}
else
{
cout << "删除失败" << endl;
exit(0);
}
cout << "删除字符串" << "bluejay" << endl;
if (test_obj.deleteElem("bluejay"))
{
cout << "删除成功" << endl;
cout << "当前Trie为:" << endl << test_obj << endl;
TrieTree copy(test_obj);
cout << "当前Trie的副本为:" << endl << copy << endl;
}
else
{
cout << "删除失败" << endl;
exit(0);
}
}
cout << endl;
string mod = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
const int L = 9; // 随机字符串最大长度
const int r = 2; //相同长度重复次数
vector<int> LList(L);
vector<string> random_str;
for (int run = 0; run < LList.size(); ++run)
LList[run] = run + 1;
shuffle(LList.begin(), LList.end(), default_random_engine());
for (int re = 1; re <= r; ++re)
{
for (int run = 0; run < LList.size(); ++run)
{
string r;
for (int go = 1; go <= LList[run]; ++go)
{
r.append(1, mod[rand() % mod.size()]);
}
random_str.push_back(r);
}
}
for (vector<string>::iterator p = random_str.begin(); p != random_str.end(); ++p)
{
cout << "插入字符串" << *p << endl;
if (test_obj.insert(*p))
{
cout << "插入成功" << endl;
cout << "当前Trie为:" << endl << test_obj << endl;
TrieTree copy(test_obj);
cout << "当前Trie的副本为:" << endl << copy << endl;
}
else
{
cout << "插入失败" << endl;
exit(0);
}
}
cout << endl;
// TrieTreeNode *copy = test_ptr.copy();
for (vector<string>::iterator p = random_str.begin(); p != random_str.end(); ++p)
{
cout << "删除字符串" << *p << endl;
if (test_obj.deleteElem(*p))
{
cout << "删除成功" << endl;
cout << "当前Trie为:" << endl << test_obj << endl;
TrieTree copy(test_obj);
cout << "当前Trie的副本为:" << endl << copy << endl;
}
else
{
cout << "删除失败" << endl;
exit(0);
}
}
cout << endl;
random_str.clear();
for (int i = 1; i <= 7; ++i)
{
string temp(mod, 0, i);
for (int run = 1; run <= 7; ++run)
{
string r;
for (int go = 1; go <= run; ++go)
{
r.append(1, mod[rand() % mod.size()]);
}
random_str.push_back(temp + r);
}
}
cout << "测试字符串有共同前缀不相等情形" << endl;
for (vector<string>::iterator p = random_str.begin(); p != random_str.end(); ++p)
{
cout << "插入字符串" << *p << endl;
if (test_obj.insert(*p))
{
cout << "插入成功" << endl;
cout << "当前Trie为:" << endl << test_obj << endl;
TrieTree copy(test_obj);
cout << "当前Trie的副本为:" << endl << copy << endl;
}
else
{
cout << "插入失败" << endl;
exit(0);
}
}
cout << endl;
// TrieTreeNode *copy = test_ptr.copy();
for (vector<string>::iterator p = random_str.begin(); p != random_str.end(); ++p)
{
cout << "删除字符串" << *p << endl;
if (test_obj.deleteElem(*p))
{
cout << "删除成功" << endl;
cout << "当前Trie为:" << endl << test_obj << endl;
TrieTree copy(test_obj);
cout << "当前Trie的副本为:" << endl << copy << endl;
}
else
{
cout << "删除失败" << endl;
exit(0);
}
}
cout << endl;
shuffle(mod.begin(), mod.end(), default_random_engine());
for (string::size_type i = 1; i <= mod.size(); ++i)
{
string temp(mod, 0, i);
cout << "插入字符串" << mod << "的前缀" << temp << endl;
if (test_obj.insert(temp))
{
cout << "插入成功" << endl;
cout << "当前Trie为:" << endl << test_obj << endl;
TrieTree copy(test_obj);
cout << "当前Trie的副本为:" << endl << copy << endl;
}
else
{
cout << "插入失败" << endl;
exit(0);
}
}
for (string::size_type i = 1; i <= mod.size(); ++i)
{
string temp(mod, 0, i);
cout << "删除字符串" << mod << "的前缀" << temp << endl;
if (test_obj.deleteElem(temp))
{
cout << "删除成功" << endl;
cout << "当前Trie为:" << endl << test_obj << endl;
TrieTree copy(test_obj);
cout << "当前Trie的副本为:" << endl << copy << endl;
}
else
{
cout << "删除失败" << endl;
exit(0);
}
}
return 0;
}每种实现应该都能适用于空串""的插入删除，自己没有验证过，感兴趣可自行验证