数据结构备忘录:trie树基本操作

#include <map>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
using namespace std;

struct      //Trie树节点类型
{
    enum NodeType { DATANODE, BRANCHNODE } type_flag;  
    union
    {
        string key_in_trie;   //叶节点关键字
        map<string, 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<string, TrieTreeNode *>();
            for (map<string, TrieTreeNode *>::iterator p = be_copied.sub_ptr.begin(); p != be_copied.sub_ptr.end(); ++p)
            {
                sub_ptr.insert(make_pair(p->first, nullptr));
            }
          }
          break;
        }
    }
     
    ~TrieTreeNode()
    {
        switch (type_flag)
        {
        case NodeType::DATANODE : key_in_trie.~string(); break;
        case NodeType::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(); }
    ~TrieTree();
private:
    bool static strCompare(const string &left, const string &right, const size_t &i);
    TrieTreeNode *root;   //Trie树根节点
};

bool TrieTree::strCompare(const string &left, const string &right, const size_t &i)
{
    for (size_t j = i; ; ++j)
    {
        if (j >= left.size() && j >= right.size())
            return true;
        else if (j >= left.size() || j >= right.size())
            return false;
        else if (left[j] != right[j])
            return false;
    }
}

bool TrieTree::deleteElem(const string &be_deleted) const
{
    TrieTreeNode *run = root;
    stack<pair<TrieTreeNode *, map<string, TrieTreeNode *>::iterator>> work_stack;
    string::size_type i = 0;
    while (run->type_flag != TrieTreeNode::NodeType::DATANODE)
    {
        if (i < be_deleted.size())
        {
            string temp = be_deleted.substr(i, 1);
            ++i;
            map<string, TrieTreeNode *>::iterator it = run->sub_ptr.find(temp);
            if (it == run->sub_ptr.end())
            {
                return false;
            }
            else
            {
                work_stack.push(make_pair(run, it));
                run = it->second;
            }
        }
        else
        {
            map<string, TrieTreeNode *>::iterator it = run->sub_ptr.find("");
            if (it != run->sub_ptr.end())
            {
                work_stack.push(make_pair(run, it));
                run = it->second;
                break;
            }
            else
            {
                return false;
            }
        }
    }
    
    if (work_stack.top().second->first != "" && strCompare(be_deleted, run->key_in_trie, i) == false)
    {
        return false;
    }

    bool delete_or_not = true;
    while (work_stack.top().first != root)
    {
        if (delete_or_not == true)
        {
            delete work_stack.top().second->second;
            if (work_stack.top().second->second->type_flag == TrieTreeNode::NodeType::DATANODE)
            {
                run = nullptr;
            }

            work_stack.top().first->sub_ptr.erase(work_stack.top().second);

            if (work_stack.top().first->sub_ptr.size() >= 2)
            {
                return true;
            }
            else if (work_stack.top().first->sub_ptr.size() == 1)
            {
                if (work_stack.top().first->sub_ptr.begin()->second->type_flag != TrieTreeNode::NodeType::DATANODE)
                {
                    return true;
                }
                else
                {
                    run = work_stack.top().first->sub_ptr.begin()->second;
                    delete work_stack.top().first;
                    delete_or_not = false;
                }
            }
            work_stack.pop();
        }
        else
        {
            if (work_stack.top().first->sub_ptr.size() >= 2)
            {
                work_stack.top().second->second = run;
                return true;
            }
            else
            {
                delete work_stack.top().first;
                work_stack.pop();
            }
        }
    }

    if (delete_or_not == true)
    {
        delete work_stack.top().second->second;
        root->sub_ptr.erase(work_stack.top().second);
    }
    else
    {
        work_stack.top().second->second = run;
    }
    return true;
}

bool TrieTree::insert(const string &be_inserted) const 
{
    TrieTreeNode *run = root;
    map<string, TrieTreeNode *>::iterator father;
    string::size_type i = 0;
    while (run->type_flag != TrieTreeNode::NodeType::DATANODE)
    {
        if (i < be_inserted.size())
        {
            string temp = be_inserted.substr(i, 1);
            ++i;
            map<string, TrieTreeNode *>::iterator it = run->sub_ptr.find(temp);
            if (it == run->sub_ptr.end())
            {
                run->sub_ptr.insert(make_pair(temp, new TrieTreeNode(be_inserted)));
                return true;
            }
            else
            {
                father = it;
                run = it->second;
            }
        }
        else
        {
            if (run->sub_ptr.find("") != run->sub_ptr.end())
            {
                return false;
            }
            else
            {
                run->sub_ptr.insert(make_pair("", new TrieTreeNode(be_inserted)));
                return true;
            }
        }
    }
    
    if (strCompare(be_inserted, run->key_in_trie, i) == true)  
    {
        return false;
    }
    else
    {
        while (true)
        {
            father->second = new TrieTreeNode();
            if (i >= be_inserted.size())
            {
                father->second->sub_ptr.insert(make_pair("", new TrieTreeNode(be_inserted)));
                father->second->sub_ptr.insert(make_pair(run->key_in_trie.substr(i, 1), run));
            }
            else if (i >= run->key_in_trie.size())
            {
                father->second->sub_ptr.insert(make_pair("", run));
                father->second->sub_ptr.insert(make_pair(be_inserted.substr(i, 1), new TrieTreeNode(be_inserted)));
            }
            else if (be_inserted[i] != run->key_in_trie[i])
            {
                father->second->sub_ptr.insert(make_pair(run->key_in_trie.substr(i, 1), run));
                father->second->sub_ptr.insert(make_pair(be_inserted.substr(i, 1), new TrieTreeNode(be_inserted)));
            }
            else
            {
                father = father->second->sub_ptr.insert(make_pair(be_inserted.substr(i, 1), new TrieTreeNode())).first;
                ++i;
                continue;
            }
            return true;
        }
    }
}

TrieTree::~TrieTree()
{
    TrieTreeNode *run = root;
    stack<pair<TrieTreeNode *, map<string, 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 = 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)
            {
                if (work_stack.top().second == root->sub_ptr.end())
                {
                    delete root;
                    return;
                }

                run = work_stack.top().second->second;
                trace_back_flag = true;
            }
            else
            {
                if (work_stack.top().second != run->sub_ptr.end())
                {
                    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 = run->sub_ptr.erase(work_stack.top().second);
                }
            }
        }
    }
}

TrieTreeNode *TrieTree::copy()
{
    TrieTreeNode *be_copied = root;
    stack<pair<TrieTreeNode *, map<string, TrieTreeNode *>::iterator>> work_stack;
    stack<pair<TrieTreeNode *, map<string, 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->second = new TrieTreeNode(*be_copied);
                }
                else
                {
                    ++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
        {
            map<string, TrieTreeNode *>::iterator tempit = work_stack.top().second;
            if (tempit->second->type_flag != TrieTreeNode::DATANODE)
            {
                copy_trace_stack.pop();
            }

            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
            {
                if (++(work_stack.top().second) != be_copied->sub_ptr.end())
                {
                    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;
}

int main()
{
    vector<string> test = {"abcd", "abydb", "ary", "AFD", "abyc", "AFDGH", "AFMGB", "AFMGRQ", "cdfg", "cdgkn", "cdgkmq"};
    TrieTree test_obj;
    for (vector<string>::iterator p = test.begin(); p != test.end(); ++p)
    {
        cout << "插入字符串" << *p << endl;
        test_obj.insert(*p);
    }

    cout << endl;
    // TrieTreeNode *copy = test_ptr.copy();
    for (vector<string>::iterator p = test.begin(); p != test.end(); ++p)
    {
        cout << "删除字符串" << *p << endl;
        test_obj.deleteElem(*p);
    }
    cout << endl;
}