Tree.hpp V2.0!!!
连夜|加工……
不解释，自己看吧……
（告诉你们把，就是可以使用自定义数据类型来保存子节点了）
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
#include <exception>
#include <typeinfo>
#include <cstring>
#include <memory>
#include <bits/c++config.h>
#include <bits/stl_pair.h>
#include <stack>
#include <queue>
namespace std
{
template <typename _Value, typename _Skidtp = void *>
class tree_node
{
void *par;
_Value val;
string code;
protected:
tree_node(void *par = nullptr, _Value val = _Value(), string code = "")
: par(par == nullptr ? this : par), val(val), code(code) {}
~tree_node() = default;
string &code_reference()
{
return code;
}
_Value &val_reference()
{
return val;
}
void *&par_reference()
{
return par;
}
public:
string get_code()
{
return code;
}
_Value get_val()
{
return val;
}
void *get_par()
{
return par;
}
string set_code(string code)
{
this->code = code;
return this->code;
}
_Value set_val(_Value val)
{
this->val = val;
return this->val;
}
void *set_par(void *par)
{
this->par = par;
return this->par;
}
};
template <typename _Value>
class tree_node<_Value, vector<tree_node<_Value> *>> : tree_node<_Value>
{
public:
typedef tree_node<_Value> base_type;
typedef tree_node<_Value, 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:
using base_type::get_code;
using base_type::get_par;
using base_type::get_val;
using base_type::set_code;
using base_type::set_par;
using base_type::set_val;
tree_node(self_type *par = nullptr, store_kid_type kid_list = {}, _Value val = _Value(), string code = "")
: tree_node<_Value, void *>(par, val, code), kid(kid_list.empty() ? store_kid_type(1, this) : kid_list) {}
~tree_node()
{
base_type::~tree_node();
if (par != this)
{
store_kid_type &parKid = parKid;
parKid.erase(find(parKid.begin(), parKid.end(), this));
}
if (kid.front() != this)
for (typename store_kid_type::iterator it = kid.begin(); it != kid.end(); it++)
(*it)->set_par(*it);
}
store_kid_type get_kid_list()
{
return kid;
}
store_kid_type set_kid_list(store_kid_type kid_list)
{
kid = kid_list;
return kid;
}
store_kid_type &kid_list()
{
return kid;
}
bool no_kid()
{
return kid.empty();
}
bool single_kid()
{
return kid.size() == 1;
}
bool multiple_kid()
{
return kid.size() > 1;
}
bool is_leaf_node()
{
if (!repair())
throw runtime_error(strcat(strcat((char *)"std::tree_node<", typeid(_Value).name()),
">::is_leaf_node() -> Runtime error: Repair a tree_node unsuccessfully."));
return kid.front() == this;
}
bool is_root_node()
{
if (!repair())
throw runtime_error(strcat(strcat((char *)"std::tree_node<", typeid(_Value).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()
{
if (par_is_invalid())
par = this;
if (kid_is_invalid())
if (kid.size() <= 1)
kid = {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();
}
};
enum tree_sequence
{
preorder,
inorder,
postorder,
levorder,
rpreorder,
rinorder,
rpostorder,
rlevorder
};
template <typename _Value,
typename _Snodkidtp,
typename _Alloc = allocator<tree_node<_Value, _Snodkidtp>>>
class tree
{
typedef tree_node<_Value, _Snodkidtp> node_type;
typedef typename tree_node<_Value, _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 code The code string of the root node.
*
* This constructor constructs a root node by
* given @a val or default value of @a _Value, @a kid or no kids and @a code or default code: "0:root",
* and creates a %tree with the constructed root node.
*/
tree(_Value val = _Value(), node_kid_type kid = {}, string code = "0:root") : rot(alloc.allocate(1)), node_amount(1)
{
dynamicT_n.push_back({rot, 1});
alloc.construct(rot, rot, kid, val, code);
}
/**
* @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 code The codestring of the root node.
*
* This constructor assign @a kid and @a code 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 = {}) : rot(t_n), node_amount(1)
{
rot->set_par(t_n);
rot->kid_list() = kid.empty() ? node_kid_type{t_n} : kid;
}
tree(node_type *t_n, _Value val, node_kid_type kid = {})
: rot(t_n), node_amount(1)
{
rot->set_val(val);
rot->set_par(t_n);
rot->kid_list() = kid.empty() ? node_kid_type{t_n} : kid;
}
tree(node_type *t_n, node_kid_type kid, string code) : rot(t_n), node_amount(1)
{
rot->set_par(t_n);
rot->kid_list() = kid;
rot->set_code(code);
}
tree(node_type *t_n, _Value val, node_kid_type kid, string code)
: rot(t_n), node_amount(1)
{
rot->set_val(val);
rot->set_par(t_n);
rot->kid_list() = kid;
rot->set_code(code);
}
/**
* @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, _Value val = _Value(), 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<_Value> *emplace_below(tree_node<_Value> *par, vector<tree_node<_Value> *> extra_kid = {},
_Value val = _Value(), string code = string())
{
// Try to allocate a new tree node.
tree_node<_Value> *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<_Value> *t_n, tree_node<_Value> *par, node_kid_type extra_kid = {},
bool change_val = false, _Value val = _Value(),
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(_Value 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(_Value).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_code())
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_code())
return t_n;
sta.pop();
}
}
break;
}
// Levorder & rlevorder.
case 2:
{
if (find_by_val && val == rot->get_val() || !find_by_val && code == rot->get_code())
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_code() == code)
return *it;
if (!(*it)->is_leaf_node())
que.push(*it);
}
que.pop();
}
}
}
// If unseccessful return nullptr.
return nullptr;
}
};
}附上测试代码：
#include <iostream>
using std::cin;
using std::cout;
#include <cstdio>
using std::printf;
using std::scanf;
#include <array>
#include "Tree.hpp"
int main()
{
typedef std::vector<std::tree_node<int> *> skidtp;
typedef std::tree_node<int, skidtp> node_type;
std::tree<int, skidtp> tre(0);
std::vector<std::tree_node<int, skidtp> *> &rotkid = tre.get_root()->kid_list();
tre.emplace_kid(tre.get_root(), 1, {}, "1");
node_type *t_n1 = tre.emplace_kid(tre.get_root(), 2, {}, "2");
tre.emplace_kid(tre.get_root(), 3, {}, "3");
node_type *t_n2 = tre.emplace_kid(tre.get_root(), 4, {}, "4");
tre.emplace_kid(t_n1, 5, {}, "5:a");
tre.emplace_kid(t_n2, 5, {}, "5:b");
cout << tre.at(2, 1)->get_code() << '\n';
node_type *it = tre.find(5, std::rlevorder);
if (it == nullptr)
cout << "false\n";
else
cout << it->get_code() << '\n';
return 0;
}