32.C++二叉树进阶1（二叉搜索树）
⭐上篇文章：31.C++多态4（静态多态，动态多态，虚函数表的存储位置）-CSDN博客
⭐本篇代码：c++学习/18.二叉树进阶-二叉搜索树 · 橘子真甜/c++-learning-of-yzc - 码云 - 开源中国 (gitee.com)
⭐标⭐是比较重要的部分
一. 二叉搜索树的概念
二叉搜索树也称二叉排序树，它有可能是一颗空树。二叉搜索树性质如下：
1 若它有左子树，那么它的左子树所有节点的值小于根节点
2 如它有右子树，那么它的右子树所有节点的值小于根节点
3 它的左右子树也是二叉搜索树
二叉树的代码框架如下：
#pragma once
#include <iostream>
#include <vector>
//二叉树节点
template<class K>
struct BSTreeNode
{
K _key;
BSTreeNode* _left;
BSTreeNode* _right;
BSTreeNode(const K& key)
:_key(key), _left(nullptr), _right(nullptr)
{};
};
//二叉树
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
bool Insert()
{}
bool find()
{}
bool Delete)
{}
//二叉树不允许修改数据
private:
Node* _root; //根节点
};
二. 二叉搜索树的插入
假设我们插入的节点为key
若一棵树为空，则直接插入即可
若不为空：
按照二叉搜索树的性质，插入该节点即可。
如果某一个节点和key值相同，则直接不插入
若某一个节点比key值大，则应该将key插入到该节点的左子树中
若某一个节点比key值小，则应该将key插入到该节点的右子树中
然后在其左右子树中进行判断，直到子树节点为空，然后插入即可
流程图如下：
插入函数的代码如下：
bool Insert(const K& key)
{
//根节点为空
if (!root)
{
_root = new Node(key);
return true;
}
//不为空，根据性质插入数据
Node* cur = _root;
Node* parent = cur; //最后cur为空，需要一个节点保存其父节点用于连接
while (cur)
{
if (key > cur->_key) //比当前值大，找其右子树
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key) //比当前树小，找其左子树
{
parent = cur;
cur = cur->_left;
}
else
return false; //有相同节点，插入失败
}
//此时cur为空，cur即为插入的数据
cur = new Node(key);
if (cur->_key > parent->_key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}三. 二叉搜索树的查找
二叉搜索树的查找过程和插入过程非常相似。比如在插入的过程中，如果发现值相同，返回true即可，如果为空，则说明没有这个节点，返回false
bool find(const K& key)
{
if (!_root)
return false;
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
cur = cur->_right;
else if (key < cur->_key)
cur = cur->_left;
else
return true;
}
//cur为空，没有key这个节点
return false;
}
四. 二叉树的删除
二叉树的删除比较麻烦。可以分为下面四个情况。
1 该节点无左右子节点：
2 该节点只有左子树：
3 该节点只有右子树
4 该节点有左右子树
实际情况1与情况2或者3是重合的，所以只需考虑三者情况
4.1 删除节点右子树为空
下面这流程图我们要删除节点9
若删除节点是父亲左孩子，父亲的左指向删除节点的左孩子
若删除节点是父亲的右孩子，父亲的右指向删除节点的左孩子
如果一个节点左右都为空，也满足这种情况
4.2 删除节点左子树为空
与上面情况类似
若删除节点是父亲左孩子，父亲的左指向删除节点的右孩子
若删除节点是父亲的右孩子，父亲的右指向删除节点的右孩子
4.3 左右孩子均不为空
此时需要找到一个节点来替代这个节点，在二叉搜索树中，根据其左子树节点比根节点小，右子树节点比根节点大的性质。如果一给节点左右不为空，只需找出其左子树最大，或者右子树最小来替代这个节点即可。
流程图如下：
4.4 删除节点代码
//删除
bool Erase(const K& key)
{
//1.该节点只有一个孩子
//2.该节点没有孩子
//3.该节点有三个孩子
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)
{
//当cur为根的时候要特判
if (cur == _root)
{
_root = cur->_right;
}
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
delete cur;
cur = nullptr;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
delete cur;
cur = nullptr;
}
else//两边都不为空
{
//找到左边最大，右边最小与当前值交互即可
Node* rightmin = cur->_right;
Node* rightminparent = cur;
while (rightmin->_left)
{
rightminparent = rightmin;
rightmin = rightmin->_left;
}
cur->_key = rightmin->_key;
//如果cur的右孩子是最小的，直接让cur指向右孩子的右孩子即可
if (rightmin == cur->_right)
{
cur->_right = rightmin->_right;
}
else
{
rightminparent->_left = rightmin->_right;
}
delete rightmin;
rightmin = nullptr;
}
return true;
}
}
return false;
}五. 二叉搜索树的遍历
根据二叉搜索树的性质，如果我们以中序遍历(左根右)，那我们的遍历的时候先是最小的，然后依次遍历更大的。那么最终的排序顺序是有序的！
中序遍历代码如下：
void _InOrder(const Node* root)
{
if (!root)
return;
//中序遍历
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}六.代码与测试
bstree.h
#pragma once
#include<iostream>
#include<vector>
using namespace std;
template<class K>
struct BSTreeNode
{
BSTreeNode* _left;
BSTreeNode* _right;
K _key;
//构造函数
BSTreeNode(const K& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
//插入
bool Insert(const K& key)
{
//第一次插入
if (!_root)
{
_root = new Node(key);
return true;
}
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
{
return false;
}
}
cur = new Node(key);
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
//查找
bool find(const K& key)
{
if (!_root)
return false;
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 Erase(const K& key)
{
//1.该节点只有一个孩子
//2.该节点没有孩子
//3.该节点有三个孩子
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)
{
//当cur为根的时候要特判
if (cur == _root)
{
_root = cur->_right;
}
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
delete cur;
cur = nullptr;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
delete cur;
cur = nullptr;
}
else//两边都不为空
{
//找到左边最大，右边最小与当前值交互即可
Node* rightmin = cur->_right;
Node* rightminparent = cur;
while (rightmin->_left)
{
rightminparent = rightmin;
rightmin = rightmin->_left;
}
cur->_key = rightmin->_key;
//如果cur的右孩子是最小的，直接让cur指向右孩子的右孩子即可
if (rightmin == cur->_right)
{
cur->_right = rightmin->_right;
}
else
{
rightminparent->_left = rightmin->_right;
}
delete rightmin;
rightmin = nullptr;
}
return true;
}
}
return false;
}
//二叉搜索树不允许修改，修改后会导致二叉树失效
//中序遍历
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
Node* _root = nullptr;
void _InOrder(const Node* root)
{
if (!root)
return;
//中序遍历
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
};test.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include"bstree.h"
void test1()
{
BSTree<int> tree;
vector<int> arr;
for (int i = 0; i < 10; i++)
{
int t = rand() % 10000;
arr.push_back(t);
tree.Insert(t);
}
tree.InOrder();
for (int i = 0; i <= 9; i++)
{
cout << "删除" << arr[i] << "后:";
tree.Erase(arr[i]);
tree.InOrder();
}
}
int main()
{
srand((unsigned int)time(0));
test1();
}
可以看到，排序的顺序是有序的