昆山网站设计哪家好,wordpress图片放大镜,贵阳做网站的,广州网页设计公司C数据结构与算法实现#xff08;目录#xff09;
答案在此#xff1a;二叉查找树#xff08;binary search tree#xff09;#xff08;答案#xff09;
写在前面
部分内容参《算法导论》
基本接口实现
1 删除
删除值为value的第一个节点 删除叶子节点1 删除叶子节…C数据结构与算法实现目录
答案在此二叉查找树binary search tree答案
写在前面
部分内容参《算法导论》
基本接口实现
1 删除
删除值为value的第一个节点 删除叶子节点1 删除叶子节点1 3删除叶子节点1 删除有两个孩子的节点z 分成下面几个步骤进行
1 找到z的后继y是z的后继。这时候可以确定y是不可能有左孩子的。
2 删除y让y的右孩子x取代自己的位置。删除只有一个孩子的节点上面已经讨论过。
3 让y的值覆盖z的值。 待实现代码
#pragma once
#include algorithm
#include list
#include iostream
#include stack
#include queue
#include cstdlib
#include ctime
#include string
#include cassert
#include map
#include sstream
using namespace std;//------下面的代码是用来测试你的代码有没有问题的辅助代码你无需关注------
#include algorithm
#include cstdlib
#include iostream
#include vector
#include utility
using namespace std;
struct Record { Record(void* ptr1, size_t count1, const char* location1, int line1, bool is) :ptr(ptr1), count(count1), line(line1), is_array(is) { int i 0; while ((location[i] location1[i]) i 100) { i; } }void* ptr; size_t count; char location[100] { 0 }; int line; bool is_array false; bool not_use_right_delete false; }; bool operator(const Record lhs, const Record rhs) { return lhs.ptr rhs.ptr; }std::vectorRecord myAllocStatistic; void* newFunctionImpl(std::size_t sz, char const* file, int line, bool is) { void* ptr std::malloc(sz); myAllocStatistic.push_back({ ptr,sz, file, line , is }); return ptr; }void* operator new(std::size_t sz, char const* file, int line) { return newFunctionImpl(sz, file, line, false); }void* operator new [](std::size_t sz, char const* file, int line)
{return newFunctionImpl(sz, file, line, true);
}void operator delete(void* ptr) noexcept { Record item{ ptr, 0, , 0, false }; auto itr std::find(myAllocStatistic.begin(), myAllocStatistic.end(), item); if (itr ! myAllocStatistic.end()) { auto ind std::distance(myAllocStatistic.begin(), itr); myAllocStatistic[ind].ptr nullptr; if (itr-is_array) { myAllocStatistic[ind].not_use_right_delete true; } else { myAllocStatistic[ind].count 0; }std::free(ptr); } }void operator delete[](void* ptr) noexcept { Record item{ ptr, 0, , 0, true }; auto itr std::find(myAllocStatistic.begin(), myAllocStatistic.end(), item); if (itr ! myAllocStatistic.end()) { auto ind std::distance(myAllocStatistic.begin(), itr); myAllocStatistic[ind].ptr nullptr; if (!itr-is_array) { myAllocStatistic[ind].not_use_right_delete true; } else { myAllocStatistic[ind].count 0; }std::free(ptr); } }
#define new new(__FILE__, __LINE__)
struct MyStruct { void ReportMemoryLeak() { std::cout Memory leak report: std::endl; bool leak false; for (auto i : myAllocStatistic) { if (i.count ! 0) { leak true; std::cout leak count i.count Byte , file i.location , line i.line; if (i.not_use_right_delete) { cout , not use right delete. ; } cout std::endl; } }if (!leak) { cout No memory leak. endl; } }~MyStruct() { ReportMemoryLeak(); } }; static MyStruct my; void check_do(bool b, int line __LINE__) { if (b) { cout line: line Pass endl; } else { cout line: line Ohh! not passed!!!!!!!!!!!!!!!!!!!!!!!!!!! endl; exit(0); } }
#define check(msg) check_do(msg, __LINE__);
//------上面的代码是用来测试你的代码有没有问题的辅助代码你无需关注------templatetypename T
class binary_search_tree
{
private:struct tree_node//OK{tree_node() :data(T()){}tree_node(const T t) :data(t){}bool exist_parent(void) const { return parent ! nullptr; }T data;tree_node* parent nullptr;tree_node* left nullptr;tree_node* right nullptr;};
public:binary_search_tree(void) :m_root(nullptr) {}//默认构造函数什么也不需要做因为成员定义的时候就已经初始化了binary_search_tree(const T*, const int);//从数组构造一颗二叉树binary_search_tree(const binary_search_tree);//拷贝构造函数binary_search_tree operator (const binary_search_tree);~binary_search_tree(void) { clear(); }//析构函数
public:int size(void) const;//元素数量bool empty(void) const { return size() 0; }//二叉树是否为空bool insert(const T data);//插入一个元素T minmum(void) const;//最小值T maxmum(void) const;//最大值bool exists(const T data) const;//判断元素是否存在void clear(void);//非递归清空二叉树void erase(const T data);templatetypename Tfriend ostream operator(ostream out, const binary_search_treeT tree);//输出二叉树void print_pre_order_nonrecursive(void) const;//非递归:先序遍历输出二叉树void print_in_order_nonrecursive(void) const;//非递归:中序遍历输出二叉树void print_post_order_nonrecursive(void) const;//非递归:后续遍历输出二叉树void print_in_order_recursive(std::ostream os) const;//递归中序遍历输出二叉树void print_element_order(void) const;//非递归按元素顺序输出二叉树std::string to_string_in_order(void) const;int max_length_between_node(void) const;//最大节点距离int hight(void) const;//树高度bool operator(const binary_search_tree other) const;//两个树相等结构相同对应元素相同bool operator!(const binary_search_tree other) const { return !equal(other); }//两个树不相等bool equal(const binary_search_tree other) const;//两个树相等结构相同对应元素相同
private:void print_binary_tree(ostream, const tree_node* bt, int depth) const;//二叉树形式打印二叉树tree_node* find(const T data);//查找tree_node* maxmum(tree_node*) const;//最大节点tree_node* minmum(tree_node*) const;//最小节点tree_node* successor(tree_node* t) const;//后继节点//节点的深度与高度对于树中相同深度的每个结点来说它们的高度不一定相同这取决于每个结点下面的叶结点的深度int hight(const tree_node* _t) const;bool equal(const tree_node* lhs, const tree_node* rhs) const;//两个树相等结构相同对应元素相同bool is_node_leaf(const tree_node* node) const;bool is_left_child(const tree_node* parent, const tree_node* node);bool is_leaf_node_equal(const tree_node* lhs, const tree_node* rhs) const;void copy(const binary_search_tree other);void copy_node_from(tree_node* dest, tree_node* dest_parent, const tree_node* from);void print_in_order_recursive(std::ostream os, const tree_node* node) const;//递归中序遍历输出二叉树void erase_node(tree_node* pnode);//参数是引用类型主要是为了erase_node(m_root) 时更新m_root;void erase_and_reconnect(tree_node* pnode, tree_node* pnode_child);void update_parent(tree_node* pnode);//删除叶子结点后让父节点指向空指针
private:tree_node* left(tree_node* p){assert(p ! nullptr);return p-left;}
private:tree_node* m_root nullptr;//OKint m_size 0;
};
templatetypename T
std::string binary_search_treeT::to_string_in_order(void) const
{std::stringstream oss;this-print_in_order_recursive(oss);auto str oss.str();return str;
}
templatetypename T
binary_search_treeT::binary_search_tree(const T* arr, const int length) : binary_search_tree()
{//(4) your code //可以使用成员函数insert(const T data) 来实现这个函数
}
templatetypename T
inline binary_search_treeT::binary_search_tree(const binary_search_tree from) :m_root(nullptr)
{//(5) your code //可以使用成员函数copy来实现
}
templatetypename T
binary_search_treeT binary_search_treeT::operator(const binary_search_tree from)
{//(5) your code //可以使用成员函数copy来实现。//从这里可以看出copy函数应该先用clear成员函数清空自己原有的全部节点return *this;
}
templatetypename T
void binary_search_treeT::copy(const binary_search_tree other)
{if (this other)//如果拷贝自己则什么也不做{return;//直接返回}clear();//先清空自己的内容m_size other.m_size;//成员变量赋值if (other.m_root)//从根节点开始拷贝递归的拷贝二叉树的每一个节点照葫芦画瓢{copy_node_from(m_root/*需要被创建的节点*/, nullptr/*需要被创建的节点的父节点用户指向孩子*/, other.m_root/*提供节点存储的数据*/);}
}
templatetypename T
bool binary_search_treeT::insert(const T data)
{if (m_root ! nullptr){tree_node *fast, *slow, *ptemp;fast slow ptemp m_root;while (fast ! 0){slow fast;if (data slow-data){fast slow-left;}else if (data slow-data){fast slow-right;}else//esle equal do nothing 元素不允许重复//元素如果已经存在什么也不做{fast 0;return false;//直接退出不再插入相同的元素的}}if (data slow-data){slow-left new tree_node(data);slow-left-parent slow;}else if (data slow-data){slow-right new tree_node(data);slow-right-parent slow;}else{return false;}//esle equal do nothing}else{m_root new tree_node(data);}m_size;return true;
}
templatetypename T
int binary_search_treeT::hight(void) const
{return hight(m_root);
}
templatetypename T
int binary_search_treeT::hight(const tree_node* _t) const
{//树的高度也是树的层树最大层的层数就是树的高度//(7) your code 如果没有元素返回0// 如果只有一个根节点没有孩子节点高度为1// 如果有孩子节点树的高度就 1 孩子节点的高度左右子树高度较大的那一个return -1;
}
templatetypename T
bool binary_search_treeT::operator(const binary_search_tree other) const
{return this-equal(other);//两个二叉树相等当且仅当两颗树长的一模一样
}
templatetypename T
bool binary_search_treeT::equal(const binary_search_tree other) const
{return equal(m_root, other.m_root);
}
templatetypename T
bool binary_search_treeT::equal(const tree_node* lhs, const tree_node* rhs) const
{// 先判断两个树是否为空//再判断两个树是否都是叶子节点 可以使用 is_leaf_node_equal 成员函数//再判断两个树的两个左右子树是否同时相等 可以递归调用当前equal函数//(8) your codereturn false;
}
templatetypename T
inline bool binary_search_treeT::is_leaf_node_equal(const tree_node* lhs, const tree_node* rhs) const
{if (is_node_leaf(lhs) is_node_leaf(rhs)){return lhs-data rhs-data;}return false;
}
templatetypename T
inline bool binary_search_treeT::is_node_leaf(const tree_node * node) const
{return node ! nullptr node-left nullptr node-right nullptr;
}templatetypename T
///*需要被创建的节点*/, nullptr/*需要被创建的节点*/, other.m_root/*提供节点存储的数据*/
void binary_search_treeT::copy_node_from(tree_node * dest, tree_node* dest_parent, const tree_node * from)
{//(9) your code 深度拷贝from节点并切递归拷贝从而完成整棵树的拷贝//注意dest节点传递的是引用这意味着你可以非常方便的对这个地址变量赋值赋值就会修改传进来的外部变量//改函数使用递归调用自己的方式完成整棵树的拷贝。注意对左子树和又子树可能需要分别调用一次递归函数才能完成。}templatetypename T
int binary_search_treeT::max_length_between_node(void) const
{int max_length 0;const tree_node* ptree m_root;listtree_node* listNode;listNode.push_back(m_root);while (!listNode.empty()){auto pnode listNode.front();listNode.pop_front();if (pnode-left ! nullptr){listNode.push_back(pnode-left);}if (pnode-right ! nullptr){listNode.push_back(pnode-right);}int tempBetween hight(pnode-left) hight(pnode-right);max_length std::maxint(tempBetween, max_length);}return max_length;
}
templatetypename T
void binary_search_treeT::clear(void)
{//使用一个辅助队列(或者栈)层次遍历删除所有节点。//遍历到一个节点A就把孩子BC放到队列并把这个节点A从队列里取出释放//(10) your code}
templatetypename T
void binary_search_treeT::print_binary_tree(ostream out, const tree_node* bt, int depth) const
{//用右左孩子的方式输出一颗树,先输出右孩子后输出左孩子if (bt){print_binary_tree(out, bt-right, depth 1);if (depth 0){out bt-data endl;}else if (depth 1){out -- bt-data endl;}else{int n depth;while (--n){cout ;}out -- bt-data endl;}print_binary_tree(out, bt-left, depth 1);}
}
templatetypename T
void binary_search_treeT::print_in_order_nonrecursive(void) const
{cout print_in_order_nonrecursive : ;stacktree_node* tempstack;tree_node* t m_root;if (t ! NULL){do{tempstack.push(t);t t-left;} while (t ! NULL);}while (!tempstack.empty()){tree_node* p tempstack.top();cout p-data ;tempstack.pop();if (p-right ! NULL){p p-right;do{tempstack.push(p);p p-left;} while (p ! NULL);}}cout endl;
}
templatetypename T
inline void binary_search_treeT::print_in_order_recursive(std::ostream os) const
{print_in_order_recursive(os, m_root);
}
templatetypename T
void binary_search_treeT::print_in_order_recursive(std::ostream os, const tree_node * node) const
{if (node nullptr){return;}print_in_order_recursive(os, node-left);os node-data ;print_in_order_recursive(os, node-right);
}
templatetypename T
ostream operator(ostream out, const binary_search_treeT tree)
{tree.print_binary_tree(out, tree.m_root, 0);return out;
}
templatetypename T
void binary_search_treeT::print_post_order_nonrecursive(void) const
{//后续序序遍历输出一颗树的全部结点值2,3,1//广度优先遍历cout print_post_order_nonrecursive : ;typedef pairtree_node*, bool multinode;stackmultinode tempstack;if (m_root){tempstack.push(make_pair(m_root, false));}while (!tempstack.empty()){multinode m tempstack.top(); tempstack.pop();if (m.first-left NULL m.first-right NULL){//叶子节点直接输出cout m.first-data ;}else if (m.second true){//所有孩子都遍历完了才会到这一步cout m.first-data ;}else{//非终结点并且孩子还没遍历完。m.second true; tempstack.push(m);if (m.first-right ! NULL){tempstack.push(make_pair(m.first-right, false));}if (m.first-left ! NULL){tempstack.push(make_pair(m.first-left, false));}}}cout endl;
}
templatetypename T
void binary_search_treeT::print_pre_order_nonrecursive(void) const
{//先序遍历输出一颗树的全部结点值1,2,3,先根遍历cout print_pre_order_nonrecursive : ;stacktree_node* node_stack;if (m_root){node_stack.push(m_root);tree_node* t;while (!node_stack.empty()){t node_stack.top();node_stack.pop();cout t-data ;if (t-right ! 0){node_stack.push(t-right);}if (t-left ! 0){node_stack.push(t-left);}}cout endl;}
}
templatetypename T
bool binary_search_treeT::exists(const T data) const
{bool result false;if (m_root){tree_node* pfind m_root;while (pfind){if (pfind-data data){result true;break;}else if (data pfind-data){pfind pfind-left;}elsepfind pfind-right;}}return result;
}
templatetypename T
typename binary_search_treeT::tree_node* binary_search_treeT::find(const T data)
{//(11) your code 利用find非递归实现查找某个值是否存在于树中return nullptr;
}templatetypename T
int binary_search_treeT::size(void) const
{return m_size;
}
templatetypename T
T binary_search_treeT::minmum(void) const
{//(12) your code 返回最小值 请使用成员函数 minmum(tree_node* p) const 来实现return T();
}
templatetypename T
typename binary_search_treeT::tree_node* binary_search_treeT::minmum(tree_node* p) const
{//(13) your code 返回最小值非递归实现return nullptr;
}
templatetypename T
T binary_search_treeT::maxmum(void) const
{//(14) your code 返回最大值 请使用成员函数 maxmum(tree_node* p) const 来实现return T();
}
templatetypename T
typename binary_search_treeT::tree_node* binary_search_treeT::maxmum(tree_node* t) const
{//(14) your code 返回最大值非递归实现return nullptr;
}
templatetypename T
typename binary_search_treeT::tree_node* binary_search_treeT::successor(tree_node* t) const
{//(15) your code 找到一个节点的后继结点这个函数是顺序迭代遍历二叉树的关键函数。//具体思路为如果这个节点有右子树那么右子树的minmum节点就是后继结点。//如果这个节点没有右子树比该节点大的值一定是往右上方去的第一个节点。//参考《算法导论》return nullptr;
}
templatetypename T
void binary_search_treeT::print_element_order(void) const
{cout print_element_order by order: ;if (!empty()){//(16) your code 使用后继节点成员函数作为顺序迭代的依据实现顺序遍历一颗二次函数。//循环获取后继只要有后继就输出这个后继。cout endl;}
}templatetypename T
void binary_search_treeT::erase(const T data)
{tree_node* itr find(data);assert(itr ! nullptr);--m_size;if (itr m_root){/*删除根节点可能需要释放根节点本身这个时候m_root的指向需要更新。* 所以erase_node的参数是引用类型希望可以在erase_node内部对m_root重新* 赋值来打到更新根节点指向的目的。*/erase_node(m_root);return;}else{erase_node(itr);}
}
templatetypename T
void binary_search_treeT::erase_node(tree_node* pnode)
{//pnode如果没有parent那么它就是root这个时候删除pnode// 无需考虑pnode的parent需要更新的问题。//只需要处理其孩子替代自己的问题if (pnode-left nullptr pnode-right nullptr){//叶子结点被删除了的话被删除节点的父亲应该指向空指针。update_parent(pnode);//内部会先判断pnode有没有parentdelete pnode;//这里会更新传进来的引用参数比如如果传进来的是m_root的话。pnode nullptr;//如果pnode是m_root的话这句话就会变得必不可少更新m_root}//如果被删除的节点p只有左孩子让p的左孩子p_left_child取代自己作为p的parent节点的做孩子else if (pnode-left ! nullptr pnode-right nullptr){//让pnode的父亲节点和pnode的孩子建立连接erase_and_reconnect(pnode, pnode-left);}//如果只有右孩子让右孩子取代自己else if (pnode-left nullptr pnode-right ! nullptr){//让pnode的父亲节点和pnode的孩子建立连接erase_and_reconnect(pnode, pnode-right);}else{//https://zhuanlan.zhihu.com/p/640863892//分成下面几个步骤进行//1 找到z的后继y是z的后继。这时候可以确定y是不可能有左孩子的。//2 删除y让y的右孩子x取代自己的位置。删除只有一个孩子的节点上面已经讨论过。//3 让y的值覆盖z的值。tree_node* psuccessor successor(pnode);pnode-data psuccessor-data;//3 让y的值覆盖z的值。//2 删除y, y只有一个孩子只有一个孩子的节点删除此函数的开始部分已经实现了。只需要调用此函数即可。//(17) your code}
}
templatetypename T
void binary_search_treeT::update_parent(tree_node* pnode)
{//删除叶子结点后让父节点指向空指针if (pnode-parent){auto parent pnode-parent;is_left_child(parent, pnode) ? (parent-left nullptr) : (parent-right nullptr);}
}
templatetypename T
void binary_search_treeT::erase_and_reconnect(tree_node* delete_pnode, tree_node* pnode_child)
{//让左孩子取代自己同时考虑parent不存在的情况下取代自己。if (delete_pnode-exist_parent()){//拿到父节点auto parent delete_pnode-parent;auto is_left is_left_child(parent, delete_pnode);//先备份地址将来用于释放内存auto pbackup delete_pnode;//指向新节点自己的左孩子替代自己// reconnect1 -delete_pnode pnode_child;// - reconnect2 pnode_child-parent parent;//指向新的父亲//删除自己原来的内存delete pbackup;//父节点和自己的左孩子建立连接is_left ? parent-left delete_pnode : parent-right delete_pnode;}else //删除根节点 删除根节点可不是删除整个树哦{//先备份地址将来用于释放内存auto pbackup delete_pnode;//指向新节点自己的左孩子替代自己delete_pnode pnode_child;//删除自己原来的内存delete pbackup;}
}
templatetypename T
bool binary_search_treeT::is_left_child(const tree_node* parent, const tree_node* pnode)
{assert(parent ! nullptr);assert(pnode ! nullptr);return (parent-left pnode);
}void test_tree(const binary_search_treeint _tree)
{cout test_tree:\n;cout _tree;cout tree size : _tree.size() endl;cout tree max length between node _tree.max_length_between_node() endl;_tree.print_in_order_nonrecursive();_tree.print_element_order();_tree.print_post_order_nonrecursive();_tree.print_pre_order_nonrecursive();cout min element : _tree.minmum() endl;cout max element : _tree.maxmum() \n endl;
}
void test1()
{binary_search_treeint tree;check(tree.size() 0);check(tree.empty());check(tree.hight() 0);
}
void test2()
{int arr[1] { 1 };binary_search_treeint tree(arr, 1);check(tree.size() 1);check(tree.to_string_in_order() 1 );check(!tree.empty());
}
void test3()
{int arr[2] { 1, 2 };binary_search_treeint tree(arr, 2);check(tree.size() 2);check(tree.to_string_in_order() 1 2 );check(!tree.empty());
}
void test4()
{int arr[2] { 2, 1 };binary_search_treeint tree(arr, 2);check(tree.size() 2);check(tree.to_string_in_order() 1 2 );check(!tree.empty());
}
void test5()
{constexpr int length 3;int arr[length] { 1, 2, 3 };binary_search_treeint tree(arr, length);check(tree.size() length);check(tree.to_string_in_order() 1 2 3 );check(!tree.empty());
}
void test6()
{constexpr int length 3;int arr[length] { 2, 1, 3 };binary_search_treeint tree(arr, length);check(tree.size() length);check(tree.to_string_in_order() 1 2 3 );check(!tree.empty());
}
void test7()
{constexpr int length 3;int arr[length] { 3, 2, 1, };binary_search_treeint tree(arr, length);check(tree.size() length);check(tree.to_string_in_order() 1 2 3 );check(!tree.empty());
}
void test8()
{constexpr int length 3;int arr[length] { 3, 1, 2, };binary_search_treeint tree(arr, length);check(tree.size() length);check(tree.to_string_in_order() 1 2 3 );check(!tree.empty());
}
void test9()
{constexpr int length 10;int arr[length] { 1,3,5,7,9,2,4,6,8,10 };binary_search_treeint tree(arr, length);check(tree.size() length);check(tree.to_string_in_order() 1 2 3 4 5 6 7 8 9 10 );check(!tree.empty());
}
void test10()
{constexpr int length 10;int arr[length] { 2,4,6,8,10,1,3,5,7,9 };binary_search_treeint tree(arr, length);check(tree.size() length);check(tree.to_string_in_order() 1 2 3 4 5 6 7 8 9 10 );check(!tree.empty());
}
void test11()
{constexpr int length 10;int arr[length] { 10,9,8,7,6,5,4,3,2,1 };binary_search_treeint tree(arr, length);check(tree.size() length);check(tree.to_string_in_order() 1 2 3 4 5 6 7 8 9 10 );check(!tree.empty());check(tree.hight() 10);
}
void test12()
{constexpr int length 10;int arr[length] { 5,4,3,2,1,10,9,8,7,6 };binary_search_treeint tree(arr, length);check(tree.size() length);check(tree.to_string_in_order() 1 2 3 4 5 6 7 8 9 10 );check(!tree.empty());check(tree.hight() 6);
}
void test13()
{constexpr int length 1;int arr[length] { 1 };binary_search_treeint tree(arr, length);check(tree.minmum() 1);check(tree.maxmum() 1);check(tree.hight() 1);
}
void test14()
{constexpr int length 2;int arr[length] { 1, 2 };binary_search_treeint tree(arr, length);check(tree.minmum() 1);check(tree.maxmum() 2);check(tree.hight() 2);
}
void test15()
{constexpr int length 10;int arr[length] { 5,4,3,2,1,10,9,8,7,6 };binary_search_treeint tree(arr, length);check(tree.minmum() 1);check(tree.maxmum() 10);
}
void test16()
{constexpr int length 1;int arr[length] { 1 };binary_search_treeint tree(arr, length);check(tree.exists(1));tree.erase(1);check(!tree.exists(1));check(tree.size() 0);
}
void test17()
{int arr[] { 3,2,1 };binary_search_treeint tree(arr, sizeof(arr) / sizeof(int));check(tree.exists(1));cout tree endl;tree.erase(2);cout tree endl;check(!tree.exists(2));check(tree.size() 2);check(!tree.empty());check(tree.to_string_in_order() 1 3 );
}
void test18()
{constexpr int length 2;int arr[length] { 1, 2 };binary_search_treeint tree(arr, length);check(tree.exists(1));check(tree.exists(2));tree.erase(1);check(!tree.exists(1));check(tree.exists(2));tree.clear();check(tree.empty());check(tree.size() 0);check(!tree.exists(2));
}
void test19()
{constexpr int length 10;int arr[length] { 5,3,4,1,2,10,8,9,7,6 };binary_search_treeint tree(arr, length);cout tree endl ------------------- endl;tree.erase(1);cout tree endl ------------------- endl;check(tree.to_string_in_order() 2 3 4 5 6 7 8 9 10 );tree.erase(2);cout tree endl ------------------- endl;check(tree.to_string_in_order() 3 4 5 6 7 8 9 10 );tree.erase(3);check(tree.to_string_in_order() 4 5 6 7 8 9 10 );cout tree endl ------------------- endl;tree.erase(4);cout tree endl ------------------- endl;check(tree.to_string_in_order() 5 6 7 8 9 10 );tree.erase(5);cout tree endl ------------------- endl;check(tree.to_string_in_order() 6 7 8 9 10 );tree.erase(6);cout tree endl ------------------- endl;check(tree.to_string_in_order() 7 8 9 10 );tree.erase(7);cout tree endl ------------------- endl;check(tree.to_string_in_order() 8 9 10 );tree.erase(8);cout tree endl ------------------- endl;check(tree.to_string_in_order() 9 10 );tree.erase(9);cout tree endl ------------------- endl;check(tree.to_string_in_order() 10 );tree.erase(10);cout tree endl ------------------- endl;check(tree.to_string_in_order() );
}
void test20()
{constexpr int length 10;int arr[length] { 5,3,4,1,2,10,8,9,7,6 };binary_search_treeint tree(arr, length);cout tree endl ------------------- endl;tree.erase(10);cout tree endl ------------------- endl;check(tree.to_string_in_order() 1 2 3 4 5 6 7 8 9 );tree.erase(8);cout tree endl ------------------- endl;check(tree.to_string_in_order() 1 2 3 4 5 6 7 9 );
}
void test21()
{constexpr int length 10;int arr[length] { 5,3,4,1,2,10,8,9,7,6 };binary_search_treeint tree(arr, length);cout tree endl ------------------- endl;tree.erase(5);cout tree endl ------------------- endl;check(tree.to_string_in_order() 1 2 3 4 6 7 8 9 10 );
}
void test22()
{constexpr int length 10;int arr[length] { 2,4,6,8,10,1,3,5,7,9 };binary_search_treeint tree(arr, length);check(tree.hight() 6);tree.erase(1);check(!tree.exists(1));tree.erase(2);check(!tree.exists(2));tree.erase(3);check(!tree.exists(3));tree.erase(4);check(!tree.exists(4));tree.erase(5);check(!tree.exists(5));check(tree.to_string_in_order() 6 7 8 9 10 );tree.erase(6);check(!tree.exists(6));tree.erase(7);check(!tree.exists(7));tree.erase(8);check(!tree.exists(8));tree.erase(9);check(!tree.exists(9));tree.erase(10);check(!tree.exists(10));check(tree.empty());
}
void test23()
{//test equalint a[3] { 15, 12, 14 };binary_search_treeint tree(a, 3);check(tree.hight() 3);cout tree:\n tree endl;auto tree2 tree;cout tree2:\n tree2 endl;check(tree2.equal(tree));
}
void test24(binary_search_treeint tree)
{cout tree:\n tree endl;auto tree2 tree;cout tree2:\n tree2 endl;check(tree2.equal(tree));check(tree2 tree);tree.clear();cout tree endl;check(tree2.equal(tree) false);check(tree2 ! tree);
}
void test25()
{int a[3] { 15, 12, 14 };binary_search_treeint tree(a, 3);tree.print_in_order_recursive(cout);
}
int main()
{test1();//emptytest2();//test create insert empty sizetest3();test4();test5();test6();test7();test8();test9();test10();test11();test12();test13();test14();//minmum maxmumtest15();test16();//exists clear erase size emptytest17();//erasetest18();//erasetest19();//erasetest20();//erasetest21();//erasetest22();//erasetest23();int maxLength 0;int a[100] { 15, 12, 14, 13, 16, 34, 23, 24, 22, 21, 20, 19, 18, 17, 35, 36, 37, 38, 39, 40, 41, 0 };binary_search_treeint tree(a, 22);check(tree.size() 22);check(tree.empty() false);check(tree.maxmum() 41);check(tree.minmum() 0);test_tree(tree);binary_search_treeint tree1(a, 3);test_tree(tree1);test24(tree);//test copytest25();//printreturn 0;
}正确输出
line:725 Pass
line:726 Pass
line:727 Pass
line:733 Pass
line:734 Pass
line:735 Pass
line:741 Pass
line:742 Pass
line:743 Pass
line:749 Pass
line:750 Pass
line:751 Pass
line:758 Pass
line:759 Pass
line:760 Pass
line:767 Pass
line:768 Pass
line:769 Pass
line:776 Pass
line:777 Pass
line:778 Pass
line:785 Pass
line:786 Pass
line:787 Pass
line:794 Pass
line:796 Pass
line:797 Pass
line:804 Pass
line:806 Pass
line:807 Pass
line:814 Pass
line:816 Pass
line:817 Pass
line:818 Pass
line:825 Pass
line:827 Pass
line:828 Pass
line:829 Pass
line:836 Pass
line:837 Pass
line:838 Pass
line:845 Pass
line:846 Pass
line:847 Pass
line:854 Pass
line:855 Pass
line:862 Pass
line:864 Pass
line:865 Pass
line:871 Pass
3--2--13--1line:875 Pass
line:876 Pass
line:877 Pass
line:878 Pass
line:885 Pass
line:886 Pass
line:888 Pass
line:889 Pass
line:891 Pass
line:892 Pass
line:893 Pass--10--9--8--7--6
5--4--3--2--1---------------------10--9--8--7--6
5--4--3--2-------------------
line:903 Pass--10--9--8--7--6
5--4--3-------------------
line:906 Pass
line:908 Pass--10--9--8--7--6
5--4---------------------10--9--8--7--6
5-------------------
line:912 Pass
10--9--8--7--6-------------------
line:915 Pass
10--9--8--7-------------------
line:918 Pass
10--9--8-------------------
line:921 Pass
10--9-------------------
line:924 Pass
10-------------------
line:927 Pass-------------------
line:930 Pass--10--9--8--7--6
5--4--3--2--1---------------------9--8--7--6
5--4--3--2--1-------------------
line:940 Pass--9--7--6
5--4--3--2--1-------------------
line:943 Pass--10--9--8--7--6
5--4--3--2--1---------------------10--9--8--7
6--4--3--2--1-------------------
line:953 Pass
line:960 Pass
line:962 Pass
line:964 Pass
line:966 Pass
line:968 Pass
line:970 Pass
line:971 Pass
line:973 Pass
line:975 Pass
line:977 Pass
line:979 Pass
line:981 Pass
line:982 Pass
line:989 Pass
tree:
15--14--12tree2:
15--14--12line:993 Pass
line:1047 Pass
line:1048 Pass
line:1049 Pass
line:1050 Pass
test_tree:--41--40--39--38--37--36--35--34--24--23--22--21--20--19--18--17--16
15--14--13--12--0
tree size : 22
tree max length between node 14
print_in_order_nonrecursive : 0 12 13 14 15 16 17 18 19 20 21 22 23 24 34 35 36 37 38 39 40 41
print_element_order by order: 0 12 13 14 15 16 17 18 19 20 21 22 23 24 34 35 36 37 38 39 40 41
print_post_order_nonrecursive : 0 13 14 12 17 18 19 20 21 22 24 23 41 40 39 38 37 36 35 34 16 15
print_pre_order_nonrecursive : 15 12 0 14 13 16 34 23 22 21 20 19 18 17 24 35 36 37 38 39 40 41
min element : 0
max element : 41test_tree:
15--14--12
tree size : 3
tree max length between node 2
print_in_order_nonrecursive : 12 14 15
print_element_order by order: 12 14 15
print_post_order_nonrecursive : 14 12 15
print_pre_order_nonrecursive : 15 12 14
min element : 12
max element : 15tree:--41--40--39--38--37--36--35--34--24--23--22--21--20--19--18--17--16
15--14--13--12--0tree2:--41--40--39--38--37--36--35--34--24--23--22--21--20--19--18--17--16
15--14--13--12--0line:1000 Pass
line:1001 Passline:1004 Pass
line:1005 Pass
12 14 15 Memory leak report:
No memory leak.
