【C++】二叉搜索树

1.概念

二叉搜索树又称二叉排序树，可以是一棵空树，不为空具有以下性质:

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

2.实现

2.1创建节点

2.2查找

创建cur来代替_root来循环遍历
1.从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
2.最多查找高度次，走到到空，还没找到，这个值不存在。

递归版本

在私有域中封装具体实现细节，在公共域中提供接口使用，作为成员函数在类中可直接访问私有成员变量。

递归的终止条件是1.找到空节点(失败) 2.找到key所在节点(成功)
若当前的key值小于目标key值，则递归地在当前节点的右树中查找；反之在左树查找。不断缩小搜索范围，直到找到目标key值或搜索范围为空。

2.3插入

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->_left = cur;}else{parent->_right = cur;}return true;
}

创建cur来代替_root来循环遍历，提前保存父节点
1.树为空，则直接新增节点，赋值给root指针,插入成功
2.树不空，按二叉搜索树性质查找插入位置，插入新节点。若找到key值相同的节点就插入失败，因为二叉搜索树性质决定不允许有相同key值的节点同时存在。
3.找到空节点后创建新节点，注意记得用父节点链接上形成搜索二叉树，需要判断链接在父节点的左边还是右边。

递归版本

还是在私有域封装实现细节，公共域提供接口使用，作为类的成员函数可直接访问私有成员。

递归结束条件为找到空节点位置，创建新节点进行链接。
这里的神来之笔是Node*&root，每次递归下去的是当前节点指针的引用（），这样就可以省略提前保存父节点指针的步骤，直接进行链接即可。root永远是父亲右指针和左指针的别名，这样就不用判断重新链接在父指针的左还是右。

为什么循环不能传指针的引用？
引用的问题是不能改变指针指向，循环中没办法使用，递归可以因为每次都会创建新的栈帧，不同域中可以定义同名变量，每个栈帧中的引用都不同，每次递归都创建新的引用

2.4删除

删除时有三种情况：
1.删除节点没有孩子
2.删除节点只有一个孩子
3.有两个孩子
解决办法：
a：1和2属于直接删除场景，删除后父节点重新链接即可(nullptr或子节点)
b：3用替换法，用左子树的最大节点(最右节点)，或者右子树的最小节点(最左节点)。这样能确保交换根节点和要删除节点的key值后左子树key值依然小于根节点key值，右子树key值依然大于根节点key值，满足二叉搜索树性质。最后删除 要删除节点位置即可。

bool Erase(const k& key)
{Node* cur = _root;Node* parent = cur;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->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}}//删除节点的右树为空else if (cur->_right == nullptr){//处理跟=根节点为要删除节点情况if (cur == _root){_root = cur->_left;}if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = 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->_right == leftmax){parent->_right = leftmax->_left;}if (parent->_left == leftmax){parent->_left = leftmax->_left;}cur = leftmax;}delete cur;return true;}}return false;
}

代码逻辑：
1.创建cur来代替_root来循环遍历，提前保存父节点
2.找要删除节点的位置，比较当前位置key值与目标key值，不断更新父节点位置和cur节点位置，循环遍历下去，直到找到目标位置
3.依次分析删除的三种情况，注意检查删除节点是根节点的情况

需要将根节点更新到子树不为空的位置，这样父节点也跟着更新了(Node* parent = cur)，若不更新父节点为空，会造成非法访问的问题
4.重点分析删除节点有两个孩子情况：
左边和右边情况分别创建leftmax或rightmax来记录替代节点，父节点赋值为cur，可以避免父节点为空跳过循环中父节点赋值而造成的非法访问问题。找到后交换两节点中key值，再进行删除后的重新链接

递归版本

public:
bool EraseR(const k& key)
{return _EraseR(_root, key);
}
private:
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* leftmax = root->_left;while (leftmax->_right){leftmax = leftmax->_right;}swap(leftmax->_key, root->_key);return _EraseR(root->_left, key);}delete del;return true;}
}

递归终止条件1.根节点为空返回false 2.删除成功返回true
代码逻辑：
1.递归查找要删除的节点
2.当前key值等于目标key值，进行删除逻辑：
保存要删除节点到临时指针del
然后重新链接树，左子树为空，将当前节点右子树链接到父节点；右子树为空，将当前节点左子树链接到父节点；左右子树都不为空时，找到左子树的最大节点(最右节点)，或右子树的最小节点(最左节点)，将该节点key值与根节点key值交换，然后递归的在根节点的左子树中删除目标key值，这样目标key值所在节点从有两个孩子变成没有孩子

辨析：
return _EraseR(root->_left, key);第一个参数若用leftmax

删除接口传参Node*& root，用的指针的引用，传下来的是节点指针的引用，所以不需要提前保存父节点进行重新链接。但此处传leftmax指针的引用实际上是指向1节点指针的引用(当前节点指针的引用)，将3这个节点删除后8节点指针指向没有改变，导致结构混乱。应该传root->_left，指向3节点，发现3的右节点为空直接指向1节点，正确完成删除

感受指针引用的妙处

以右子树为空的情况分析：正常情况下，root是父亲右指针或左指针的别名，直接更改父节点指向，上文已分析过

当要删除节点为空节点时，此时root为_root的别名,同样可以直接更改_root的指向

2.5复制

拷贝构造函数使用参数 t 来获取原对象的数据，然后根据这些数据构造一个新对象，新对象在内存中是完全独立的副本。复用copy函数实现深拷贝

递归终止条件1.传入节点为空无需复制返回空指针 2.每次递归调用中创建一个key值与原树相同的节点
通过后序遍历递归复制左子树和右子树，在递归过程中创建节点，在返回过程中链接形成树型结构

2.6销毁

采用后序遍历的方式销毁二叉树，释放当前节点占用内存后，记得将root指针置空

析构函数复用销毁的实现

3.二叉搜索树的应用

key搜索模型：

K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。上述代码实现就是该模型的应用
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

key_value模型：

每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对
比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对

namespace key_value
{template<class k, class v >struct BSTreeNode{BSTreeNode<k,v>* _left;BSTreeNode<k,v>* _right;k _key;v _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:BSTree():_root(nullptr){}//封装一次可以通过类直接调用void _Inorder(){Inorder(_root);cout << endl;}Node* FindR(const k& key){return _FindR(_root, key);}bool InsertR(const k& key,const v&value){return _InsertR(_root, key,value);}bool EraseR(const k& key){return _EraseR(_root, key);}private:void Inorder(Node* _root){if (_root == nullptr){return;}Inorder(_root->_left);cout << _root->_key << ":"<<_root->_value<<endl;Inorder(_root->_right);}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* leftmax = root->_left;while (leftmax->_right){leftmax = leftmax->_right;}swap(leftmax->_key, root->_key);return _EraseR(root->_left, key);}delete del;return true;}}bool _InsertR(Node*& root, const k& key,const v&value){if (root == nullptr){root = new Node(key,value);return true;}if (root->_key < key){return _InsertR(root->_right, key,value);}else if (root->_key > key){return _InsertR(root->_left, key,value);}else{return false;}}Node* _FindR(Node* root, const k& key){if (root == nullptr){return nullptr;}if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return root;}}Node* _root;};
}

实现思路与key模型基本相同，只是节点中多增加了_value成员变量，BSTree类中多增加了一个模板参数v，实现插入功能时要同时插入value值。

• 测试代码

void testBSTree1()
{key_value::BSTree<string, string> dict;dict.InsertR("mint", "薄荷");dict.InsertR("forever", "永远");dict.InsertR("love", "相爱");string str;while (cin >> str){key_value::BSTreeNode<string, string>* ret = dict.FindR(str);if (ret){cout << ret->_value << endl;}else{cout << "无此单词" << endl;}}
}

输入CTRLz+换行结束输入，正常退出ctrlc直接关掉程序