实现了tree数据结构
但半成品（悲
(空行)
(空行)
'\n'
V1.0
只实现了一点吧，然后tree<(自己看)>::find()没完全写好，也没测试
(谁要是帮我测试了并告诉我，我会很开心的qwq)
对了，那个memory（头文件）中的allocator总感觉不对呢……？
悄悄地告诉你：析构函数绝对有问题，好像内存泄漏了(但找不到问题啊啊啊!!)
好了，下面是源代码：
//（代码丢失了555……）.
.
.
.
.
其实注释不太好
V1.2(V1.1势了)
还是只实现了一点，但std::tree::find()欧克了。
析构函数现在应该是没问题啦。
改了一些函数的名字，自己看吧AWA
相比V1.0去掉了不必要的一些header，虽说速度也没快吧……
添加了很多注释哦，快感谢我awa（嘻嘻
:)-> 不会有人英文注释看不懂吧[疑惑.jpg]
下面是代码：
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
#include <memory>
#include <bits/c++config.h>
#include <bits/stl_tree.h>
#include <bits/stl_pair.h>
#include <exception>
#include <typeinfo>
#include <stack>
#include <queue>
namespace std
{
template <typename _Value>
class tree_node
{
private:
string code;
_Value val;
tree_node<_Value> *par;
vector<tree_node<_Value> *> kid;
public:
tree_node(_Value val = _Value(),
tree_node<_Value> *par = nullptr,
vector<tree_node<_Value> *> kid = {},
string code = "")
: code(code),
val(val),
par(par == nullptr ? this : par),
kid(kid.empty() ? vector<tree_node<_Value> *>{this} : kid) {}
~tree_node()
{
if (par != this && !par_is_invalid())
{
vector<tree_node<_Value> *> &parKid = parKid;
parKid.erase(find(parKid.begin(), parKid.end(), this));
}
if (kid.front() != this)
for (typename vector<tree_node<_Value> *>::iterator it = kid.begin(); it != kid.end(); it++)
(*it)->set_par(*it);
}
string get_code()
{
return code;
}
_Value get_val()
{
return val;
}
tree_node<_Value> *get_par()
{
return par;
}
vector<tree_node<_Value> *> get_kid_list()
{
return kid;
}
string set_code(string code)
{
this->code = code;
return this->code;
}
_Value set_val(_Value val)
{
this->val = val;
return this->val;
}
tree_node<_Value> *set_par(tree_node<_Value> *par)
{
this->par = par;
return this->par;
}
vector<tree_node<_Value> *> &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()
{
while (!repair())
;
return kid.front() == this;
}
bool is_root_node()
{
while (!repair())
;
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 vector<tree_node<_Value> *>::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 _Hash = hash<_Value>,
// typename _Pred = equal_to<_Value>,
typename _Alloc = allocator<tree_node<_Value>>>
class tree
{
private:
tree_node<_Value> *rot;
size_t node_amount;
_Alloc alloc;
vector<pair<tree_node<_Value> *, size_t>> 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(), vector<tree_node<_Value> *> kid = {}, string code = "0:root")
: rot(alloc.allocate(1)), node_amount(1)
{
dynamicT_n.push_back({rot, 1});
alloc.construct(rot, val, rot, kid, 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(tree_node<_Value> *t_n, vector<tree_node<_Value> *> kid = {}) : rot(t_n), node_amount(1)
{
rot->set_par(t_n);
rot->kid_list() = kid.empty() ? vector<tree_node<_Value> *>{t_n} : kid;
}
tree(tree_node<_Value> *t_n, _Value val, vector<tree_node<_Value> *> kid = {})
: rot(t_n), node_amount(1)
{
rot->set_val(val);
rot->set_par(t_n);
rot->kid_list() = kid.empty() ? vector<tree_node<_Value> *>{t_n} : kid;
}
tree(tree_node<_Value> *t_n, vector<tree_node<_Value> *> kid, string code) : rot(t_n), node_amount(1)
{
rot->set_par(t_n);
rot->kid_list() = kid;
rot->set_code(code);
}
tree(tree_node<_Value> *t_n, _Value val, vector<tree_node<_Value> *> 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 vector<pair<tree_node<_Value> *, size_t>>::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.
*/
tree_node<_Value> *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.
*/
tree_node<_Value> *at(size_t dep, size_t ord)
{
queue<tree_node<_Value> *> que;
que.push(rot);
while (dep-- > 0)
{
size_t i = que.size();
while (que.size() - i <= ord && i > 0)
{
vector<tree_node<_Value> *> kid = que.front()->get_kid_list();
que.pop();
i--;
for (typename vector<tree_node<_Value> *>::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;
cout << '*' << que.size() << '\n';
}
return que.size() <= ord ? nullptr : que.back();
}
typename vector<tree_node<_Value> *>::iterator insert_kid(tree_node<_Value> *par,
tree_node<_Value> *t_n,
size_t index = 0xffffffffffffffffULL)
{
// parKid: A reference to a %vector of child nodes of a parent node.
vector<tree_node<_Value> *> &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;
}
tree_node<_Value> *emplace_kid(tree_node<_Value> *par,
_Value val = _Value(),
vector<tree_node<_Value> *> 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.
vector<tree_node<_Value> *> &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.
tree_node<_Value> *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, val, par, kid, 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.
vector<tree_node<_Value> *> &parKid = par->kid_list();
if (par->is_leaf_node())
parKid.clear();
// Construct the new tree node.
for (typename vector<tree_node<_Value> *>::iterator it = parKid.begin(); it != parKid.end(); it++)
extra_kid.push_back(*it);
alloc.construct(ptr, val, par, extra_kid, code);
// Set the parent nodes of the extra kid nodes and the kid nodes of par to the new tree node.
for (typename vector<tree_node<_Value> *>::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.
*/
tree_node<_Value> *insert_below(tree_node<_Value> *t_n,
tree_node<_Value> *par,
vector<tree_node<_Value> *> 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.
vector<tree_node<_Value> *> &parKid = par->kid_list();
if (par->is_leaf_node())
parKid.clear();
// Assign t_n
for (typename vector<tree_node<_Value> *>::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 vector<tree_node<_Value> *>::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.
*/
tree_node<_Value> *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<tree_node<_Value> *, size_t>> sta;
sta.push({rot, 0});
while (!sta.empty())
{
tree_node<_Value> *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;
vector<tree_node<_Value> *> 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<tree_node<_Value> *> que;
que.push(rot);
while (!que.empty())
{
vector<tree_node<_Value> *> kid = que.front()->get_kid_list();
if (r__)
reverse(kid.begin(), kid.end());
for (typename vector<tree_node<_Value> *>::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;
}
};
}后面没啥了。
