右为空
右为空时，使用parent节点去接收cur的左子树，但是还需判断下cur的左子树节点在parent的左子树还是右子树
当cur作为根节点时，此时parent为NULL,就会报错
所以要把cur作为根节点的情况单独处理
把cur的左子树的节点作为根，然后直接删除cur节点
删除节点有左孩子和右孩子节点
当找到minright时，minright在9节点位置上，minright可以替代cur的位置，替cur照顾两个孩子，但是minright本身也是有可能有孩子的，所以还需要找到minright的上一个父节点parent，同时需要判断下minright节点是parent节点的左孩子还是有孩子
pminright初始化不能为NULL，若为空，若不进入while循环，则无法更新pminright值，
导致NULL->left，从而报错
，minright不一定是minright的左子树，也有可能是pminright的右子树 ，所以需要判断下
整体代码
//删除 bool Erase(const K& key) { //将第一种和第二种看作一种 Node* parent = nullptr;//记录cur之前的节点 Node* cur = _root; while (cur!=NULL) { if (cur->_key > key) { cur = cur->_left; } else if (cur->_key < key) { cur = cur->_right; } else { //相等则说明数据存在，要删除 //1.左为空 if (cur->_left == nullptr) { if (cur == _root)//当cur作为根节点时 { _root = cur->_right; } else { if (parent->_left == cur)//若cur在parent节点的左边 { parent->_left = cur->_right; } else//若cur在parent节点的右边 { parent->_right = cur->_right; } } delete cur; } //2.右为空 else if (cur->_right == nullptr) { if (cur == _root)//当cur作为根节点时 { _root = cur->_left; } else { if (parent->_left == cur)//若cur在parent节点的左边 { parent->_left = cur->_left; } else//若cur在parent节点的右边 { parent->_right = cur->_left; } } delete cur; } //3.请保姆 else { //寻找右子树的最小节点 Node* pminright = cur; Node* minright = cur->_right;//右子树的最小节点 //最左节点 while (minright->_left)//找到最小节点 { pminright = minright;//记录minright之前的节点 minright = minright->_left; } cur->_key = minright->_key; //由于不知道minright是pminright的左子树还是右子树 ，所以需要判断下 //再将minright的右子树pminright if (pminright->_left == minright) { pminright->_left = minright->_right; } else { pminright->_right = minright->_right; } delete minright; } return true; } } //说明要删除的数据不存在 return false; }
二叉搜索树的实现 (递归)
递归实现，全都使用了函数嵌套的方式，与非递归的中序遍历的方式相同，是为了使用_root这个定义在类中的成员变量
查找
bool _FindR(Node * root, const K & key) { if (root == nullptr) { return false; } if (root->_key == key) { return true; } if (root->_key < key) { retrun _FindR(root->_right, key); } else { retrun _FindR(root->_left, key); } } bool FindR(const K & key) { return _FindR(_root, key); }
插入
bool _InsertR(Node*&root,const K&key)//插入 { if (root == nullptr) { root = new Node(key); return true; } if (root->_key < key) { return _InsertR(root->_right, key); } else if(root->_key > key) { return _InsertR(root->_left, key); } else { return false; } } bool InsertR(const K& key) { return _InsertR(_root,key); }
通过引用的方式解决遇见NULL连接新节点的问题
因为引用的原因，所以root==NULL进入if判断时， root作为上一个节点左指针的别名，相当于 root->_left 新创建了一个节点，直接与二叉树连接起来了
就不用像非递归一样考虑创建节点后，与它的上一个节点连接的问题
删除
删除节点有左孩子和右孩子节点
bool _EraseR(Node*&root,const K& key) { if (root == nullptr) { return false; } if (root->_key < key) { return EraseR(root->_right, key); } else if (root->_key > key) { return EraseR(root->_left, key); } else { //开始删除 Node* del= root;//保存要删除的节点 if (root->_left == nullptr)//左为空 { root = root->_right; } else if (root->_right == nullptr)//右为空 { root = root->_left; } else { //替代法 Node* maxleft = root->_left; //在左子树中寻找最右 作为左子树最大节点 while (maxleft->_right != NULL) { maxleft = maxleft->_right; } swap(maxleft, root); return EeaseR(root->_left, key); } delete del; return true; } } bool EraseR(const K&key) { return _EraseR(_root,key); }
二叉搜索树实现的整体代码
#pragma once #include<iostream> using namespace std; template <class K> //BSTree -- BinarySearchTree 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()//析构 { Destroy(_root); _root = nullptr; } /*BSTree(const BSTree<K>& t) { } void cpoy(Node*root) { }*/ //插入 bool Insert(const K& key) { if (_root == NULL)//若root根节点为nullptr { _root = new Node(key); return true; } Node* cur = _root; Node* parent = nullptr;//用于接收cur之前的节点 while (cur != NULL) { if (cur->_key > key)//若插入的值比cur值小 { parent = cur; cur = cur->_left; } else if (cur->_key < key)//若插入的值比cur值大 { parent = cur; cur = cur->_right; } else//若相等，则直接返回false { return false; } } //遇见空指针，连接新节点 //由于不知道parent的左还是右连接key，所以需要判断 cur = new Node(key); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; } //中序遍历 void inorder() { _inorder(_root); } void _inorder(Node*root) { if (root == NULL) { return; } _inorder(root->_left);//左 cout << root->_key << " ";//根 _inorder(root->_right);//右 } //查找 bool Find(const K& key) { Node* cur = _root; while (cur != NULL) { if (cur->_key > key) { cur = cur->_left; } else if (cur->_key < key) { cur = cur->_right; } else { return true; } } return false; } //删除 bool Erase(const K& key) { //将第一种和第二种看作一种 Node* parent = nullptr;//记录cur之前的节点 Node* cur = _root; while (cur!=NULL) { if (cur->_key > key) { cur = cur->_left; } else if (cur->_key < key) { cur = cur->_right; } else { //相等则说明数据存在，要删除 //1.左为空 if (cur->_left == nullptr) { if (cur == _root)//当cur作为根节点时 { _root = cur->_right; } else { if (parent->_left == cur)//若cur在parent节点的左边 { parent->_left = cur->_right; } else//若cur在parent节点的右边 { parent->_right = cur->_right; } } delete cur; } //2.右为空 else if (cur->_right == nullptr) { if (cur == _root)//当cur作为根节点时 { _root = cur->_left; } else { if (parent->_left == cur)//若cur在parent节点的左边 { parent->_left = cur->_left; } else//若cur在parent节点的右边 { parent->_right = cur->_left; } } delete cur; } //3.请保姆 else { //寻找右子树的最小节点 Node* pminright = cur; Node* minright = cur->_right;//右子树的最小节点 //最左节点 while (minright->_left)//找到最小节点 { pminright = minright;//记录minright之前的节点 minright = minright->_left; } cur->_key = minright->_key; //由于不知道minright是pminright的左子树还是右子树 ，所以需要判断下 //再将minright的右子树pminright if (pminright->_left == minright) { pminright->_left = minright->_right; } else { pminright->_right = minright->_right; } delete minright; } return true; } } //说明要删除的数据不存在 return false; } //--------- 递归 bool _FindR(Node * root, const K & key)//查找 { if (root == nullptr) { return false; } if (root->_key == key) { return true; } if (root->_key < key) { return _FindR(root->_right, key); } else { return _FindR(root->_left, key); } } bool FindR(const K & key) { return _FindR(_root, key); } bool _InsertR(Node*&root,const K&key)//插入 { if (root == nullptr) { root = new Node(key); return true; } if (root->_key < key) { return _InsertR(root->_right, key); } else if(root->_key > key) { return _InsertR(root->_left, key); } else { return false; } } bool InsertR(const K& key) { return _InsertR(_root,key); } bool _EraseR(Node*&root,const K& key) { if (root == nullptr) { return false; } if (root->_key < key) { return EraseR(root->_right, key); } else if (root->_key > key) { return EraseR(root->_left, key); } else { //开始删除 Node* del= root;//保存要删除的节点 if (root->_left == nullptr)//左为空 { root = root->_right; } else if (root->_right == nullptr)//右为空 { root = root->_left; } else { //替代法 Node* maxleft = root->_left; //在左子树中寻找最右 作为左子树最大节点 while (maxleft->_right != NULL) { maxleft = maxleft->_right; } swap(maxleft, root); return EeaseR(root->_left, key); } delete del; return true; } } bool EraseR(const K&key) { return _EraseR(_root,key); } void Destroy(Node* root) { if (root == nullptr) { return; } Destroy(root->_left); Destroy(root->_right); delete root; } private: Node* _root = nullptr; };
应用搜索场景
1. key模型
在不在
1.门禁系统
2.车库系统
3.检查一篇文章中单词拼写是否正确
你拼写的单词是否在库中，若库则说明拼写正确，若不在，则说明拼写错误
key模型与上述实现的二叉搜索树基本一致
2. key value 模型
1.中英文互译字典
2.电话号码查询快递信息
3. 电话号码+验证码 查询考试成绩
4.统计水果出现的次数
key value模型 与上述实现的二叉搜索树实现功能差不多，只是增加了一个模板参数value
中英文互译字典的简单实现
通过插入将预先设置好的单词与对应意思输入树中，
输入str时，在树中查找该单词是否存在
若找到则返回节点指针指向的value，若没找到则返回nuullptr
统计水果出现次数的简单实现
3. key value模型代码
#pragma once #include<iostream> using namespace std; namespace key_value { template <class K,class V>//key //BSTree -- BinarySearchTree struct BSTreeNode { BSTreeNode<K,V>* _left;//左 BSTreeNode<K,V>* _right;//右 K _key;//key值 V _value;//value值 BSTreeNode(const K& key, const V& value) :_left(nullptr), _right(nullptr), _key(key), _value(value) { } }; template <class K,class V> class BSTree { typedef BSTreeNode<K, V> Node; public: //插入 bool Insert(const K& key, const V& value) { if (_root == NULL)//若root根节点为nullptr { _root = new Node(key, value); return true; } Node* cur = _root; Node* parent = nullptr;//用于接收cur之前的节点 while (cur != NULL) { if (cur->_key > key)//若插入的值比cur值小 { parent = cur; cur = cur->_left; } else if (cur->_key < key)//若插入的值比cur值大 { parent = cur; cur = cur->_right; } else//若相等，则直接返回false { return false; } } //遇见空指针，连接新节点 //由于不知道parent的左还是右连接key，所以需要判断 cur = new Node(key, value); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; } //查找 Node* Find(const K& key) { Node* cur = _root; while (cur != NULL) { if (cur->_key > key) { cur = cur->_left; } else if (cur->_key < key) { cur = cur->_right; } else { return cur;//成功就返回当前节点 } } return nullptr;//失败就返回空 } //中序遍历 void inorder() { _inorder(_root); } void _inorder(Node* root) { if (root == NULL) { return; } _inorder(root->_left);//左 cout << root->_key << ":"<<root->_value<<endl;//根 _inorder(root->_right);//右 } private: Node* _root = nullptr; }; }
