实现了tree数据结构
但半成品（悲
只实现了一点吧，然后tree<(自己看)>::find()没完全写好，也没测试
(谁要是帮我测试了并告诉我，我会很开心的qwq)
对了，那个memory（头文件）中的allocator总感觉不对呢……？
悄悄地告诉你：析构函数绝对有问题，好像内存泄漏了(但找不到问题啊啊啊!!)
好了，下面是源代码：
#include <functional>
#include <initializer_list>
#include <iterator>
#include <memory>
#include <queue>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>
#include <iostream>
namespace std
{
template <typename _Value>
class tree_node
{
private:
string code;
_Value val;
tree_node<_Value> *par;
unordered_set<tree_node<_Value> *> kid;
bool kid_is_unusable()
{
return kid.empty();
}
bool par_is_unusable()
{
return par == nullptr;
}
public:
tree_node(_Value val = _Value(),
tree_node<_Value> *par = nullptr,
unordered_set<tree_node<_Value> *> kid = unordered_set<tree_node<_Value> *>(),
string code = string())
: code(code),
val(val),
par(par != nullptr ? par : this),
kid(kid.empty() ? unordered_set<tree_node<_Value> *>{this} : kid) {}
~tree_node()
{
if (par != this && !par_is_unusable())
par->kid_list().erase(par->kid_list().find(this));
if (*(kid.begin()) != this)
for (typename unordered_set<tree_node<_Value> *>::iterator it = kid.begin(); it != kid.end(); it++)
(*it)->set_par(nullptr);
}
string get_code()
{
return code;
}
_Value get_val()
{
return val;
}
tree_node<_Value> *get_par()
{
return par;
}
void set_code(string code)
{
this->code = code;
}
void set_val(_Value val)
{
this->val = val;
}
void set_par(tree_node<_Value> *par)
{
this->par = par;
}
unordered_set<tree_node<_Value> *> &kid_list()
{
return kid;
}
bool is_usable()
{
return !(par_is_unusable() && kid_is_unusable());
}
bool repair()
{
if (par_is_unusable())
par = this;
if (kid_is_unusable())
kid = unordered_set<tree_node<_Value> *>{this};
return is_usable();
}
};
enum tree_sequence
{
preorder = 0,
postorder = 2,
levorder
};
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> *, int>> dynamicT_n;
public:
/**
* @brief Creates a %tree with a root node.
* @param val The value of the root node.
* @param kid A %unordered_set 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(),
unordered_set<tree_node<_Value> *> kid = unordered_set<tree_node<_Value> *>(),
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 %unordered_set 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,
unordered_set<tree_node<_Value> *> kid = unordered_set<tree_node<_Value> *>(),
string code = "")
: rot(t_n), node_amount(1)
{
rot->set_par(t_n);
if (!kid.empty())
rot->kid_list() = kid;
if (!code.empty())
rot->set_code(code);
}
tree(tree_node<_Value> *t_n,
_Value val,
unordered_set<tree_node<_Value> *> kid = unordered_set<tree_node<_Value> *>(),
string code = "")
: rot(t_n), node_amount(1)
{
rot->set_val(val);
rot->set_par(t_n);
rot->kid_list() = kid.empty() ? unordered_set<tree_node<_Value> *>{t_n} : kid;
if (!code.empty())
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> *, int>>::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.~vector<pair<tree_node<_Value> *, int>>();
}
/**
* @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 Insert a new tree node into a %tree.
* @param par A pointer to the parent node of the new tree node.
* @param extra_kid An %unordered_set including pointers to extra kid 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 an element under the given parent %tree_node and assign the given data to it.
* If successful it returns a pointer to the new tree node.
* If unsuccessful it returns nullptr.
*/
tree_node<_Value> *insert(tree_node<_Value> *par,
unordered_set<tree_node<_Value> *> extra_kid = unordered_set<tree_node<_Value> *>(),
_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 the parent node is also the leave node
typename unordered_set<tree_node<_Value> *>::iterator parSelf = par->kid_list().find(par);
if (parSelf != par->kid_list().end())
par->kid_list().erase(parSelf);
// Construct the new tree node
extra_kid.insert(par->kid_list().begin(), par->kid_list().end());
alloc.construct(ptr, val, par, extra_kid, code);
// Set the parent nodes of the extra kid nodes and the kid nodes of the parent node to the new tree node
for (typename unordered_set<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 the parent node
par->kid_list().clear();
par->kid_list().insert(ptr);
// Return the pointer to the new node
return ptr;
}
tree_node<_Value> *insert(tree_node<_Value> *t_n,
tree_node<_Value> *par,
unordered_set<tree_node<_Value> *> extra_kid = unordered_set<tree_node<_Value> *>(),
bool use_val = false,
_Value val = _Value(),
bool use_code = false,
string code = string())
{
// Check if the parent node is also the leave node
typename unordered_set<tree_node<_Value> *>::iterator parSelf = par->kid_list().find(par);
if (parSelf != par->kid_list().end())
par->kid_list().erase(parSelf);
// Construct the new tree node
extra_kid.insert(par->kid_list().begin(), par->kid_list().end());
t_n->kid_list() = extra_kid;
if (use_val)
t_n->set_val(val);
if (use_code)
t_n->set_code(code);
// Set the parent nodes of the extra kid nodes and the kid nodes of the parent node to the new tree node
for (typename unordered_set<tree_node<_Value> *>::iterator it = extra_kid.begin();
it != extra_kid.end();
it++)
(*it)->set_par(t_n);
// Set the new node to the kid node of the parent node
par->kid_list().clear();
par->kid_list().insert(t_n);
// Return the pointer to the new node
return t_n;
}
tree_node<_Value> *find(_Value x, tree_sequence order = preorder, bool is_code = false)
{
if (x == rot.get_val())
return rot;
switch (order)
{
case levorder:
queue<tree_node<_Value> *> que;
que.push(rot);
while (!que.empty())
{
unordered_set<tree_node<_Value> *> kid = que.front()->kid_list();
for (typename unordered_set<tree_node<_Value> *>::iterator it = kid.begin();
it != kid.end();
it++)
{
if (is_code)
{
if ((*it)->get_val() == x)
return *it;
}
else if ((*it)->get_code() == x)
return *it;
if ((*it)->kid_list().size() > 1 ||
(*(*it)->kid_list().begin())->get_code() != (*it)->get_code())
que.push(*it);
}
}
break;
case preorder:
case postorder:
stack<tree_node<_Value> *> sta;
***;
}
return nullptr;
}
};
}.
.
.
.
.
其实注释不太好