一、二叉搜索树概念
二叉搜索树也叫做二叉排序树，它要么是一棵空树，要么具有以下性质:
（1）若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
（2）若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
（3）它的左右子树也分别为二叉搜索树
如下就是二叉搜索树，对于任何一个节点，它的左子树的所有节点值都比它小，它的右子树的所有节点值都比它大：
int a[] = {9,6,15,4,13,5,1,20,8,27};
总结：在左子树值比根小，右子树值比根大。 当树走中序遍历时，序列都是有序的。
二叉搜索树的结构定义：
1. #include<iostream> 2. using namespace std; 3. 4. //树的节点可以支持多种类型 5. template<class K> 6. 7. //树节点结构 8. struct BSTreeNode 9. { 10. BSTreeNode<K>* _left;//左指针 11. BSTreeNode<K>* _right;//右指针 12. K _key;//值 13. 14. //树节点构造函数 15. BSTreeNode(const K& key) 16. :_left(nullptr) 17. ,_right(nullptr) 18. ,_key(key) 19. {} 20. }; 21. 22. template<class K> 23. class BStree//树结构 24. { 25. typedef BSTreeNode<K> Node; 26. public: 27. 28. //构造函数只需要将根初始化为空就行了 29. BSTree() 30. :_root(nullptr) 31. {} 32. 33. private: 34. Node* _root;//根 35. };
二、二叉搜索树操作（非递归）
1.二叉搜索树的查找（非递归）
二份查找借助排序查找，二叉搜索树借助结构
查找的时间复杂度，最坏查找高度次，就可以确认一个值在不在树中：
（1）当树接近完全二叉树或满二叉树 ，时间复杂度为O(N):
（2）查找的时间复杂度最坏为O(N)，如下这种情况：
因此二叉搜索树在极端情况下没办法保证效率。
（1）查找
查找比较简单：
①key比当前节点值大，向左走
②key比当前节点值小，向右走
③key等于当前节点值，找到了
1. //查找 2. Node* Find(const K& key) 3. { 4. Node* cur = _root; 5. if (cur->_key > key)//比当前节点小，就向左走 6. { 7. cur = cur->_left; 8. } 9. else if (cur->_key < key)//比当前节点大，就向右走 10. { 11. cur = cur->_right; 12. } 13. else 14. { 15. return cur;//找到了，返回 16. } 17. 18. return nullptr; 19. }
（2）中序遍历
由于根节点的访问限定符是私有的，那么在main函数中要终须遍历一棵树时，就无法将二叉搜索树的对象根节点传给中序遍历，因为类外面访问不到私有成员。
因此可以这样考虑：这个二叉搜索树对象是有根节点的，可以考虑在里面套一层，给套在里面的函数传参_root ，去递归调用自己:
1. //内层函数使用_root 2. void _Inorder(Node* root) 3. { 4. if (root == nullptr) 5. { 6. return; 7. } 8. _Inorder(root->_left);//递归调用自己 9. cout << root->_key << " "; 10. _Inorder(root->_right);//递归调用自己 11. } 12. 13. //先调不传参数的InOrder 14. void InOrder() 15. { 16. //把_root传给子函数，让子函数去使用_root 17. _InOrder(_root); 18. cout << endl; 19. }
2.二叉搜索树的插入（非递归）
插入节点分两步：
（1）找位置
①key比当前节点值大，向左走
②key比当前节点值小，向右走
③key等于当前节点值，该节点值已经存在，插入失败
（2）插入
①key比父亲节点值小就插入父亲左子树
②key比父亲节点值大就插入父亲右子树
由于插入后，要将节点链接到树中，因此要定义parent节点，用来链接新节点：
1. //插入 2. bool Insert(const K& key) 3. { 4. //1.树为空 5. if (_root == nullptr) 6. { 7. _root = new Node(key); 8. return true; 9. } 10. 11. //2.树不为空 非递归方式，两步：（1）找位置 （2）插入节点 12. //(1)找位置 13. Node* parent = nullptr; 14. Node* cur = _root; 15. while (cur) 16. { 17. if (cur->_key < key)//比当前节点大，就往右走 18. { 19. parent = cur;//记录当前节点的父亲位置 20. cur = cur->_right; 21. } 22. else if (cur->_key > key)//比当前节点小，就向左走 23. { 24. parent = cur;//记录当前节点的父亲位置 25. cur = cur->_left; 26. } 27. else 28. { 29. return false;//树里面已经有这个节点了，就返回flase 30. } 31. } 32. 33. //(2)插入节点 34. cur = new Node(key); 35. if(parent->_key > key)//比父亲节点值小就连接在父亲左子树 36. { 37. parent->_left = cur; 38. } 39. else 40. { 41. parent->_right = cur;//比父亲节点值大就连接在父亲右子树 42. } 43. return true; 44. }
3.二叉搜索树的删除（非递归）
（1）找位置
①key比当前节点值大，向左走
②key比当前节点值小，向右走
③key等于当前节点值，找到了，准备删除
（2）删除，有两种删除方法：非递归和递归
非递归删除:
①该节点没有孩子，即该节点是叶子节点，删除节点后把父亲指向自己的指针置空
②该节点有一个孩子，就把该节点的孩子节点的链接给该节点的父亲，顶替自己的位置，①可以当成②的特殊情况
③该节点有两个孩子，找比它自己的左孩子大，比它自己的右孩子小的节点替换它（也就是拿它的左子树的最大节点或右子树的最小节点替换它），替换之后，该节点就只有一个孩子或没有孩子了，就变成①或②了。
1. //删除 2. bool Erase(const K& key) 3. { 4. Node* parent = nullptr; 5. Node* cur = _root; 6. while (cur) 7. { 8. if (cur->_key > key)//比当前节点小，就往左走 9. { 10. parent = cur;//记录父亲位置 11. cur = cur->_left; 12. } 13. else if (cur->_key < key)//比当前节点大，就往右走 14. { 15. parent = cur;//记录父亲位置 16. cur = cur->_right; 17. } 18. else//找到了，要删除 19. { 20. //1.删除的是叶子节点, 删除节点后把父亲指向自己的指针置空 21. //2.删除的是有一个孩子的节点,就把它的孩子节点的链接给它的父亲，顶替自己的位置 22. //3.删除的是有两个孩子的节点，找比它自己的左孩子大，比它自己的右孩子小的节点替换它， 23. //也就是它的左子树的最大节点或右子树的最小节点替换它，它就只有一个孩子或没有孩子了 24. 25. //第1可以当成第2去处理，当前节点的父亲节点指向空就可以了 26. 27. if (cur->_left == nullptr)//cur左为空，就让父亲指向cur的右 28. { 29. //如果要删除根，直接让根的右孩子做根 30. if (cur == _root) 31. { 32. _root = cur->_right; 33. } 34. else 35. { 36. if (parent->_left == cur)//当cur是父亲的左时，就让父亲的左指向cur的右 37. { 38. parent->_left = cur->_right; 39. } 40. else//当cur是父亲的右时，就让父亲的右指向cur的右 41. { 42. parent->_right = cur->_right; 43. } 44. } 45. 46. delete cur; 47. } 48. else if (cur->_right == nullptr)//cur右为空，就让父亲指向cur的左 49. { 50. //如果要删除根，直接让根的右孩子做根 51. if (cur == _root) 52. { 53. _root = cur->_right; 54. } 55. else 56. { 57. if (parent->_left == cur)//当cur是父亲的左时，就让父亲的左指向cur的左 58. { 59. parent->_left = cur->_left; 60. } 61. else//当cur是父亲的右时，就让父亲的右指向cur的左 62. { 63. parent->_right = cur->_left; 64. } 65. } 66. 67. delete cur;//删除 68. } 69. else//左右都不为空，替换法删除 70. { 71. //找右子树最左节点 当右子树的左孩子不为空时就继续遍历 72. Node* minRight = cur->_right; 73. Node* minParent = cur;//这里不要初始化成null，否则左为空时，minParent->_left就会崩掉 74. 75. //当左不为空时，就一直向左走，直到找到右子树最左节点 76. while (minRight->_left) 77. { 78. minParent = minRight; 79. minRight = minRight->_left; 80. } 81. 82. //保存替换节点的值 83. cur->_key = minRight->_key; 84. 85. //删除替换节点 86. if (minParent->_left == minRight)//如果右子树最左节点是minParent的左，那就让minParent的左指向右子树最左节点的右 87. { 88. minParent->_left = minRight->_right; 89. } 90. else//如果右子树最左节点是minParent的右，那就让minParent的右指向右子树最左节点的右 91. { 92. minParent->_right = minRight->_right; 93. } 94. delete minRight;//删除 95. } 96. 97. return true; 98. } 99. 100. } 101. return false;//cur不存在，直接返回 102. }
递归删除：
相对于非递归，只需要修改找到了要修改的代码：找到了后不需要管cur到底左为空、右为空、还是左右都不为空
① 找要删除节点的右子树的最小节点并把它的值保存起来
② 删除右子树的最小节点
③ 把要删除的节点值替换成右子树的最小节点值
1. else//左右都不为空，替换法删除 2. { 3. //找右子树最小节点 4. Node* minRight = cur->_right; 5. while (minRight->_left) 6. { 7. minRight = minRight->_left; 8. } 9. 10. //用min保存右子树最小节点的值 11. K min = minRight->_key; 12. 13. //递归调用自己去替换删除节点，一定会走到左为空的情况处理 14. this->Erase(min); 15. 16. //删除完毕替换节点之后，把cur的值替换成min 17. cur->_key = min; 18. }
