• 二叉查找树（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的值。

    待实现代码

    1. #pragma once
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. #include 
    11. #include 
    12. #include 
    13. using namespace std;
    14.  
    15. //------下面的代码是用来测试你的代码有没有问题的辅助代码，你无需关注------
    16. #include 
    17. #include 
    18. #include  
    19. #include 
    20. #include 
    21. using namespace std;
    22. 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 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)
    23. {
    24.     return newFunctionImpl(sz, file, line, true);
    25. }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); } }
    26. #define new new(__FILE__, __LINE__)
    27. 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); } }
    28. #define check(msg)  check_do(msg, __LINE__);
    29. //------上面的代码是用来测试你的代码有没有问题的辅助代码，你无需关注------
    30.  
    31. template<typename T>
    32. class binary_search_tree
    33. {
    34. private:
    35.     struct tree_node//OK
    36.     {
    37.         tree_node() :data(T()){}
    38.         tree_node(const T& t) :data(t){}
    39.         bool exist_parent(void) const { return parent != nullptr; }
    40.         T data;
    41.         tree_node* parent = nullptr;
    42.         tree_node* left = nullptr;
    43.         tree_node* right = nullptr;
    44.     };
    45. public:
    46.     binary_search_tree(void) :m_root(nullptr) {}//默认构造函数：什么也不需要做，因为成员定义的时候就已经初始化了
    47.     binary_search_tree(const T*, const int);//从数组构造一颗二叉树
    48.     binary_search_tree(const binary_search_tree&);//拷贝构造函数
    49.     binary_search_tree& operator = (const binary_search_tree&);
    50.     ~binary_search_tree(void) { clear(); }//析构函数
    51. public:
    52.     int size(void) const;//元素数量
    53.     bool empty(void) const { return size() == 0; }//二叉树是否为空
    54.     bool insert(const T& data);//插入一个元素
    55.  
    56.     T minmum(void) const;//最小值
    57.     T maxmum(void) const;//最大值
    58.  
    59.     bool exists(const T& data) const;//判断元素是否存在
    60.     void clear(void);//非递归清空二叉树
    61.     void erase(const T& data);
    62.  
    63.     template<typename T>
    64.     friend ostream& operator<<(ostream& out, const binary_search_tree& tree);//输出二叉树
    65.     void print_pre_order_nonrecursive(void) const;//非递归:先序遍历输出二叉树
    66.     void print_in_order_nonrecursive(void) const;//非递归:中序遍历输出二叉树
    67.     void print_post_order_nonrecursive(void) const;//非递归:后续遍历输出二叉树
    68.  
    69.     void print_in_order_recursive(std::ostream& os) const;//递归中序遍历输出二叉树
    70.     void print_element_order(void) const;//非递归按元素顺序输出二叉树
    71.     std::string to_string_in_order(void) const;
    72.     int max_length_between_node(void) const;//最大节点距离
    73.     int hight(void) const;//树高度
    74.     bool operator==(const binary_search_tree& other) const;//两个树相等：结构相同，对应元素相同
    75.     bool operator!=(const binary_search_tree& other) const { return !equal(other); }//两个树不相等
    76.     bool equal(const binary_search_tree& other) const;//两个树相等：结构相同，对应元素相同
    77. private:
    78.     void print_binary_tree(ostream&, const tree_node* bt, int depth) const;//二叉树形式打印二叉树
    79.     tree_node* find(const T& data);//查找
    80.     tree_node* maxmum(tree_node*) const;//最大节点
    81.     tree_node* minmum(tree_node*) const;//最小节点
    82.     tree_node* successor(tree_node* t) const;//后继节点
    83.     //节点的深度与高度：对于树中相同深度的每个结点来说，它们的高度不一定相同，这取决于每个结点下面的叶结点的深度
    84.     int hight(const tree_node* _t) const;
    85.     bool equal(const tree_node* lhs, const tree_node* rhs) const;//两个树相等：结构相同，对应元素相同
    86.     bool is_node_leaf(const tree_node* node) const;
    87.     bool is_left_child(const tree_node* parent, const tree_node* node);
    88.     bool is_leaf_node_equal(const tree_node* lhs, const tree_node* rhs) const;
    89.     void copy(const binary_search_tree& other);
    90.     void copy_node_from(tree_node*& dest, tree_node* dest_parent, const tree_node* from);
    91.     void print_in_order_recursive(std::ostream& os
    92.         , const tree_node* node) const;//递归中序遍历输出二叉树
    93.     void erase_node(tree_node*& pnode);//参数是引用类型，主要是为了：erase_node(m_root) 时，更新m_root;
    94.     void erase_and_reconnect(tree_node*& pnode, tree_node* pnode_child);
    95.     void update_parent(tree_node* pnode);//删除叶子结点后，让父节点指向空指针
    96. private:
    97.     tree_node* left(tree_node* p)
    98.     {
    99.         assert(p != nullptr);
    100.         return p->left;
    101.     }
    102. private:
    103.     tree_node* m_root = nullptr;//OK
    104.     int m_size = 0;
    105. };
    106. template<typename T>
    107. std::string binary_search_tree::to_string_in_order(void) const
    108. {
    109.     std::stringstream oss;
    110.     this->print_in_order_recursive(oss);
    111.     auto str = oss.str();
    112.     return str;
    113. }
    114. template<typename T>
    115. binary_search_tree::binary_search_tree(const T* arr, const int length) : binary_search_tree()
    116. {
    117.     //(4) your code 
    118.     //可以使用成员函数insert(const T& data) 来实现这个函数
    119. }
    120. template<typename T>
    121. inline binary_search_tree::binary_search_tree(const binary_search_tree & from) :m_root(nullptr)
    122. {
    123.     //(5) your code 
    124.     //可以使用成员函数copy来实现
    125. }
    126. template<typename T>
    127. binary_search_tree& binary_search_tree::operator=(const binary_search_tree & from)
    128. {
    129.     //(5) your code 
    130.     //可以使用成员函数copy来实现。
    131.     //从这里可以看出copy函数应该先用clear成员函数清空自己原有的全部节点
    132.  
    133.  
    134.     return *this;
    135. }
    136. template<typename T>
    137. void binary_search_tree::copy(const binary_search_tree& other)
    138. {
    139.     if (this == &other)//如果拷贝自己，则什么也不做
    140.     {
    141.         return;//直接返回
    142.     }
    143.     clear();//先清空自己的内容
    144.     m_size = other.m_size;//成员变量赋值
    145.     if (other.m_root)//从根节点开始拷贝；递归的拷贝二叉树的每一个节点，照葫芦画瓢
    146.     {
    147.         copy_node_from(m_root/*需要被创建的节点*/, nullptr/*需要被创建的节点的父节点：用户指向孩子*/, other.m_root/*提供节点存储的数据*/);
    148.     }
    149. }
    150. template<typename T>
    151. bool binary_search_tree::insert(const T& data)
    152. {
    153.     if (m_root != nullptr)
    154.     {
    155.         tree_node *fast, *slow, *ptemp;
    156.         fast = slow = ptemp = m_root;
    157.  
    158.         while (fast != 0)
    159.         {
    160.             slow = fast;
    161.             if (data < slow->data)
    162.             {
    163.                 fast = slow->left;
    164.             }
    165.             else if (data > slow->data)
    166.             {
    167.                 fast = slow->right;
    168.             }
    169.             else
    170.             //esle equal do nothing 元素不允许重复
    171.             //，元素如果已经存在，什么也不做
    172.             {
    173.                 fast = 0;
    174.                 return false;//直接退出，不再插入相同的元素的
    175.             }
    176.         }
    177.         if (data < slow->data)
    178.         {
    179.             slow->left = new tree_node(data);
    180.             slow->left->parent = slow;
    181.         }
    182.         else if (data > slow->data)
    183.         {
    184.             slow->right = new tree_node(data);
    185.             slow->right->parent = slow;
    186.         }
    187.         else
    188.         {
    189.             return false;
    190.         }
    191.         //esle equal do nothing
    192.     }
    193.     else
    194.     {
    195.         m_root = new tree_node(data);
    196.     }
    197.     ++m_size;
    198.     return true;
    199. }
    200. template<typename T>
    201. int binary_search_tree::hight(void) const
    202. {
    203.     return hight(m_root);
    204. }
    205. template<typename T>
    206. int binary_search_tree::hight(const tree_node* _t) const
    207. {
    208.     //树的高度，也是树的层树，最大层的层数就是树的高度
    209.     //(7) your code 如果没有元素，返回0
    210.     // 如果只有一个根节点，没有孩子节点高度为1
    211.     // 如果有孩子节点，树的高度就 = 1 + 孩子节点的高度（左右子树高度较大的那一个）
    212.  
    213.  
    214.     return -1;
    215. }
    216. template<typename T>
    217. bool binary_search_tree::operator==(const binary_search_tree & other) const
    218. {
    219.     return this->equal(other);//两个二叉树相等，当且仅当两颗树长的一模一样
    220. }
    221. template<typename T>
    222. bool binary_search_tree::equal(const binary_search_tree & other) const
    223. {
    224.     return equal(m_root, other.m_root);
    225. }
    226. template<typename T>
    227. bool binary_search_tree::equal(const tree_node* lhs, const tree_node* rhs) const
    228. {
    229.     // 先判断两个树是否为空
    230.  
    231.     //再判断两个树是否都是叶子节点  可以使用 is_leaf_node_equal 成员函数
    232.  
    233.     //再判断两个树的两个左右子树是否同时相等  可以递归调用当前equal函数
    234.  
    235.     //(8) your code
    236.  
    237.     return false;
    238. }
    239. template<typename T>
    240. inline bool binary_search_tree::is_leaf_node_equal(const tree_node* lhs
    241.     , const tree_node* rhs) const
    242. {
    243.     if (is_node_leaf(lhs) && is_node_leaf(rhs))
    244.     {
    245.         return lhs->data == rhs->data;
    246.     }
    247.     return false;
    248. }
    249. template<typename T>
    250. inline bool binary_search_tree::is_node_leaf(const tree_node * node) const
    251. {
    252.     return node != nullptr && node->left == nullptr && node->right == nullptr;
    253. }
    254.  
    255.  
    256. template<typename T>
    257. ///*需要被创建的节点*/, nullptr/*需要被创建的节点*/, other.m_root/*提供节点存储的数据*/
    258. void binary_search_tree::copy_node_from(tree_node *& dest, tree_node* dest_parent, const tree_node * from)
    259. {
    260.     //(9) your code 深度拷贝from节点，并切递归拷贝，从而完成整棵树的拷贝
    261.  
    262.     //注意dest节点传递的是引用，这意味着你可以非常方便的对这个地址变量赋值，赋值就会修改传进来的外部变量
    263.  
    264.     //改函数使用递归调用自己的方式，完成整棵树的拷贝。注意对左子树和又子树可能需要分别调用一次递归函数才能完成。
    265.  
    266. }
    267.  
    268. template<typename T>
    269. int binary_search_tree::max_length_between_node(void) const
    270. {
    271.     int max_length = 0;
    272.  
    273.     const tree_node* ptree = m_root;
    274.  
    275.     list listNode;
    276.  
    277.     listNode.push_back(m_root);
    278.     while (!listNode.empty())
    279.     {
    280.         auto pnode = listNode.front();
    281.         listNode.pop_front();
    282.         if (pnode->left != nullptr)
    283.         {
    284.             listNode.push_back(pnode->left);
    285.         }
    286.         if (pnode->right != nullptr)
    287.         {
    288.             listNode.push_back(pnode->right);
    289.         }
    290.         int tempBetween = hight(pnode->left) + hight(pnode->right);
    291.  
    292.         max_length = std::max<int>(tempBetween, max_length);
    293.     }
    294.  
    295.  
    296.     return max_length;
    297. }
    298. template<typename T>
    299. void binary_search_tree::clear(void)
    300. {
    301.     //使用一个辅助队列(或者栈)，层次遍历删除所有节点。
    302.     //遍历到一个节点A就把孩子BC放到队列，并把这个节点A从队列里取出释放
    303.     //(10) your code
    304.  
    305.  
    306. }
    307. template<typename T>
    308. void binary_search_tree::print_binary_tree(ostream& out, const tree_node* bt, int depth) const
    309. {
    310.     //用右左孩子的方式输出一颗树,先输出右孩子后输出左孩子
    311.     if (bt)
    312.     {
    313.         print_binary_tree(out, bt->right, depth + 1);
    314.  
    315.         if (depth == 0)
    316.         {
    317.             out << bt->data << endl;
    318.         }
    319.         else if (depth == 1)
    320.         {
    321.             out << " --" << bt->data << endl;
    322.         }
    323.         else
    324.         {
    325.             int n = depth;
    326.             while (--n)
    327.             {
    328.                 cout << "    ";
    329.             }
    330.             out << " --" << bt->data << endl;
    331.         }
    332.  
    333.         print_binary_tree(out, bt->left, depth + 1);
    334.     }
    335. }
    336. template<typename T>
    337. void binary_search_tree::print_in_order_nonrecursive(void) const
    338. {
    339.     cout << "print_in_order_nonrecursive : ";
    340.     stack tempstack;
    341.     tree_node* t = m_root;
    342.     if (t != NULL)
    343.     {
    344.         do
    345.         {
    346.             tempstack.push(t);
    347.             t = t->left;
    348.         } while (t != NULL);
    349.     }
    350.     while (!tempstack.empty())
    351.     {
    352.         tree_node* p = tempstack.top();
    353.         cout << p->data << " ";
    354.         tempstack.pop();
    355.         if (p->right != NULL)
    356.         {
    357.             p = p->right;
    358.             do
    359.             {
    360.                 tempstack.push(p);
    361.                 p = p->left;
    362.             } while (p != NULL);
    363.         }
    364.     }
    365.     cout << endl;
    366. }
    367. template<typename T>
    368. inline void binary_search_tree::print_in_order_recursive(std::ostream & os) const
    369. {
    370.     print_in_order_recursive(os, m_root);
    371. }
    372. template<typename T>
    373. void binary_search_tree::print_in_order_recursive(std::ostream & os, const tree_node * node) const
    374. {
    375.     if (node == nullptr)
    376.     {
    377.         return;
    378.     }
    379.     print_in_order_recursive(os, node->left);
    380.     os << node->data << " ";
    381.     print_in_order_recursive(os, node->right);
    382. }
    383. template<typename T>
    384. ostream& operator<<(ostream& out, const binary_search_tree& tree)
    385. {
    386.     tree.print_binary_tree(out, tree.m_root, 0);
    387.     return out;
    388. }
    389. template<typename T>
    390. void binary_search_tree::print_post_order_nonrecursive(void) const
    391. {
    392.     //后续序序遍历输出一颗树的全部结点值2,3,1
    393.     //广度优先遍历
    394.     cout << "print_post_order_nonrecursive : ";
    395.     typedef pairbool> multinode;
    396.     stack tempstack;
    397.     if (m_root)
    398.     {
    399.         tempstack.push(make_pair(m_root, false));
    400.     }
    401.     while (!tempstack.empty())
    402.     {
    403.         multinode m = tempstack.top(); tempstack.pop();
    404.         if (m.first->left == NULL && m.first->right == NULL)
    405.         {//叶子节点直接输出
    406.             cout << m.first->data << " ";
    407.         }
    408.         else if (m.second == true)
    409.         {//所有孩子都遍历完了才会到这一步
    410.             cout << m.first->data << " ";
    411.         }
    412.         else
    413.         {//非终结点，并且孩子还没遍历完。
    414.             m.second = true; tempstack.push(m);
    415.             if (m.first->right != NULL)
    416.             {
    417.                 tempstack.push(make_pair(m.first->right, false));
    418.             }
    419.             if (m.first->left != NULL)
    420.             {
    421.                 tempstack.push(make_pair(m.first->left, false));
    422.             }
    423.         }
    424.     }
    425.     cout << endl;
    426. }
    427. template<typename T>
    428. void binary_search_tree::print_pre_order_nonrecursive(void) const
    429. {
    430.     //先序遍历输出一颗树的全部结点值1,2,3,先根遍历
    431.     cout << "print_pre_order_nonrecursive : ";
    432.     stack node_stack;
    433.     if (m_root)
    434.     {
    435.         node_stack.push(m_root);
    436.         tree_node* t;
    437.         while (!node_stack.empty())
    438.         {
    439.             t = node_stack.top();
    440.             node_stack.pop();
    441.             cout << t->data << " ";
    442.             if (t->right != 0)
    443.             {
    444.                 node_stack.push(t->right);
    445.             }
    446.             if (t->left != 0)
    447.             {
    448.                 node_stack.push(t->left);
    449.             }
    450.         }
    451.         cout << endl;
    452.     }
    453. }
    454. template<typename T>
    455. bool binary_search_tree::exists(const T& data) const
    456. {
    457.     bool result = false;
    458.     if (m_root)
    459.     {
    460.         tree_node* pfind = m_root;
    461.         while (pfind)
    462.         {
    463.             if (pfind->data == data)
    464.             {
    465.                 result = true;
    466.                 break;
    467.             }
    468.             else if (data < pfind->data)
    469.             {
    470.                 pfind = pfind->left;
    471.             }
    472.             else
    473.                 pfind = pfind->right;
    474.         }
    475.     }
    476.     return result;
    477. }
    478. template<typename T>
    479. typename binary_search_tree::tree_node* binary_search_tree::find(const T& data)
    480. {
    481.     //(11) your code 利用find，非递归实现：查找某个值是否存在于树中
    482.     return nullptr;
    483. }
    484.  
    485. template<typename T>
    486. int binary_search_tree::size(void) const
    487. {
    488.     return m_size;
    489. }
    490. template<typename T>
    491. T binary_search_tree::minmum(void) const
    492. {
    493.     //(12) your code 返回最小值 ，请使用成员函数 minmum(tree_node* p) const  来实现
    494.     return T();
    495. }
    496. template<typename T>
    497. typename binary_search_tree::tree_node* binary_search_tree::minmum(tree_node* p) const
    498. {
    499.     //(13) your code 返回最小值：非递归实现
    500.     return nullptr;
    501. }
    502. template<typename T>
    503. T binary_search_tree::maxmum(void) const
    504. {
    505.     //(14) your code 返回最大值 ，请使用成员函数 maxmum(tree_node* p) const  来实现
    506.     return T();
    507. }
    508. template<typename T>
    509. typename binary_search_tree::tree_node* binary_search_tree::maxmum(tree_node* t) const
    510. {
    511.     //(14) your code 返回最大值：非递归实现
    512.     return nullptr;
    513. }
    514. template<typename T>
    515. typename binary_search_tree::tree_node* binary_search_tree::successor(tree_node* t) const
    516. {
    517.     //(15) your code  找到一个节点的后继结点，这个函数是顺序迭代遍历二叉树的关键函数。
    518.     //具体思路为，如果这个节点有右子树，那么右子树的minmum节点就是后继结点。
    519.     //如果，这个节点没有右子树，比该节点大的值，一定是往右上方去的第一个节点。
    520.     //参考《算法导论》
    521.  
    522.  
    523.     return nullptr;
    524. }
    525. template<typename T>
    526. void binary_search_tree::print_element_order(void) const
    527. {
    528.     cout << "print_element_order by order: ";
    529.     if (!empty())
    530.     {
    531.         //(16) your code 使用后继节点成员函数作为顺序迭代的依据，实现顺序遍历一颗二次函数。
    532.         //循环获取后继，只要有后继，就输出这个后继。
    533.  
    534.  
    535.         cout << endl;
    536.     }
    537. }
    538.  
    539. template<typename T>
    540. void binary_search_tree::erase(const T& data)
    541. {
    542.     tree_node* itr = find(data);
    543.     assert(itr != nullptr);
    544.     --m_size;
    545.     if (itr == m_root)
    546.     {
    547.         /*删除根节点，可能需要释放根节点本身，这个时候m_root的指向需要更新。
    548.         * 所以erase_node的参数是引用类型，希望可以在erase_node内部对m_root重新
    549.         * 赋值来打到更新根节点指向的目的。
    550.         */
    551.         erase_node(m_root);
    552.         return;
    553.     }
    554.     else
    555.     {
    556.         erase_node(itr);
    557.     }
    558. }
    559. template<typename T>
    560. void binary_search_tree::erase_node(tree_node*& pnode)
    561. {
    562.     //pnode如果没有parent，那么它就是root，这个时候，删除pnode
    563.     // ，无需考虑pnode的parent需要更新的问题。
    564.     //只需要处理其孩子替代自己的问题
    565.  
    566.     if (pnode->left == nullptr && pnode->right == nullptr)
    567.     {
    568.         //叶子结点被删除了的话，被删除节点的父亲应该指向空指针。
    569.         update_parent(pnode);//内部会先判断pnode有没有parent
    570.         delete pnode;
    571.         //这里会更新传进来的引用参数，比如，如果传进来的是m_root的话。
    572.         pnode = nullptr;//如果pnode是m_root的话，这句话就会变得必不可少（更新m_root）
    573.     }
    574.     //如果被删除的节点p只有左孩子：让p的左孩子p_left_child取代自己作为p的parent节点的做孩子
    575.     else if (pnode->left != nullptr && pnode->right == nullptr)
    576.     {
    577.         //让pnode的父亲节点和pnode的孩子建立连接
    578.         erase_and_reconnect(pnode, pnode->left);
    579.     }
    580.     //如果只有右孩子：让右孩子取代自己
    581.     else if (pnode->left == nullptr && pnode->right != nullptr)
    582.     {
    583.         //让pnode的父亲节点和pnode的孩子建立连接
    584.         erase_and_reconnect(pnode, pnode->right);
    585.     }
    586.     else
    587.     {
    588.         //https://zhuanlan.zhihu.com/p/640863892
    589.         //分成下面几个步骤进行：
    590.         //1 找到z的后继，y是z的后继。这时候可以确定y是不可能有左孩子的。
    591.         //2 删除y，让y的右孩子x取代自己的位置。删除只有一个孩子的节点上面已经讨论过。
    592.         //3 让y的值覆盖z的值。
    593.         tree_node* psuccessor = successor(pnode);
    594.         pnode->data = psuccessor->data;//3 让y的值覆盖z的值。
    595.         //2 删除y, y只有一个孩子，只有一个孩子的节点删除此函数的开始部分已经实现了。只需要调用此函数即可。
    596.         //(17) your code
    597.     }
    598. }
    599. template<typename T>
    600. void binary_search_tree::update_parent(tree_node* pnode)
    601. {//删除叶子结点后，让父节点指向空指针
    602.     if (pnode->parent)
    603.     {
    604.         auto parent = pnode->parent;
    605.         is_left_child(parent, pnode) ? (parent->left = nullptr) : (parent->right = nullptr);
    606.     }
    607. }
    608. template<typename T>
    609. void binary_search_tree::erase_and_reconnect(tree_node*& delete_pnode, tree_node* pnode_child)
    610. {
    611.     //让左孩子取代自己，同时考虑parent不存在的情况下取代自己。
    612.     if (delete_pnode->exist_parent())
    613.     {
    614.         //拿到父节点
    615.         auto parent = delete_pnode->parent;
    616.         auto is_left = is_left_child(parent, delete_pnode);
    617.         //先备份地址，将来用于释放内存
    618.         auto pbackup = delete_pnode;
    619.         //指向新节点：自己的左孩子替代自己
    620.         // reconnect1 ->
    621.         delete_pnode = pnode_child;
    622.         // <- reconnect2 
    623.         pnode_child->parent = parent;//指向新的父亲
    624.         //删除自己原来的内存
    625.         delete pbackup;
    626.  
    627.         //父节点和自己的左孩子建立连接
    628.         is_left ? parent->left = delete_pnode : parent->right = delete_pnode;
    629.     }
    630.     else //删除根节点， 删除根节点可不是删除整个树哦
    631.     {
    632.         //先备份地址，将来用于释放内存
    633.         auto pbackup = delete_pnode;
    634.         //指向新节点：自己的左孩子替代自己
    635.         delete_pnode = pnode_child;
    636.         //删除自己原来的内存
    637.         delete pbackup;
    638.     }
    639. }
    640. template<typename T>
    641. bool binary_search_tree::is_left_child(const tree_node* parent, const tree_node* pnode)
    642. {
    643.     assert(parent != nullptr);
    644.     assert(pnode != nullptr);
    645.     return (parent->left == pnode);
    646. }
    647.  
    648. void test_tree(const binary_search_tree<int>& _tree)
    649. {
    650.     cout << "test_tree:\n";
    651.     cout << _tree;
    652.     cout << "tree size : " << _tree.size() << endl;
    653.     cout << "tree max length between node " << _tree.max_length_between_node() << endl;
    654.     _tree.print_in_order_nonrecursive();
    655.     _tree.print_element_order();
    656.     _tree.print_post_order_nonrecursive();
    657.     _tree.print_pre_order_nonrecursive();
    658.     cout << "min element : " << _tree.minmum() << endl;
    659.     cout << "max element : " << _tree.maxmum() << "\n" << endl;
    660. }
    661. void test1()
    662. {
    663.     binary_search_tree<int> tree;
    664.     check(tree.size() == 0);
    665.     check(tree.empty());
    666.     check(tree.hight() == 0);
    667. }
    668. void test2()
    669. {
    670.     int arr[1] = { 1 };
    671.     binary_search_tree<int> tree(arr, 1);
    672.     check(tree.size() == 1);
    673.     check(tree.to_string_in_order() == "1 ");
    674.     check(!tree.empty());
    675. }
    676. void test3()
    677. {
    678.     int arr[2] = { 1, 2 };
    679.     binary_search_tree<int> tree(arr, 2);
    680.     check(tree.size() == 2);
    681.     check(tree.to_string_in_order() == "1 2 ");
    682.     check(!tree.empty());
    683. }
    684. void test4()
    685. {
    686.     int arr[2] = { 2, 1 };
    687.     binary_search_tree<int> tree(arr, 2);
    688.     check(tree.size() == 2);
    689.     check(tree.to_string_in_order() == "1 2 ");
    690.     check(!tree.empty());
    691. }
    692. void test5()
    693. {
    694.     constexpr int length = 3;
    695.     int arr[length] = { 1, 2, 3 };
    696.     binary_search_tree<int> tree(arr, length);
    697.     check(tree.size() == length);
    698.     check(tree.to_string_in_order() == "1 2 3 ");
    699.     check(!tree.empty());
    700. }
    701. void test6()
    702. {
    703.     constexpr int length = 3;
    704.     int arr[length] = { 2, 1, 3 };
    705.     binary_search_tree<int> tree(arr, length);
    706.     check(tree.size() == length);
    707.     check(tree.to_string_in_order() == "1 2 3 ");
    708.     check(!tree.empty());
    709. }
    710. void test7()
    711. {
    712.     constexpr int length = 3;
    713.     int arr[length] = { 3, 2, 1, };
    714.     binary_search_tree<int> tree(arr, length);
    715.     check(tree.size() == length);
    716.     check(tree.to_string_in_order() == "1 2 3 ");
    717.     check(!tree.empty());
    718. }
    719. void test8()
    720. {
    721.     constexpr int length = 3;
    722.     int arr[length] = { 3, 1, 2, };
    723.     binary_search_tree<int> tree(arr, length);
    724.     check(tree.size() == length);
    725.     check(tree.to_string_in_order() == "1 2 3 ");
    726.     check(!tree.empty());
    727. }
    728. void test9()
    729. {
    730.     constexpr int length = 10;
    731.     int arr[length] = { 1,3,5,7,9,2,4,6,8,10 };
    732.     binary_search_tree<int> tree(arr, length);
    733.     check(tree.size() == length);
    734.     check(tree.to_string_in_order() ==
    735.         "1 2 3 4 5 6 7 8 9 10 ");
    736.     check(!tree.empty());
    737. }
    738. void test10()
    739. {
    740.     constexpr int length = 10;
    741.     int arr[length] = { 2,4,6,8,10,1,3,5,7,9 };
    742.     binary_search_tree<int> tree(arr, length);
    743.     check(tree.size() == length);
    744.     check(tree.to_string_in_order() ==
    745.         "1 2 3 4 5 6 7 8 9 10 ");
    746.     check(!tree.empty());
    747. }
    748. void test11()
    749. {
    750.     constexpr int length = 10;
    751.     int arr[length] = { 10,9,8,7,6,5,4,3,2,1 };
    752.     binary_search_tree<int> tree(arr, length);
    753.     check(tree.size() == length);
    754.     check(tree.to_string_in_order() ==
    755.         "1 2 3 4 5 6 7 8 9 10 ");
    756.     check(!tree.empty());
    757.     check(tree.hight() == 10);
    758. }
    759. void test12()
    760. {
    761.     constexpr int length = 10;
    762.     int arr[length] = { 5,4,3,2,1,10,9,8,7,6 };
    763.     binary_search_tree<int> tree(arr, length);
    764.     check(tree.size() == length);
    765.     check(tree.to_string_in_order() ==
    766.         "1 2 3 4 5 6 7 8 9 10 ");
    767.     check(!tree.empty());
    768.     check(tree.hight() == 6);
    769. }
    770. void test13()
    771. {
    772.     constexpr int length = 1;
    773.     int arr[length] = { 1 };
    774.     binary_search_tree<int> tree(arr, length);
    775.     check(tree.minmum() == 1);
    776.     check(tree.maxmum() == 1);
    777.     check(tree.hight() == 1);
    778. }
    779. void test14()
    780. {
    781.     constexpr int length = 2;
    782.     int arr[length] = { 1, 2 };
    783.     binary_search_tree<int> tree(arr, length);
    784.     check(tree.minmum() == 1);
    785.     check(tree.maxmum() == 2);
    786.     check(tree.hight() == 2);
    787. }
    788. void test15()
    789. {
    790.     constexpr int length = 10;
    791.     int arr[length] = { 5,4,3,2,1,10,9,8,7,6 };
    792.     binary_search_tree<int> tree(arr, length);
    793.     check(tree.minmum() == 1);
    794.     check(tree.maxmum() == 10);
    795. }
    796. void test16()
    797. {
    798.     constexpr int length = 1;
    799.     int arr[length] = { 1 };
    800.     binary_search_tree<int> tree(arr, length);
    801.     check(tree.exists(1));
    802.     tree.erase(1);
    803.     check(!tree.exists(1));
    804.     check(tree.size() == 0);
    805. }
    806. void test17()
    807. {
    808.     int arr[] = { 3,2,1 };
    809.     binary_search_tree<int> tree(arr, sizeof(arr) / sizeof(int));
    810.     check(tree.exists(1));
    811.     cout << tree << endl;
    812.     tree.erase(2);
    813.     cout << tree << endl;
    814.     check(!tree.exists(2));
    815.     check(tree.size() == 2);
    816.     check(!tree.empty());
    817.     check(tree.to_string_in_order() == "1 3 ");
    818. }
    819. void test18()
    820. {
    821.     constexpr int length = 2;
    822.     int arr[length] = { 1, 2 };
    823.     binary_search_tree<int> tree(arr, length);
    824.     check(tree.exists(1));
    825.     check(tree.exists(2));
    826.     tree.erase(1);
    827.     check(!tree.exists(1));
    828.     check(tree.exists(2));
    829.     tree.clear();
    830.     check(tree.empty());
    831.     check(tree.size() == 0);
    832.     check(!tree.exists(2));
    833. }
    834. void test19()
    835. {
    836.     constexpr int length = 10;
    837.     int arr[length] = { 5,3,4,1,2,10,8,9,7,6 };
    838.     binary_search_tree<int> tree(arr, length);
    839.     cout << tree << endl << "-------------------" << endl;
    840.     tree.erase(1);
    841.     cout << tree << endl << "-------------------" << endl;
    842.     check(tree.to_string_in_order() == "2 3 4 5 6 7 8 9 10 ");
    843.     tree.erase(2);
    844.     cout << tree << endl << "-------------------" << endl;
    845.     check(tree.to_string_in_order() == "3 4 5 6 7 8 9 10 ");
    846.     tree.erase(3);
    847.     check(tree.to_string_in_order() == "4 5 6 7 8 9 10 ");
    848.     cout << tree << endl << "-------------------" << endl;
    849.     tree.erase(4);
    850.     cout << tree << endl << "-------------------" << endl;
    851.     check(tree.to_string_in_order() == "5 6 7 8 9 10 ");
    852.     tree.erase(5);
    853.     cout << tree << endl << "-------------------" << endl;
    854.     check(tree.to_string_in_order() == "6 7 8 9 10 ");
    855.     tree.erase(6);
    856.     cout << tree << endl << "-------------------" << endl;
    857.     check(tree.to_string_in_order() == "7 8 9 10 ");
    858.     tree.erase(7);
    859.     cout << tree << endl << "-------------------" << endl;
    860.     check(tree.to_string_in_order() == "8 9 10 ");
    861.     tree.erase(8);
    862.     cout << tree << endl << "-------------------" << endl;
    863.     check(tree.to_string_in_order() == "9 10 ");
    864.     tree.erase(9);
    865.     cout << tree << endl << "-------------------" << endl;
    866.     check(tree.to_string_in_order() == "10 ");
    867.     tree.erase(10);
    868.     cout << tree << endl << "-------------------" << endl;
    869.     check(tree.to_string_in_order() == "");
    870. }
    871. void test20()
    872. {
    873.     constexpr int length = 10;
    874.     int arr[length] = { 5,3,4,1,2,10,8,9,7,6 };
    875.     binary_search_tree<int> tree(arr, length);
    876.     cout << tree << endl << "-------------------" << endl;
    877.     tree.erase(10);
    878.     cout << tree << endl << "-------------------" << endl;
    879.     check(tree.to_string_in_order() == "1 2 3 4 5 6 7 8 9 ");
    880.     tree.erase(8);
    881.     cout << tree << endl << "-------------------" << endl;
    882.     check(tree.to_string_in_order() == "1 2 3 4 5 6 7 9 ");
    883. }
    884. void test21()
    885. {
    886.     constexpr int length = 10;
    887.     int arr[length] = { 5,3,4,1,2,10,8,9,7,6 };
    888.     binary_search_tree<int> tree(arr, length);
    889.     cout << tree << endl << "-------------------" << endl;
    890.     tree.erase(5);
    891.     cout << tree << endl << "-------------------" << endl;
    892.     check(tree.to_string_in_order() == "1 2 3 4 6 7 8 9 10 ");
    893. }
    894. void test22()
    895. {
    896.     constexpr int length = 10;
    897.     int arr[length] = { 2,4,6,8,10,1,3,5,7,9 };
    898.     binary_search_tree<int> tree(arr, length);
    899.     check(tree.hight() == 6);
    900.     tree.erase(1);
    901.     check(!tree.exists(1));
    902.     tree.erase(2);
    903.     check(!tree.exists(2));
    904.     tree.erase(3);
    905.     check(!tree.exists(3));
    906.     tree.erase(4);
    907.     check(!tree.exists(4));
    908.     tree.erase(5);
    909.     check(!tree.exists(5));
    910.     check(tree.to_string_in_order() == "6 7 8 9 10 ");
    911.     tree.erase(6);
    912.     check(!tree.exists(6));
    913.     tree.erase(7);
    914.     check(!tree.exists(7));
    915.     tree.erase(8);
    916.     check(!tree.exists(8));
    917.     tree.erase(9);
    918.     check(!tree.exists(9));
    919.     tree.erase(10);
    920.     check(!tree.exists(10));
    921.     check(tree.empty());
    922. }
    923. void test23()
    924. {
    925.     //test equal
    926.     int a[3] = { 15, 12, 14 };
    927.     binary_search_tree<int> tree(a, 3);
    928.     check(tree.hight() == 3);
    929.     cout << "tree:\n" << tree << endl;
    930.     auto tree2 = tree;
    931.     cout << "tree2:\n" << tree2 << endl;
    932.     check(tree2.equal(tree));
    933. }
    934. void test24(binary_search_tree<int>& tree)
    935. {
    936.     cout << "tree:\n" << tree << endl;
    937.     auto tree2 = tree;
    938.     cout << "tree2:\n" << tree2 << endl;
    939.     check(tree2.equal(tree));
    940.     check(tree2 == tree);
    941.     tree.clear();
    942.     cout << tree << endl;
    943.     check(tree2.equal(tree) == false);
    944.     check(tree2 != tree);
    945. }
    946. void test25()
    947. {
    948.     int a[3] = { 15, 12, 14 };
    949.     binary_search_tree<int> tree(a, 3);
    950.     tree.print_in_order_recursive(cout);
    951. }
    952. int main()
    953. {
    954.     test1();//empty
    955.     test2();//test create insert empty size
    956.     test3();
    957.     test4();
    958.     test5();
    959.     test6();
    960.     test7();
    961.     test8();
    962.     test9();
    963.     test10();
    964.     test11();
    965.     test12();
    966.     test13();
    967.     test14();//minmum maxmum
    968.     test15();
    969.     test16();//exists clear erase size empty
    970.     test17();//erase
    971.     test18();//erase
    972.     test19();//erase
    973.     test20();//erase
    974.     test21();//erase
    975.     test22();//erase
    976.     test23();
    977.  
    978.     int maxLength = 0;
    979.     int a[100] = { 15, 12, 14, 13, 16
    980.                  , 34, 23, 24, 22, 21
    981.                  , 20, 19, 18, 17, 35
    982.                  , 36, 37, 38, 39, 40
    983.                  , 41, 0 };
    984.  
    985.     binary_search_tree<int> tree(a, 22);
    986.     check(tree.size() == 22);
    987.     check(tree.empty() == false);
    988.     check(tree.maxmum() == 41);
    989.     check(tree.minmum() == 0);
    990.     test_tree(tree);
    991.  
    992.     binary_search_tree<int> tree1(a, 3);
    993.     test_tree(tree1);
    994.  
    995.     test24(tree);//test copy
    996.     test25();//print
    997.  
    998.     return 0;
    999. }

    正确输出

    1. line:725 Pass
    2. line:726 Pass
    3. line:727 Pass
    4. line:733 Pass
    5. line:734 Pass
    6. line:735 Pass
    7. line:741 Pass
    8. line:742 Pass
    9. line:743 Pass
    10. line:749 Pass
    11. line:750 Pass
    12. line:751 Pass
    13. line:758 Pass
    14. line:759 Pass
    15. line:760 Pass
    16. line:767 Pass
    17. line:768 Pass
    18. line:769 Pass
    19. line:776 Pass
    20. line:777 Pass
    21. line:778 Pass
    22. line:785 Pass
    23. line:786 Pass
    24. line:787 Pass
    25. line:794 Pass
    26. line:796 Pass
    27. line:797 Pass
    28. line:804 Pass
    29. line:806 Pass
    30. line:807 Pass
    31. line:814 Pass
    32. line:816 Pass
    33. line:817 Pass
    34. line:818 Pass
    35. line:825 Pass
    36. line:827 Pass
    37. line:828 Pass
    38. line:829 Pass
    39. line:836 Pass
    40. line:837 Pass
    41. line:838 Pass
    42. line:845 Pass
    43. line:846 Pass
    44. line:847 Pass
    45. line:854 Pass
    46. line:855 Pass
    47. line:862 Pass
    48. line:864 Pass
    49. line:865 Pass
    50. line:871 Pass
    51. 3
    52.  --2
    53.      --1
    54.  
    55. 3
    56.  --1
    57.  
    58. line:875 Pass
    59. line:876 Pass
    60. line:877 Pass
    61. line:878 Pass
    62. line:885 Pass
    63. line:886 Pass
    64. line:888 Pass
    65. line:889 Pass
    66. line:891 Pass
    67. line:892 Pass
    68. line:893 Pass
    69.  --10
    70.          --9
    71.      --8
    72.          --7
    73.              --6
    74. 5
    75.      --4
    76.  --3
    77.          --2
    78.      --1
    79.  
    80. -------------------
    81.  --10
    82.          --9
    83.      --8
    84.          --7
    85.              --6
    86. 5
    87.      --4
    88.  --3
    89.      --2
    90.  
    91. -------------------
    92. line:903 Pass
    93.  --10
    94.          --9
    95.      --8
    96.          --7
    97.              --6
    98. 5
    99.      --4
    100.  --3
    101.  
    102. -------------------
    103. line:906 Pass
    104. line:908 Pass
    105.  --10
    106.          --9
    107.      --8
    108.          --7
    109.              --6
    110. 5
    111.  --4
    112.  
    113. -------------------
    114.  --10
    115.          --9
    116.      --8
    117.          --7
    118.              --6
    119. 5
    120.  
    121. -------------------
    122. line:912 Pass
    123. 10
    124.      --9
    125.  --8
    126.      --7
    127.          --6
    128.  
    129. -------------------
    130. line:915 Pass
    131. 10
    132.      --9
    133.  --8
    134.      --7
    135.  
    136. -------------------
    137. line:918 Pass
    138. 10
    139.      --9
    140.  --8
    141.  
    142. -------------------
    143. line:921 Pass
    144. 10
    145.  --9
    146.  
    147. -------------------
    148. line:924 Pass
    149. 10
    150.  
    151. -------------------
    152. line:927 Pass
    153.  
    154. -------------------
    155. line:930 Pass
    156.  --10
    157.          --9
    158.      --8
    159.          --7
    160.              --6
    161. 5
    162.      --4
    163.  --3
    164.          --2
    165.      --1
    166.  
    167. -------------------
    168.      --9
    169.  --8
    170.      --7
    171.          --6
    172. 5
    173.      --4
    174.  --3
    175.          --2
    176.      --1
    177.  
    178. -------------------
    179. line:940 Pass
    180.  --9
    181.      --7
    182.          --6
    183. 5
    184.      --4
    185.  --3
    186.          --2
    187.      --1
    188.  
    189. -------------------
    190. line:943 Pass
    191.  --10
    192.          --9
    193.      --8
    194.          --7
    195.              --6
    196. 5
    197.      --4
    198.  --3
    199.          --2
    200.      --1
    201.  
    202. -------------------
    203.  --10
    204.          --9
    205.      --8
    206.          --7
    207. 6
    208.      --4
    209.  --3
    210.          --2
    211.      --1
    212.  
    213. -------------------
    214. line:953 Pass
    215. line:960 Pass
    216. line:962 Pass
    217. line:964 Pass
    218. line:966 Pass
    219. line:968 Pass
    220. line:970 Pass
    221. line:971 Pass
    222. line:973 Pass
    223. line:975 Pass
    224. line:977 Pass
    225. line:979 Pass
    226. line:981 Pass
    227. line:982 Pass
    228. line:989 Pass
    229. tree:
    230. 15
    231.      --14
    232.  --12
    233.  
    234. tree2:
    235. 15
    236.      --14
    237.  --12
    238.  
    239. line:993 Pass
    240. line:1047 Pass
    241. line:1048 Pass
    242. line:1049 Pass
    243. line:1050 Pass
    244. test_tree:
    245.                                  --41
    246.                              --40
    247.                          --39
    248.                      --38
    249.                  --37
    250.              --36
    251.          --35
    252.      --34
    253.              --24
    254.          --23
    255.              --22
    256.                  --21
    257.                      --20
    258.                          --19
    259.                              --18
    260.                                  --17
    261.  --16
    262. 15
    263.      --14
    264.          --13
    265.  --12
    266.      --0
    267. tree size : 22
    268. tree max length between node 14
    269. 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
    270. 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
    271. 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
    272. 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
    273. min element : 0
    274. max element : 41
    275.  
    276. test_tree:
    277. 15
    278.      --14
    279.  --12
    280. tree size : 3
    281. tree max length between node 2
    282. print_in_order_nonrecursive : 12 14 15
    283. print_element_order by order: 12 14 15
    284. print_post_order_nonrecursive : 14 12 15
    285. print_pre_order_nonrecursive : 15 12 14
    286. min element : 12
    287. max element : 15
    288.  
    289. tree:
    290.                                  --41
    291.                              --40
    292.                          --39
    293.                      --38
    294.                  --37
    295.              --36
    296.          --35
    297.      --34
    298.              --24
    299.          --23
    300.              --22
    301.                  --21
    302.                      --20
    303.                          --19
    304.                              --18
    305.                                  --17
    306.  --16
    307. 15
    308.      --14
    309.          --13
    310.  --12
    311.      --0
    312.  
    313. tree2:
    314.                                  --41
    315.                              --40
    316.                          --39
    317.                      --38
    318.                  --37
    319.              --36
    320.          --35
    321.      --34
    322.              --24
    323.          --23
    324.              --22
    325.                  --21
    326.                      --20
    327.                          --19
    328.                              --18
    329.                                  --17
    330.  --16
    331. 15
    332.      --14
    333.          --13
    334.  --12
    335.      --0
    336.  
    337. line:1000 Pass
    338. line:1001 Pass
    339.  
    340. line:1004 Pass
    341. line:1005 Pass
    342. 12 14 15 Memory leak report:
    343. No memory leak.
  • 相关阅读:
    Django中的Cookie和Session
    Redis详解（一）
    移动硬盘丢了怎么找回来呢?
    FPGA SPI采集ADC7606数据
    什么是AB实验？能解决什么问题？终于有人讲明白了
    六种常用排序方式详解（C++实现）
    ceph存储系统
    安装虚拟机（VMware）保姆级教程及配置虚拟网络编辑器和安装WindowsServer以及宿主机访问虚拟机和配置服务器环境
    MySQL的日志管理与备份、恢复
    【机器学习笔记】
  • 原文地址：https://blog.csdn.net/ClamReason/article/details/132600649