一.二叉搜索树的基本概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则 左子树 上所有节点的值都 小于 根节点的值
- 若它的右子树不为空，则 右子树 上所有节点的值都 大于 根节点的值
- 它的 左右子树 也分别为二叉搜索树 ；
二.增删查改基本操作
//结点模板 template<class K> struct BSTreeNode { BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; BSTreeNode(const K& key) :_left(nullptr) ,_right(nullptr) ,_key(key) {} }; //在二叉搜索树模板中 typedef BSTreeNode<K> Node;
1.二叉搜索树的查找（分析＆代码演示）
分析
- 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找
- 最多查找高度次 ，走到到空，还没找到，这个值不存在。
代码演示
//查找操作 bool Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key < key)//从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找 { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return true; } } return false;//最多查找高度次 ，走到到空，还没找到，这个值不存在。 }
2.二叉搜索树的插入（分析＆代码演示）
分析
- 树为空，则直接新增节点，赋值给root指针
- 树不空， 按二叉搜索树性质的查找方式（前后指针） 找到插入位置，插入新节点
代码演示
//插入操作 bool Insert(const K& key) { //树为空，则直接新增节点，赋值给root指针 if (_root == nullptr) { _root = new Node(key); return true; } //树不空， 按二叉搜索树性质的查找方式（前后指针） 找到插入位置，插入新节点 Node* parent = nullptr;//后指针 Node* cur = _root;//前指针 while (cur) { if (cur->_key < key)//比keycur的_key大，往右走 { parent = cur; cur = cur->_right; } else if(cur->_key > key)//比keycur的_key小，往左走 { parent = cur; cur = cur->_left; } else { return false; } } //cur走到空了，开始给插入的key值创建结点，根据其比后一个结点（parent）大还是小，决定其是插在左还是右 cur = new Node(key); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; }
3.二叉搜索树的删除【※核心重点】（分析＆代码演示）
分析
- 首先查找元素是否在二叉搜索树中，如果不存在，则返回
- 否则要删除的结点可能分下面四种情况：
- 要删除的结点无孩子结点
- 要删除的结点只有左孩子结点
- 要删除的结点只有右孩子结点
- 要删除的结点有左、右孩子结点
- 对上面四种情况整理后(1与2，3分别结合)，剩下下面2种情况（直接删除，替换法），分出3种具体情况（直接删除占两种）：
- 直接删除情况： 只有左/右/无孩子结点（无孩子，只有一个孩子）
（双亲结点指向被删除节点的左还是右————取决于被删除节点是其双亲节点的左还是右节点）- 情况1：被删除节点是其双亲节点的左节点，删除该结点且使被删除节点的双亲结点指向被删除节点的 左孩子 结点
- 情况2：被删除节点是其双亲节点的右节点，删除该结点且使被删除节点的双亲结点指向被删除结点的 右孩子 结点
- 还要考虑结点为根结点情况：
- 替换法情况：【※核心难点】 （有两个孩子）
- 情况3 ：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题
- 分析：要 找到左子树的最大(右)结点，或者 右子树的最小(左)结点（下图演示中是找到左子树的最大结点）
- 具体过程分析：
- 设置前后指针，留一个cur指针指向要删除结点，parent指针跟着LeftMax指针向下逐个移动
- 找到leftMax以后，交换其和cur的数值，（收完尾后，最后一步再将指针也一同转移）
- 要分为两种情况（如下图所示） (1) leftMax指针的左指针为空，(2) leftMax指针的左指针不为空
（为什么不用讨论右指针呢？因为leftMax的右指针必定为空，否则leftMax会继续向下移动）- 因为采用的是前后指针法，所以这时留下的后指针（parent）就对应指向leftMax的左/右结点
- 最后将cur指针指向leftMax，leftMax动不动无所谓
代码演示
//删除操作 bool Erase(const K& key) { Node* parent = nullptr;//后指针 Node* cur = _root;//前指针 while (cur) { //通过二叉搜索树规则向下查找 if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } //直接删除情况：只有左/右/无孩子结点 //（双亲结点指向被删除节点的左还是右————取决于被删除节点是其双亲节点的左还是右节点） else // 找到了 { // 左为空 if (cur->_left == nullptr) { if (cur == _root) { _root = cur->_right; } else { if (parent->_right == cur)//被删除节点是其双亲节点的右节点 { parent->_right = cur->_right;//删除该结点且使被删除节点的双亲结点指向被删除结点的 右孩子 结点 } else//被删除节点是其双亲节点的左节点 { parent->_left = cur->_right;//删除该结点且使被删除节点的双亲结点指向被删除结点的 左孩子 结点 } } } // 右为空 else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else { if (parent->_right == cur) { parent->_right = cur->_left; } else { parent->_left = cur->_left; } } } // 替换法情况：左右都不为空 else { // 找替代节点 Node* parent = cur; Node* leftMax = cur->_left; while (leftMax->_right) { parent = leftMax; leftMax = leftMax->_right; } swap(cur->_key, leftMax->_key); if (parent->_left == leftMax) { parent->_left = leftMax->_left; } else { parent->_right = leftMax->_left; } cur = leftMax; } delete cur; return true; } } return false; }
4.二叉搜索树的中序遍历（分析＆代码演示）
分析
- 中序遍历要从通过模板实例化的树中调用中序遍历函数
- 需要传根结点指针，但是 根结点指针是在private域中，域外不能直接传一个根结点指针 ，所以要引入_InOrder函数，在二叉搜索树模板中 再次封装一层
代码演示
void TestBSTree1() { int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 }; BSTree<int> t; for (auto e : a) { t.Insert(e); } t.InOrder(); //需要传根结点指针，但是根结点指针是在private域中，域外不能直接传一个根结点指针， //所以要引入_InOrder函数，在二叉搜索树模板中再次封装一层 }
//中序遍历——————————————————————————————————————————为了解决中序要传入根节点的问题，引入_InOrder函数 void InOrder() { _InOrder(_root); cout << endl; } void _InOrder(Node* root) { if (root == NULL) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); }
三.二叉搜索树的性能问题：需要AVL树…红黑树…
- 插入和删除操作都必须先 查找，查找效率代表了二叉搜索树中各个操作的性能
- 当二叉搜索树 退化为单支时，其效率为O(N)，二叉搜索树的性能就失去了
- 对二叉搜索树进行改进后，得到的AVL树红黑树效率为 Log(N)
四.二叉搜索树的完整实现代码演示
//结点模板 template<class K> struct BSTreeNode { BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; BSTreeNode(const K& key) :_left(nullptr) ,_right(nullptr) ,_key(key) {} }; //二叉搜索树类模板 template<class K> class BSTree { typedef BSTreeNode<K> Node; public: //初始化列表 BSTree() :_root(nullptr) {} //查找操作 bool Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return true; } } return false; } //插入操作 bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if(cur->_key > key) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(key); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; } //删除操作 bool Erase(const K& key) { Node* parent = nullptr;//后指针 Node* cur = _root;//前指针 while (cur) { //通过二叉搜索树规则向下查找 if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } //直接删除情况：只有左/右/无孩子结点 //（双亲结点指向被删除节点的左还是右————取决于被删除节点是其双亲节点的左还是右节点） else // 找到了 { // 左为空 if (cur->_left == nullptr) { if (cur == _root) { _root = cur->_right; } else { if (parent->_right == cur)//被删除节点是其双亲节点的右节点 { parent->_right = cur->_right;//删除该结点且使被删除节点的双亲结点指向被删除结点的 右孩子 结点 } else//被删除节点是其双亲节点的左节点 { parent->_left = cur->_right;//删除该结点且使被删除节点的双亲结点指向被删除结点的 左孩子 结点 } } } // 右为空 else if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else { if (parent->_right == cur) { parent->_right = cur->_left; } else { parent->_left = cur->_left; } } } // 替换法情况：左右都不为空 else { // 找替代节点 Node* parent = cur; Node* leftMax = cur->_left; while (leftMax->_right) { parent = leftMax; leftMax = leftMax->_right; } swap(cur->_key, leftMax->_key); if (parent->_left == leftMax) { parent->_left = leftMax->_left; } else { parent->_right = leftMax->_left; } cur = leftMax; } delete cur; return true; } } return false; } //中序遍历——————————————————————————————————————————为了解决中序要传入根节点的问题，引入_InOrder函数 void InOrder() { _InOrder(_root); cout << endl; } void _InOrder(Node* root) { if (root == NULL) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } private: Node* _root; }; void TestBSTree1() { int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 }; BSTree<int> t; for (auto e : a) { t.Insert(e); } t.InOrder(); t.Erase(4); t.InOrder(); t.Erase(6); t.InOrder(); t.Erase(7); t.InOrder(); t.Erase(3); t.InOrder(); for (auto e : a) { t.Erase(e); } t.InOrder(); }
