二叉查找树（binary search tree）（难度7）

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::vector<Record> 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__);
//------上面的代码是用来测试你的代码有没有问题的辅助代码，你无需关注------template<typename 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);template<typename T>friend ostream& operator<<(ostream& out, const binary_search_tree<T>& 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;
};
template<typename T>
std::string binary_search_tree<T>::to_string_in_order(void) const
{std::stringstream oss;this->print_in_order_recursive(oss);auto str = oss.str();return str;
}
template<typename T>
binary_search_tree<T>::binary_search_tree(const T* arr, const int length) : binary_search_tree()
{//(4) your code //可以使用成员函数insert(const T& data) 来实现这个函数
}
template<typename T>
inline binary_search_tree<T>::binary_search_tree(const binary_search_tree & from) :m_root(nullptr)
{//(5) your code //可以使用成员函数copy来实现
}
template<typename T>
binary_search_tree<T>& binary_search_tree<T>::operator=(const binary_search_tree & from)
{//(5) your code //可以使用成员函数copy来实现。//从这里可以看出copy函数应该先用clear成员函数清空自己原有的全部节点return *this;
}
template<typename T>
void binary_search_tree<T>::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/*提供节点存储的数据*/);}
}
template<typename T>
bool binary_search_tree<T>::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;
}
template<typename T>
int binary_search_tree<T>::hight(void) const
{return hight(m_root);
}
template<typename T>
int binary_search_tree<T>::hight(const tree_node* _t) const
{//树的高度，也是树的层树，最大层的层数就是树的高度//(7) your code 如果没有元素，返回0// 如果只有一个根节点，没有孩子节点高度为1// 如果有孩子节点，树的高度就 = 1 + 孩子节点的高度（左右子树高度较大的那一个）return -1;
}
template<typename T>
bool binary_search_tree<T>::operator==(const binary_search_tree & other) const
{return this->equal(other);//两个二叉树相等，当且仅当两颗树长的一模一样
}
template<typename T>
bool binary_search_tree<T>::equal(const binary_search_tree & other) const
{return equal(m_root, other.m_root);
}
template<typename T>
bool binary_search_tree<T>::equal(const tree_node* lhs, const tree_node* rhs) const
{// 先判断两个树是否为空//再判断两个树是否都是叶子节点  可以使用 is_leaf_node_equal 成员函数//再判断两个树的两个左右子树是否同时相等  可以递归调用当前equal函数//(8) your codereturn false;
}
template<typename T>
inline bool binary_search_tree<T>::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;
}
template<typename T>
inline bool binary_search_tree<T>::is_node_leaf(const tree_node * node) const
{return node != nullptr && node->left == nullptr && node->right == nullptr;
}template<typename T>
///*需要被创建的节点*/, nullptr/*需要被创建的节点*/, other.m_root/*提供节点存储的数据*/
void binary_search_tree<T>::copy_node_from(tree_node *& dest, tree_node* dest_parent, const tree_node * from)
{//(9) your code 深度拷贝from节点，并切递归拷贝，从而完成整棵树的拷贝//注意dest节点传递的是引用，这意味着你可以非常方便的对这个地址变量赋值，赋值就会修改传进来的外部变量//改函数使用递归调用自己的方式，完成整棵树的拷贝。注意对左子树和又子树可能需要分别调用一次递归函数才能完成。}template<typename T>
int binary_search_tree<T>::max_length_between_node(void) const
{int max_length = 0;const tree_node* ptree = m_root;list<tree_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::max<int>(tempBetween, max_length);}return max_length;
}
template<typename T>
void binary_search_tree<T>::clear(void)
{//使用一个辅助队列(或者栈)，层次遍历删除所有节点。//遍历到一个节点A就把孩子BC放到队列，并把这个节点A从队列里取出释放//(10) your code}
template<typename T>
void binary_search_tree<T>::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);}
}
template<typename T>
void binary_search_tree<T>::print_in_order_nonrecursive(void) const
{cout << "print_in_order_nonrecursive : ";stack<tree_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;
}
template<typename T>
inline void binary_search_tree<T>::print_in_order_recursive(std::ostream & os) const
{print_in_order_recursive(os, m_root);
}
template<typename T>
void binary_search_tree<T>::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);
}
template<typename T>
ostream& operator<<(ostream& out, const binary_search_tree<T>& tree)
{tree.print_binary_tree(out, tree.m_root, 0);return out;
}
template<typename T>
void binary_search_tree<T>::print_post_order_nonrecursive(void) const
{//后续序序遍历输出一颗树的全部结点值2,3,1//广度优先遍历cout << "print_post_order_nonrecursive : ";typedef pair<tree_node*, bool> multinode;stack<multinode> 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;
}
template<typename T>
void binary_search_tree<T>::print_pre_order_nonrecursive(void) const
{//先序遍历输出一颗树的全部结点值1,2,3,先根遍历cout << "print_pre_order_nonrecursive : ";stack<tree_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;}
}
template<typename T>
bool binary_search_tree<T>::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;
}
template<typename T>
typename binary_search_tree<T>::tree_node* binary_search_tree<T>::find(const T& data)
{//(11) your code 利用find，非递归实现：查找某个值是否存在于树中return nullptr;
}template<typename T>
int binary_search_tree<T>::size(void) const
{return m_size;
}
template<typename T>
T binary_search_tree<T>::minmum(void) const
{//(12) your code 返回最小值 ，请使用成员函数 minmum(tree_node* p) const  来实现return T();
}
template<typename T>
typename binary_search_tree<T>::tree_node* binary_search_tree<T>::minmum(tree_node* p) const
{//(13) your code 返回最小值：非递归实现return nullptr;
}
template<typename T>
T binary_search_tree<T>::maxmum(void) const
{//(14) your code 返回最大值 ，请使用成员函数 maxmum(tree_node* p) const  来实现return T();
}
template<typename T>
typename binary_search_tree<T>::tree_node* binary_search_tree<T>::maxmum(tree_node* t) const
{//(14) your code 返回最大值：非递归实现return nullptr;
}
template<typename T>
typename binary_search_tree<T>::tree_node* binary_search_tree<T>::successor(tree_node* t) const
{//(15) your code  找到一个节点的后继结点，这个函数是顺序迭代遍历二叉树的关键函数。//具体思路为，如果这个节点有右子树，那么右子树的minmum节点就是后继结点。//如果，这个节点没有右子树，比该节点大的值，一定是往右上方去的第一个节点。//参考《算法导论》return nullptr;
}
template<typename T>
void binary_search_tree<T>::print_element_order(void) const
{cout << "print_element_order by order: ";if (!empty()){//(16) your code 使用后继节点成员函数作为顺序迭代的依据，实现顺序遍历一颗二次函数。//循环获取后继，只要有后继，就输出这个后继。cout << endl;}
}template<typename T>
void binary_search_tree<T>::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);}
}
template<typename T>
void binary_search_tree<T>::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}
}
template<typename T>
void binary_search_tree<T>::update_parent(tree_node* pnode)
{//删除叶子结点后，让父节点指向空指针if (pnode->parent){auto parent = pnode->parent;is_left_child(parent, pnode) ? (parent->left = nullptr) : (parent->right = nullptr);}
}
template<typename T>
void binary_search_tree<T>::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;}
}
template<typename T>
bool binary_search_tree<T>::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_tree<int>& _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_tree<int> tree;check(tree.size() == 0);check(tree.empty());check(tree.hight() == 0);
}
void test2()
{int arr[1] = { 1 };binary_search_tree<int> 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_tree<int> 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_tree<int> 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_tree<int> 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_tree<int> 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_tree<int> 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_tree<int> 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_tree<int> 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_tree<int> 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_tree<int> 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_tree<int> 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_tree<int> 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_tree<int> 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_tree<int> tree(arr, length);check(tree.minmum() == 1);check(tree.maxmum() == 10);
}
void test16()
{constexpr int length = 1;int arr[length] = { 1 };binary_search_tree<int> 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_tree<int> 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_tree<int> 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_tree<int> 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_tree<int> 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_tree<int> 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_tree<int> 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_tree<int> 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_tree<int>& 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_tree<int> 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_tree<int> tree(a, 22);check(tree.size() == 22);check(tree.empty() == false);check(tree.maxmum() == 41);check(tree.minmum() == 0);test_tree(tree);binary_search_tree<int> 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.