二叉查找树（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.

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/123910.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

android framework之Applicataion启动流程分析（四）

android framework之Applicataion启动流程分析（四）

本文主要学习并了解Application的Activity启动流程。 这边先分析一下Launcher是如何启动进程的Acitivity流程。从Launcher启动Acitivity的时候&#xff0c;它是把启动任务丢给instrumentation模块去协助完成&#xff0c;由它进一步调用AMS的startActivity()方法 去启动&#xf…
阅读更多...
怎么处理zk或redis脑裂

怎么处理zk或redis脑裂

很极端场景会出现脑裂 什么是分布式的脑裂 怎么理解zk脑裂 就是ZK&#xff0c;与客户端可能因为网络原因&#xff0c;客户端A还在跑着后续程序&#xff0c;而zk与客户端之前的心跳断了&#xff0c;此zk就把这节点给删除了&#xff0c;这时另一个客户会加锁成功&#xff0c;就样…
阅读更多...
荣耀9x使用体验

荣耀9x使用体验

第一次使用鸿蒙系统&#xff0c;感觉还行&#xff0c;虽然各种操作和手势不太习惯&#xff0c;但是不影响什么&#xff0c;这是已经发布了4年的手机&#xff0c;用起来没什么毛病&#xff0c;各方面比较均衡。 2年前买的&#xff0c;原价1500块&#xff0c;现在&#xff08;20…
阅读更多...
Unity 之利用Audio Source（音频源）组件用于播放声音

Unity 之利用Audio Source（音频源）组件用于播放声音

文章目录 Unity中的Audio Source&#xff08;音频源&#xff09;是一个用于播放声音的组件&#xff0c;通常附加到游戏对象上&#xff0c;以便在游戏中播放音频效果、音乐或对话。以下是Audio Source的详细介绍&#xff1a; 添加Audio Source&#xff1a; 要在Unity中使用Audio…
阅读更多...
SAM论文翻译

SAM论文翻译

文章目录 Abstract1、Introduction2、Related Work3、Methodology3.1、Semantic Graph3.2、Semantic Aware Module3.3、Decoder3.4、Loss Function 4、Experiments4.1、Datasets4.2、Implementation Details4.3、Evaluation Protocol4.4、Comparison with State-of-the-Art 论文…
阅读更多...
STM32WB55开发(1)----套件概述

STM32WB55开发(1)----套件概述

STM32WB55开发----1.套件概述 所用器件视频教学样品申请优势支持协议系统控制和生态系统访问功能示意图系统框图跳线设置开发板原理图 所用器件 所使用的器件是我们自行设计的开发板&#xff0c;该开发板是基于 STM32WB55 系列微控制器所构建。STM32WBXX_VFQFPN68 不仅是一款评…
阅读更多...
Win10右键 nvidia rtx desktop manager 怎么删除（最新）

Win10右键 nvidia rtx desktop manager 怎么删除（最新）

在更新了最新的 nvidia后原来的隐藏鼠标右键菜单后不行了&#xff0c;新方法如下&#xff1a; 步骤一&#xff1a;在键盘“WINR”键同时操作下&#xff0c;启动运行框&#xff0c;在框内输入“regedit”&#xff0c;打开深度系统win7 的注册表编辑器。 步骤二&#xff1a;为防…
阅读更多...
maven配置nexus私服详解

maven配置nexus私服详解

maven配置nexus私服详解 简介&#xff1a;配置步骤1、本地maven settings.xml配置1.1配置本地仓库位置1.2 server配置1.3 镜像配置1.4 私服仓库配置 2、maven项目pom.xml配置 完整配置模板 简介&#xff1a; 前提是已经搭建好了私服&#xff0c;我们需要在本地maven中配置相关…
阅读更多...
半导体厂务液体泄漏问题的挑战与解决方案

半导体厂务液体泄漏问题的挑战与解决方案

在半导体制造领域&#xff0c;液体泄漏是一项极具挑战性的问题。半导体工厂内有着大量的化学品、工艺液体和废水系统&#xff0c;这些液体在制造过程中扮演着至关重要的角色。然而&#xff0c;液体泄漏可能会导致严重的生产中断、环境污染和安全风险。本文将探讨半导体厂务中的…
阅读更多...
Qt 5.15编译（MinGW）及集成Crypto++ 8.7.0笔记

Qt 5.15编译（MinGW）及集成Crypto++ 8.7.0笔记

一、背景 为使用AES加密库&#xff08;AES/CBC加解密&#xff09;&#xff0c;选用Crypto 库&#xff08;官网&#xff09;。   最新Crypto C库依次为&#xff1a;8.8.0版本&#xff08;2023-6-25&#xff09;、8.7.0&#xff08;2022-8-7&#xff09;和8.6.0&#xff08;202…
阅读更多...
c++ day 2

c++ day 2

1、封装一个结构体&#xff0c;结构体中包含一个私有数组&#xff0c;用来存放学生的成绩&#xff0c;包含一个私有变量&#xff0c;用来记录学生个数&#xff0c; 提供一个公有成员函数&#xff0c;void setNum(int num)用于设置学生个数 提供一个公有成员函数&#xff1a;v…
阅读更多...
新能源商用车软件开发设计规范

新能源商用车软件开发设计规范

目 录 前 言.............................................................................................................. 1 1 范围............................................................................................................... 2 2 规范性…
阅读更多...
【前端demo】CSS border-radius可视化 原生实现

【前端demo】CSS border-radius可视化 原生实现

文章目录 效果原理代码 前端demo系列目录&#xff1a;https://blog.csdn.net/karshey/article/details/132585901 效果 效果预览&#xff1a;https://codepen.io/karshey/pen/zYyBPBR 参考&#xff1a; Fancy Border Radius Generator (9elements.github.io) https://borde…
阅读更多...
zabbix 自动发现

zabbix 自动发现

哈喽大家好&#xff0c;我是咸鱼 昨天老大让我初始化一批服务器&#xff0c;吭哧吭哧弄完之后需要把这批机器添加到 zabbix 上去 但是我发现一台一台添加效率好低&#xff0c;而且特别繁琐&#xff0c;当时我没有想出有什么好的方法&#xff0c;今天上网搜了一下相关资料之后…
阅读更多...
本地电脑搭建web服务器、个人博客网站并发布公网访问 【无公网IP】(1)

本地电脑搭建web服务器、个人博客网站并发布公网访问 【无公网IP】(1)

文章目录 前言1. 安装套件软件2. 创建网页运行环境 指定网页输出的端口号3. 让WordPress在所需环境中安装并运行 生成网页4. “装修”个人网站5. 将位于本地电脑上的网页发布到公共互联网上 前言 在现代社会&#xff0c;网络已经成为我们生活离不开的必需品&#xff0c;而纷繁…
阅读更多...
系统学习Linux-ELK日志收集系统

系统学习Linux-ELK日志收集系统

ELK日志收集系统集群实验 实验环境 角色主机名IP接口httpd192.168.31.50ens33node1192.168.31.51ens33noed2192.168.31.53ens33 环境配置 设置各个主机的ip地址为拓扑中的静态ip&#xff0c;并修改主机名 #httpd [rootlocalhost ~]# hostnamectl set-hostname httpd [root…
阅读更多...
【opencv】多版本安装

【opencv】多版本安装

安装opencv3.2.0以及对应的付费模块 一、安装多版本OpenCV如何切换 按照如下步骤安装的OpenCV&#xff0c;在CMakeLists.txt文件中&#xff0c;直接指定opencv的版本就可以找到相应版本的OpenCV&#xff0c;为了验证可以在CMakeLists.txt文件中使用如下指令输出版本验证&…
阅读更多...
C#写一个UDP程序判断延迟并运行在Centos上

C#写一个UDP程序判断延迟并运行在Centos上

服务端 using System.Net.Sockets; using System.Net;int serverPort 50001; Socket server; EndPoint client new IPEndPoint(IPAddress.Any, 0);//用来保存发送方的ip和端口号CreateSocket();void CreateSocket() {server new Socket(AddressFamily.InterNetwork, SocketT…
阅读更多...
SolVES4.1学习1——安装与使用教程

SolVES4.1学习1——安装与使用教程

1、下载并安装 SolVES 4版本是QGIS插件&#xff0c;但实际使用过程中发现在最新版的QGIS安装该插件过程中&#xff0c;会报错或异常。因此需安装特定版本的软件。共需安装如下图软件及Java环境等。 根据官方文档安装好后&#xff0c;可以进行相关操作。 2、设置QGIS环境 QG…
阅读更多...
消息队列理解

消息队列理解

rocketMQ RocketMQ消息存储原理_码上得天下的博客-CSDN博客 领域模型概述 | RocketMQ kafka Kafka基本架构介绍-腾讯云开发者社区-腾讯云 看完这篇Kafka&#xff0c;你也许就会了Kafka_心的步伐的博客-CSDN博客 Apache Kafka
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023