不说啥了，上代码~
#include <string>
#include <bitset>
#include <vector>
#include <algorithm>
#include <iterator>
#include <initializer_list>
#include <exception>
#include <typeinfo>
#include <cstring>
#include <memory>
#include <bits/c++config.h>
#include <bits/stl_pair.h>
#include <stack>
#include <queue>
// #include <functional>
#include <iostream>
namespace std
{
#define __tree_version__ 2.1
template <typename _Tp, typename _Skidtp = void>
class tree_node
{
protected:
typedef size_t size_type;
private:
tree_node<_Tp> *par;
_Tp val;
string id;
protected:
tree_node(tree_node<_Tp> *par = nullptr, _Tp val = _Tp(), string id = "")
: par(par == nullptr ? this : par), val(val), id(id) {}
tree_node(const tree_node<_Tp, _Skidtp> &t_n)
: par(t_n.par == t_n ? this : t_n.par), val(t_n.val), id(t_n.id) {}
~tree_node() = default;
string &id_reference()
{
return id;
}
_Tp &val_reference()
{
return val;
}
tree_node<_Tp> *&par_reference()
{
return par;
}
public:
string get_id()
{
return id;
}
_Tp get_val()
{
return val;
}
tree_node<_Tp> *get_par()
{
return par;
}
string set_id(string id)
{
this->id = id;
return this->id;
}
_Tp set_val(_Tp val)
{
this->val = val;
return this->val;
}
tree_node<_Tp> *set_par(tree_node<_Tp> *par)
{
this->par = par;
return this->par;
}
};
template <typename _Tp>
using tree_node_base = tree_node<_Tp>;
template <typename _Tp>
using vectree_node_Skidtp = vector<tree_node_base<_Tp> *>;
template <typename _Tp>
class tree_node<_Tp, vectree_node_Skidtp<_Tp>> : public tree_node_base<_Tp>
{
public:
typedef tree_node_base<_Tp> base_type;
typedef typename base_type::size_type size_type;
typedef tree_node<_Tp, vector<base_type *>> self_type;
typedef vector<self_type *> store_kid_type;
private:
store_kid_type kid;
self_type *&par = (self_type *&)base_type::par_reference();
public:
tree_node(self_type *par = nullptr, store_kid_type kid_list = {}, _Tp val = _Tp(), string id = "",
bool change_kid_par = false)
: base_type(par, val, id), kid(!change_kid_par || kid_list.empty() ? store_kid_type(1, this) : kid_list)
{
if (!is_root_node(false))
par->kid_push_back(this);
if (change_kid_par && !is_leaf_node())
for (typename store_kid_type::iterator it = kid.begin(); it != kid.end(); it++)
{
if (!(*it)->is_root_node())
((self_type *)(*it)->get_par())->erase_kid(*it);
(*it)->set_par(this);
}
}
tree_node(const self_type &t_n, bool change_kid_par = false)
: base_type(t_n), kid(!change_kid_par || kid.is_leaf_node() ? store_kid_type(1, this) : t_n.get_kid_list())
{
if (!is_root_node())
par->kid_push_back(this);
if (change_kid_par && !is_leaf_node())
{
t_n.set_to_leaf();
for (typename store_kid_type::iterator it = kid.begin(); it != kid.end(); it++)
(*it)->set_par(this);
}
}
~tree_node()
{
bool is_not_root = !is_root_node(), is_not_leaf = !is_leaf_node();
if (is_not_root)
{
par->erase_kid(this);
if (is_not_leaf)
par->insert_kid(par->kid_list_size(), kid.begin(), kid.end());
}
if (is_not_leaf)
if (is_not_root)
for (typename store_kid_type::iterator it = kid.begin(); it != kid.end(); it++)
(*it)->set_par(par);
else
for (typename store_kid_type::iterator it = kid.begin(); it != kid.end(); it++)
(*it)->set_to_root();
}
store_kid_type get_kid_list()
{
return kid;
}
pair<store_kid_type, bool> set_kid_list(const store_kid_type kid_list)
{
kid = kid_list;
return make_pair(kid, repair_kid());
}
self_type *kid_at(size_type pos)
{
return kid.at(pos);
}
self_type *front()
{
return kid.front();
}
self_type *back()
{
return kid.back();
}
template <typename... _Args>
bool kid_emplace_back(_Args &&...args)
{
kid.emplace_back(forward<_Args>(args)...);
return repair_kid();
}
bool kid_push_back(self_type *kid_ptr)
{
if (kid_ptr == nullptr || kid_ptr == this)
return true;
kid.push_back(kid_ptr);
return repair_kid();
}
template <typename... _Args>
pair<size_type, bool> kid_emplace(size_type pos, _Args &&...args)
{
return make_pair(kid.emplace(kid.begin() + pos, forward<_Args>(args)...) - kid.begin(), repair_kid());
}
pair<size_type, bool> insert_kid(size_type pos, initializer_list<self_type *> init_list)
{
return make_pair(kid.insert(kid.begin() + pos, init_list) - kid.begin(), repair_kid());
}
pair<size_type, bool> insert_kid(size_type pos, self_type *&&kid_ptr)
{
return make_pair(kid.insert(kid.begin() + pos, kid_ptr) - kid.begin(), repair_kid());
}
pair<size_type, bool> insert_kid(size_type pos, const self_type *kid_ptr)
{
return make_pair(kid.insert(kid.begin() + pos, kid_ptr) - kid.begin(), repair_kid());
}
template<typename _InputIterator>
pair<size_type, bool> insert_kid(size_type pos, _InputIterator first, _InputIterator last)
{
return make_pair(kid.insert(kid.begin() + pos, first, last) - kid.begin(), repair_kid());
}
pair<size_type, bool> insert_kid(size_type pos, store_kid_type kid_list)
{
return make_pair(kid.insert(kid.begin() + pos, kid_list.begin(), kid_list.end()) - kid.begin(), repair_kid());
}
void clear_kid()
{
return kid.clear();
}
size_type erase_kid(size_type pos)
{
return kid.erase(kid.begin() + pos) - kid.begin();
}
size_type erase_kid(size_type first, size_type last)
{
return kid.erase(kid.begin() + first, kid.begin() + last) - kid.begin();
}
size_type erase_kid(self_type *nptr)
{
return kid.erase(find(kid.begin(), kid.end(), nptr)) - kid.begin();
}
void kid_pop_back()
{
kid.pop_back();
}
size_type kid_list_capacity()
{
return kid.capacity;
}
size_type kid_list_max_size()
{
return kid.max_size();
}
void reserve_kid_list(size_type n)
{
kid.reserve(n);
}
void resize_kid_list(size_type new_size)
{
kid.resize(new_size);
}
void shrink_kid_list()
{
return kid.shrink_to_fit();
}
void reverse_kid_list()
{
reverse(kid.begin(), kid.end());
}
size_t find_kid(self_type *kid_ptr)
{
return find(kid.begin(), kid.end(), kid_ptr) - kid.begin();
}
void swap_kid(size_type a_pos, size_type b_pos)
{
swap(kid.at(a_pos), kid.at(b_pos));
}
/**
* @brief This function is too dangerous to use, because it returns the true reference of the kid list!
* @return The reference of the kid list.
*
* This function returns the reference of the kid list.
*/
store_kid_type &kid_list()
{
return kid;
}
size_type kid_list_size()
{
return kid.size();
}
bool no_kid()
{
return kid.empty();
}
bool single_kid()
{
return kid.size() == 1;
}
bool multiple_kid()
{
return kid.size() > 1;
}
void set_to_leaf()
{
for (typename store_kid_type::iterator it = kid.begin(); it != kid.end(); it++)
(*it)->set_par = (*it);
kid.assign(1, this);
}
void set_to_root()
{
par->erase_kid(this);
par = this;
}
bool is_leaf_node(bool need_repair = true)
{
if (need_repair && !repair())
throw runtime_error(strcat(strcat((char *)"std::tree_node<", typeid(_Tp).name()),
">::is_leaf_node() -> Runtime error: Repair a tree_node unsuccessfully."));
return kid.front() == this;
}
bool is_root_node(bool need_repair = true)
{
if (need_repair && !repair())
throw runtime_error(strcat(strcat((char *)"std::tree_node<", typeid(_Tp).name()),
">::is_leaf_node() -> Runtime error: Repair a tree_node unsuccessfully."));
return par == this;
}
bool kid_is_invalid()
{
return kid.empty() ||
find(kid.begin(), kid.end(), nullptr) != kid.end() ||
kid.size() > 1 && find(kid.begin(), kid.end(), this) != kid.end();
}
bool par_is_invalid()
{
return par == nullptr;
}
bool is_usable()
{
return !(par_is_invalid() && kid_is_invalid());
}
bool repair_par()
{
if (par_is_invalid())
par = this;
return is_usable();
}
bool repair_kid()
{
if (kid_is_invalid())
if (kid.size() <= 1)
kid.assign(1, this);
else
{
for (typename store_kid_type::iterator it = kid.begin(); it != kid.end(); it++)
while (it != kid.end() && *it == nullptr || *it == this)
kid.erase(it);
}
return is_usable();
}
bool repair()
{
repair_par();
repair_kid();
return is_usable();
}
};
template <typename _Tp>
using vectree_node = tree_node<_Tp, vectree_node_Skidtp<_Tp>>;
/**
* An enum which represents the order of traveling a %tree
*/
enum tree_sequence
{
preorder,
inorder,
postorder,
levorder,
rpreorder,
rinorder,
rpostorder,
rlevorder
};
/**
* @brief A container which implements hierarchical structure, which shaped like an inverted tree.
*
* @tparam _Tp Type of the value in a %tree_node.
* @tparam _Snodkidtp Type of the kid list in a %tree_node, defaults to vector<tree_node<_Tp> *>.
* Exactly, it's the same as the second template parameter of %tree_node.
* @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
*/
template <typename _Tp,
typename _Snodkidtp = typename vectree_node<_Tp>::store_kid_type,
// typename _Hash = hash<_Tp>,
// typename _Pred = equal_to<_Tp>,
typename _Alloc = allocator<tree_node<_Tp, _Snodkidtp>>>
class tree
{
typedef tree_node<_Tp, _Snodkidtp> node_type;
typedef typename tree_node<_Tp, _Snodkidtp>::store_kid_type node_kid_type;
typedef vector<pair<node_type *, size_t>> store_dynamic_type;
node_type *rot;
size_t node_amount;
_Alloc alloc;
store_dynamic_type dynamicT_n;
public:
/**
* @brief Creates a %tree with a root node.
* @param val The value of the root node.
* @param kid A %vector of pointers to kid nodes of the root node.
* @param id The id of the root node.
*
* This constructor constructs a root node by given @a val or default value of @a _Tp,
* @a par or a pointer to root node itself, @a kid or no kids and @a id or default id: "0:root",
* and creates a %tree with the constructed root node.
*/
tree(_Tp val = _Tp(), node_type *par = nullptr, node_kid_type kid = {}, string id = "0:root")
: rot(alloc.allocate(1)), node_amount(1)
{
dynamicT_n.push_back({rot, 1});
alloc.construct(rot, par, kid, val, id);
}
tree(node_type *t_n, node_type ¤t) : rot(t_n), node_amount(1)
{
*rot = current;
}
/**
* @brief Creates a %tree with a given root node.
* @param t_n A pointer to a tree node.
* @param kid A %vector of pointers to kid nodes of the root node.
* @param id The id of the root node.
*
* This constructor assign @a kid and @a id to the given tree node @a t_n,
* and set @a t_n to the root node a %tree
*/
tree(node_type *t_n, node_kid_type kid, string id) : rot(t_n), node_amount(1)
{
rot->set_par(t_n);
rot->kid_list() = kid;
rot->set_id(id);
}
tree(node_type *t_n, _Tp val, node_kid_type kid, string id)
: rot(t_n), node_amount(1)
{
rot->set_val(val);
rot->set_par(t_n);
rot->kid_list() = kid;
rot->set_id(id);
}
/**
* @brief A destructor.
*
* The destructor only erases the elements,
* and if the elements themselves are pointers, the pointed-to memory is not touched in any way.
* Managing the pointer is the user's responsibility.
*/
~tree()
{
for (typename store_dynamic_type::iterator it = dynamicT_n.begin(); !dynamicT_n.empty(); it = dynamicT_n.begin())
{
alloc.destroy(it->first);
alloc.deallocate(it->first, it->second);
dynamicT_n.erase(it);
}
dynamicT_n.clear();
}
/**
* @brief Return a pointer to the root node of a %tree.
* @return A pointer to the root node of a %tree.
*
* This function returns a pointer to the root of a %tree.
*/
node_type *get_root()
{
return rot;
}
/**
* @brief Return the number of elements in a %tree.
* @return An interger giving the number of elements in a %tree.
*
* This function returns the number of elements in a %tree.
*/
size_t size()
{
return node_amount;
}
/**
* @brief Get a pointer to a %tree_node in a %tree.
* @param dep The depth of a %tree_node which is wanted to find.
* @param ord The sequence number of a %tree_node which is wanted to find.
* @return A pointer to a %tree_node or nullptr if not find.
*
* This function tries to get the %tree_node at the designated position.
* If successful it returns a pointer to the %tree_node.
* If unsuccessful it returns nullptr.
*/
node_type *at(size_t dep, size_t ord)
{
queue<node_type *> que;
que.push(rot);
while (dep-- > 0)
{
size_t i = que.size();
while (que.size() - i <= ord && i > 0)
{
node_kid_type kid = que.front()->get_kid_list();
que.pop();
i--;
for (typename node_kid_type::iterator it = kid.begin(); it < kid.end() && que.size() - i <= ord; it++)
if (dep == 0 || !(*it)->is_leaf_node())
que.push(*it);
}
while (i-- > 0)
que.pop();
if (que.size() == 0)
return nullptr;
}
return que.size() <= ord ? nullptr : que.back();
}
typename node_kid_type::iterator insert_kid(node_type *par, node_type *t_n, size_t index = 0xffffffffffffffffULL)
{
// parKid: A reference to a %vector of child nodes of a parent node.
node_kid_type &parKid = par->kid_list();
if (par->is_leaf_node())
parKid.clear();
parKid.insert(index == 0xffffffffffffffffULL ? parKid.end() : parKid.begin() + index, t_n);
return index == 0xffffffffffffffffULL ? --parKid.end() : parKid.begin() + index;
}
node_type *emplace_kid(node_type *par, _Tp val = _Tp(), node_kid_type kid = {}, string code = "",
size_t index = 0xffffffffffffffffULL)
{
// If index > the size of the kid list of the parent node return nullptr
// parKid: A reference to a %vector of child nodes of a parent node.
node_kid_type &parKid = par->kid_list();
if (index != 0xffffffffffffffffULL && index > parKid.size())
return nullptr;
// Check if the parent node is also the leave node.
if (par->is_leaf_node())
parKid.clear();
// Try to allocate a new tree node.
node_type *ptr = alloc.allocate(1);
// If unsuccessful return nullptr.
if (ptr == nullptr)
return nullptr;
// If successful push ptr into dynamicT_n and construct ptr.
dynamicT_n.push_back({ptr, 1});
node_amount++;
alloc.construct(ptr, par, kid, val, code);
// Insert ptr into parKid.
parKid.insert(index == 0xffffffffffffffffULL ? parKid.end() : parKid.begin() + index, ptr);
// Return ptr.
return ptr;
}
/**
* @brief Emplace a new %tree_node into a %tree below a %tree_node in the %tree.
* @param par A pointer to the parent %tree_node of the new %tree_node.
* @param extra_kid A %vector including pointers to extra kid %tree_nodes of the new %tree_node.
* @param val The value of the new %tree_node.
* @param code A %string giving the code of the new %tree_node.
* @return A pointer to the new %tree_node, or nullptr if unsuccessful.
*
* This function tries to create a %tree_node with the given data and emplace it below @a par.
* If successful it returns a pointer to the new %tree_node.
* If unsuccessful it returns nullptr.
*/
tree_node<_Tp> *emplace_below(tree_node<_Tp> *par, vector<tree_node<_Tp> *> extra_kid = {},
_Tp val = _Tp(), string code = string())
{
// Try to allocate a new tree node.
tree_node<_Tp> *ptr = alloc.allocate(1);
// If unsuccessful return nullptr.
if (ptr == nullptr)
return nullptr;
// If successful push ptr into dynamicT_n.
dynamicT_n.push_back({ptr, 1});
node_amount++;
// Check if par is also the leave node.
// parKid: A reference to a %vector of child nodes of a parent node.
node_kid_type &parKid = par->kid_list();
if (par->is_leaf_node())
parKid.clear();
// Construct the new tree node.
for (typename node_kid_type::iterator it = parKid.begin(); it != parKid.end(); it++)
extra_kid.push_back(*it);
alloc.construct(ptr, par, extra_kid, val, code);
// Set the parent nodes of the extra kid nodes and the kid nodes of par to the new tree node.
for (typename node_kid_type::iterator it = extra_kid.begin(); it != extra_kid.end(); it++)
(*it)->set_par(ptr);
// Set the new node to the kid node of par.
parKid.assign(1, ptr);
// Return the pointer to the new node.
return ptr;
}
/**
* @brief Insert a %tree_node below into a %tree below a %tree_node in the %tree.
* @param t_n A pointer to a %tree_node that the user want to put it below @a par.
* @param par A pointer to the parent %tree_node of @a t_n.
* @param extra_kid A %vector including pointers to extra kid %tree_nodes of @a t_n.
* @param change_val A boolean, changes the value of @a t_n to @a val if true.
* @param val The new value of @a t_n.
* @param change_val A boolean, changes the code of @a t_n to @a code if true.
* @param code A new %string giving the code of @a t_n.
* @return A pointer to @a t_n.
*
* This function inserts @a t_n into a %tree below @a par, assigns the given data to @a t_n and
* returns a pointer to @a t_n.
*/
node_type *insert_below(tree_node<_Tp> *t_n, tree_node<_Tp> *par, node_kid_type extra_kid = {},
bool change_val = false, _Tp val = _Tp(),
bool change_code = false, string code = string())
{
// Check if par is also the leave node.
// parKid: A reference to a %vector of child nodes of par.
node_kid_type &parKid = par->kid_list();
if (par->is_leaf_node())
parKid.clear();
// Assign t_n
for (typename node_kid_type::iterator it = parKid.begin(); it != parKid.end(); it++)
extra_kid.push_back(*it);
t_n->kid_list() = extra_kid;
if (change_val)
t_n->set_val(val);
if (change_code)
t_n->set_code(code);
// Set the parent nodes of the extra kid nodes and the kid nodes of par to t_n.
for (typename node_kid_type::iterator it = extra_kid.begin(); it != extra_kid.end(); it++)
(*it)->set_par(t_n);
// Set t_n to the only kid node of par.
parKid.assign(1, t_n);
// Return t_n.
return t_n;
}
/**
* @brief Find the first %tree_node that occurs of a val or a %string giving a code in a %tree.
* @param val The val to find.
* @param order Find order(not include inorder and rinorder).
* @param check_order If true, the function will check @a order.
* @param find_by_val If true, the function will find by @a val, or it will find by @a code.
* @param code A %string giving a code to find.
* @return The first %tree_node pointer ptr in a %tree such that
* ptr->get_val() == @a val or ptr->get_code() == @a code, or nullptr if no such pointer exists.
* @throw If choose to check order and @a order is invalid, the function will throw std::invalid_argument.
*
* The function finds the first %tree_node that occurs of @a val or @a code in a %tree.
* If find a %tree_node like this, it will return a pointer to this %tree_node, or it will return nullptr.
* Also, if there is something wrong while looking for the target %tree_node
* (one is that @a order is "inorder" or "rinorder"), it will return nullptr.
* However, if the user choose to check @a order and @a order is indeed invalid,
* the function will throw std::invalid_argument.
*/
node_type *find(_Tp val, tree_sequence order = preorder, bool check_order = false,
bool find_by_val = true, string code = "")
{
// Record the order.
char tord = -1;
switch (order)
{
case preorder:
case rpreorder:
tord = 0;
break;
case postorder:
case rpostorder:
tord = 1;
break;
case levorder:
case rlevorder:
tord = 2;
break;
default:
// Check order if the user wants to.
if (check_order)
{
string wrong_type = "unknown type";
// Determine if it is "inorder" or "rinorder".
switch (order)
{
case inorder:
wrong_type = "inorder";
break;
case rinorder:
wrong_type = "rinorder";
}
// Throw an invalid argument error.
throw invalid_argument("std::tree<" + string(typeid(_Tp).name()) +
">::find_first() -> Invalid argument: argument \"order\"(" +
wrong_type + ") is invalid.");
}
}
// Record whether there is a prefix 'r'.
bool r__ = false;
switch (order)
{
case rpreorder:
case rpostorder:
case rlevorder:
r__ = true;
}
// Find the node by given information.
switch (tord)
{
// Preorder & reperorder &
// Postorder & rpostorder.
case 0:
case 1:
{
stack<pair<node_type *, size_t>> sta;
sta.push({rot, 0});
while (!sta.empty())
{
node_type *t_n = sta.top().first;
if (tord == 0 && find_by_val && val == t_n->get_val() || !find_by_val && code == t_n->get_id())
return t_n;
node_kid_type kid = t_n->get_kid_list();
if (r__)
reverse(kid.begin(), kid.end());
if (!t_n->is_leaf_node() && sta.top().second < kid.size())
{
int index = sta.top().second;
sta.pop();
sta.push({t_n, index + 1});
sta.push({kid.at(index), 0});
}
else
{
if (tord == 1 && find_by_val && val == t_n->get_val() || !find_by_val && code == t_n->get_id())
return t_n;
sta.pop();
}
}
break;
}
// Levorder & rlevorder.
case 2:
{
if (find_by_val && val == rot->get_val() || !find_by_val && code == rot->get_id())
return rot;
queue<node_type *> que;
que.push(rot);
while (!que.empty())
{
node_kid_type kid = que.front()->get_kid_list();
if (r__)
reverse(kid.begin(), kid.end());
for (typename node_kid_type::iterator it = kid.begin(); it != kid.end(); it++)
{
if (find_by_val && (*it)->get_val() == val || !find_by_val && (*it)->get_id() == code)
return *it;
if (!(*it)->is_leaf_node())
que.push(*it);
}
que.pop();
}
}
}
// If unseccessful return nullptr.
return nullptr;
}
};
}