三、二叉搜索树操作（递归）
理解了非递归操作以后， 递归操作就很简单了：
1. #include<iostream> 2. using namespace std; 3. 4. //树的节点可以支持多种类型 5. template<class K> 6. //树节点结构 7. struct BSTreeNode 8. { 9. BSTreeNode<K>* _left;//左指针 10. BSTreeNode<K>* _right;//右指针 11. K _key;//值 12. 13. //构造函数 14. BSTreeNode(const K& key) 15. :_left(nullptr) 16. , _right(nullptr) 17. , _key(key) 18. {} 19. }; 20. 21. template<class K> 22. class BStree//树结构 23. { 24. typedef BSTreeNode<K> Node; 25. public: 26. //递归查找 27. Node* FindR(const K& key) 28. { 29. return _FindR(_root, key); 30. } 31. 32. //递归插入 33. bool InsertR(const K& key) 34. { 35. return _InsertR(_root, key); 36. } 37. 38. //递归删除 39. bool EraseR(const K& key) 40. { 41. return _EraseR(_root, key); 42. } 43. private: 44. Node* _root; 45. };
由于_root是私有的，可以把递归子函数查找、插入、删除都定义成私有的
1.二叉搜索树的查找（递归）
递归查找：
1. private: 2. //查找 3. Node* _FindR(Node* root, const K& key) 4. { 5. if (root == nullptr)//没找到 6. { 7. return nullptr; 8. } 9. 10. if (key < root->_key)//到左子树去找 11. { 12. FindR(root->_left, key); 13. } 14. else if (key > root->_key)//到右子树去找 15. { 16. FindR(root->_right, key); 17. } 18. else//找到了 19. { 20. return root; 21. } 22. }
2.二叉搜索树的插入（递归）
递归插入：当找到的位置为空时才插入
1. //插入 加了&，root是_root的别名，修改root就直接修改到上一层调用，不用找父亲 2. bool _InsertR(Node*& root, const K& key) 3. { 4. if (root == nullptr)//找到位置了 5. { 6. root = new Node(key); 7. return true; 8. } 9. if (key < root->_key)//到左子树去找位置 10. { 11. _InsertR(root->_left, key); 12. } 13. else if (key > root->_key)//到右子树去找位置 14. { 15. _InsertR(root->_right, key); 16. } 17. else//已存在，无需插入 18. { 19. return false; 20. } 21. }
3.二叉搜索树的删除（递归）
递归删除：和二叉树的删除（非递归）一样，找到后的删除也有两种方式，递归和非递归
找到后的非递归删除：
1. //插入 加了&，root是_root的别名，修改root就直接修改到上一层调用，不用找父亲 2. bool _EraseR(Node*& root, const K& key) 3. { 4. if (root == nullptr)//没找到 5. { 6. return false; 7. } 8. if (key < root->_key)//到左子树去找 9. { 10. _EraseR(root->_left, key); 11. } 12. else if (key > root->_key)//到右子树去找 13. { 14. _EraseR(root->_right, key); 15. } 16. else 17. { 18. //找到了，root就是要删除的节点 19. if (root->_left == nullptr)//root左为空 20. { 21. Node* del = root; 22. root = root->_right; 23. delete del; 24. } 25. else if (root->_right == nullptr)//root右为空 26. { 27. Node* del = root; 28. root = root->_left; 29. delete del; 30. } 31. else//root左右都不为空 32. { 33. //找到右子树最左节点替换 34. Node* minParent = root; 35. Node* minRight = root->_right; 36. 37. while (minRight->_left) 38. { 39. minParent = minRight; 40. minRight = minRight->_left; 41. } 42. 43. //保存替换节点的值 44. cur->_key = minRight->_key; 45. 46. //链接 47. if (minParent->_left == minRight) 48. { 49. minParent->_left = minRight->_right; 50. } 51. else 52. { 53. minParent->_right = minRight->_right; 54. } 55. 56. //删除 57. delete minRight; 58. } 59. return true; 60. } 61. }
找到后的递归删除：
1. else//root左右都不为空 2. { 3. //找右子树最左节点 4. Node* minRight = root->_right; 5. while (minRight->_left) 6. { 7. minRight = minRight->_left; 8. } 9. 10. //保存右子树最左节点的值 11. K min = minRight->_key; 12. 13. //使用递归方法删除右子树最左节点 14. _Erase(root->_right, min); 15. }
四、二叉搜索树的默认成员函数
现在还剩下二叉搜索树的构造、拷贝构造、赋值运算符重载、析构函数。
1.构造
前面已经写过构造函数了, 即只需要把根初始化为空就行了:
1. public: 2. //构造函数需要将根初始化为空就行了 3. BSTree() 4. :_root(nullptr) 5. {}
2.拷贝构造
拷贝构造利用递归调用子函数不断拷贝节点:
1. //拷贝构造 2. BSTree(const BSTree<K>& t) 3. { 4. _root = t.copy(t._root); 5. }
在子函数处:
1. Node* _copy(Node* root) 2. { 3. if (root == nullptr)//如果根为空，直接返回 4. { 5. return; 6. } 7. 8. Node* copyNode = new Node(root->_key);//创建根节点 9. copyNode->_left = _copy(root->_left);//递归拷贝左子树节点 10. copyNode->_right = _copy(root->_right);//递归拷贝右子树节点 11. 12. return copyNode;//返回根 13. }
3.赋值运算符重载
借助拷贝构造用现代写法写:
1. //赋值运算符重载(现代写法) 2. BSTree& operator=(const BSTree<K>& t) 3. { 4. swap(_root,t._root); 5. return *this; 6. }
4.析构
递归调用子函数去析构
1. //析构 2. ~BSTree() 3. { 4. _Destroy(_root); 5. _root = nullptr; 6. }
在子函数处:
1. _Destroy(root) 2. { 3. if (root == nullptr) 4. { 5. return; 6. } 7. _Destroy(root->_left); 8. _Destroy(root->_right); 9. delete root; 10. }
