目录

搜索二叉树的概念

二叉搜索树的遍历

二叉搜索树的模拟实现

Find查找函数

 Insert插入函数

 Erase删除函数

case 1：

case 2：

待删除结点左孩子不存在，右孩子存在

 待删除结点左孩子存在，右孩子不存在

case 3：

Erase循环版本实现

中序遍历

析构函数

拷贝构造函数

赋值运算符重载

构造函数

---

搜索二叉树的概念

搜索树二叉树或者是一棵空树，或者是具有以下性质的二叉树:

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

二叉搜索树的遍历

二叉树的遍历包括前序遍历，中序遍历，后序遍历，此处按照前序遍历进行展示；

前序遍历的顺序为首先遍历根结点，其次遍历左子树，最后遍历右子树；

遍历方法：

先把根拔下来，再把左子树拔下来，最后把右子树拔下来，依次排好顺序，然后再以同样的方法递归似的拔左子树，直至左子树上的结点被拔光，最后按照同样的方式拔右子树；

 前序遍历结果：8 ---> 3 ---> 1 ---> 6 ---> 4 --->7 ---> 10 ---> 14---> 13

二叉搜索树的模拟实现

实现一颗二叉搜索树，需要实现两个类，第一个是结点类，用于存放节点值、左指针、右指针；第二个类专门用于二叉搜索树的增删查改；

//结点类的实现
template <class K>
struct BinarySearchTreeNode
{typedef BinarySearchTreeNode Node;Node* _left;//指向左子树Node* _right;//指向右子树K _key;//存储当前结点数据//开辟新结点需要构造函数BinarySearchTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}
};

二叉搜索树的类（第二个类）用于实现搜索二叉树的增删查改；

template <class K>
class BinarySearchTree
{typedef BinarySearchTreeNode<K> Node;
public://...
private:Node* _root=nullptr;
};

Find查找函数

搜索二叉树的查找,找到了返回true,否则返回false；
思路:

1. 定义cur指针从根结点开始,将待查找元素key与当前结点处的键值进行比较；
2. 若key小于当前结点处的键值,则去该节点的左子树查找；若key大于当前结点处的键值,则去该节点的右子树查找；
3. 查找过程中走到结点指针为空，找不到key，返回false；
4. 若查找过程中某个结点数据与key相等，停止查找，返回true；

bool Find(const K& key)
{Node* cur = _root;while (cur != nullptr){//key大于当前结点处的键值,则去该节点的右子树查找if (cur->_key < key){cur = cur->_right;}//若key小于当前结点处的键值,则去该节点的左子树查找else if (cur->_key > key){cur = cur->_left;}//查找过程中某个结点数据与key相等,停止查找,返回true;else{return true;}}//cur走空,找不到返回falsereturn false;
}

 Insert插入函数

思路: 插入的要求是插入的结点依旧维持搜索二叉树的逻辑结构

1. 首先确定插入的位置，从根节点开始，将插入的数值与该结点处的数值相比较；
2. 若大于该结点处的数值，前往该节点作为根节点的右子树查找；
3. 若小于该结点处的数值，前往该节点作为根节点的左子树查找；
4. 直至走到结点指针为空的位置,每次查找需要记录该结点的父亲结点的位置，方便建立链接关系；

bool Insert(const K& key)
{// 空树if (_root == nullptr){_root = new Node(key);return true;}//非空树//parent记录父节点位置Node* parent = nullptr;Node* cur = _root;while (cur != nullptr){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key>key){parent = cur;cur = cur->_left;}//为维护搜索二叉树逻辑结构,同一颗树不能出现相等的数值else{return false;}}//cur已经走空,开辟节点,存储数据,建立链接关系cur = new Node(key);//存储值为key的结点链接到父节点的何处？if (parent->_key > key){parent->_left = cur;}else{parent->_right = cur;}return true;
}

 Erase删除函数

搜索二叉树的删除:删除的要求是删除结点后依旧维持搜索二叉树的逻辑结构；
首先查找待删除元素是否在搜索二叉树中，不在返回false，否则返回true；

若查找到待删除元素所在的结点，删除结点，删除结点分三种情形：

1. 删除叶子结点；
2. 删除单孩子结点(其中又分为待删除节点处的左孩子不存在、右孩子存在或者左孩子存在、右孩不存在)；
3. 删除左右孩子皆存在的结点；

case 1：

删除叶子结点（删除13），直接释放cur所指向的空间；

case 2：

待删除结点左孩子不存在，右孩子存在

if(cur->_left==nullptr)
{parent->_right=cur->_right;delete cur;
}

if(cur->_left==nullptr)
{parent->_left=cur->_right;delete cur;
}

通过删除10与删除1，注意到一个问题，单孩子结点处的孩子结点应该链接于单孩子节点的父节点的左指针还是右指针？

需要根据单孩子结点处的键值与其父节点处的键值相比较，从而确定链接位置；

若单孩子结点处的键值大于其父节点处的键值，应该将单孩子结点处的孩子结点链接于父节点的右指针；

若单孩子结点处的键值小于其父节点处的键值，应该将单孩子结点处的孩子结点链接于父节点的左指针；

if(cur->_left==nullptr)
{if(parent->_key < cur->_key){parent->_right=cur->_right;}if(parent->_key > cur->_key){parent->_left=cur->_right;}delete cur;
}

if(cur->_left==nullptr)
{if(cur == _root){_root = cur->_right;delete cur;}
}

 待删除结点左孩子不存在，右孩子存在的所有情况分析汇总如下：

if (cur->_left == nullptr)
{if (cur == _root){_root = cur->_right;}else{if (parent->_key < cur->_key){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;return true;
}

 待删除结点左孩子存在，右孩子不存在

if(cur->_right == nullptr)
{parent->_right=cur->_left;delete cur;
}

if(cur->_right==nullptr)
{parent->_left=cur->_left;delete cur;
}

通过删除14与删除0，注意到一个问题，单孩子结点处的孩子结点应该链接于单孩子节点的父节点的左指针还是右指针？

需要根据单孩子结点处的键值与其父节点处的键值相比较，从而确定链接位置；

若单孩子结点处的键值大于其父节点处的键值，应该将单孩子结点处的孩子结点链接于父节点的右指针；

若单孩子结点处的键值小于其父节点处的键值，应该将单孩子结点处的孩子结点链接于父节点的左指针；

if(cur->_right==nullptr)
{if(parent->_key < cur->_key){parent->_right=cur->_left;}if(parent->_key > cur->_key){parent->_left=cur->_left;}delete cur;
}

if(cur->_right==nullptr)
{if(cur == _root){_root = cur->_left;delete cur;}
}

 待删除结点左孩子存在，右孩子不存在的所有情况分析汇总如下：

//待删除结点左孩子存在,右孩子不存在
else if (cur->_right == nullptr)
{if (cur == _root){_root = cur->_left;}else{if (parent->_key < cur->_key){parent->_right = cur->_left;}else{parent->_left = cur->_right;}}delete cur;return true;
}

case 3：

思路：（替换法删除）

1. 选取待删除结点作为根结点的左子树的最大结点(左子树的最右节点)或者选取待删除结点作为根结点的右子树的最小结点(右子树的最左节点)替换当前待删除结点；
2. 假设选取右子树的最左结点作为替换结点，查找替换结点RightMin的位置，将RightMin结点处的值直接赋予cur；
3. 删除RightMin节点；

注:替换结点不一定为叶子结点,但必为单孩子结点(若右子树最左结点为替换结点,则替换结点必定没有左孩子)

//寻找RightMin结点即右子树的最左结点
Node* RightMinParent = cur;
Node* RightMin = cur->_right;
while (RightMin->_left != nullptr)
{RightMinParent = RightMin;RightMin = RightMin->_left;
}
//找到RightMin结点,替换删除
cur->_key = RightMin->_key;
//链接
if (RightMinParent->_left == RightMin)//RightMin->_left==nullptr
{RightMinParent->_left = RightMin->_right;
}
if (RightMinParent->_right == RightMin)
{RightMinParent->_right = RightMin->_right;
}
delete RightMin;
return true;

Erase循环版本实现

bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur != nullptr)
{
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->_key < cur->_key){parent->_right = cur->_right;}else{parent->_left = cur->_right;}
}
delete cur;
return true;
}
else if (cur->_right == nullptr)
{if (cur == _root){_root = cur->_left;}else{if (parent->_key < cur->_key){parent->_right = cur->_left;}else{parent->_left = cur->_right;}}delete cur;return true;
}
else
{
//寻找RightMin结点即右子树的最左结点
Node* RightMinParent = cur;
Node* RightMin = cur->_right;
while (RightMin->_left != nullptr)
{RightMinParent = RightMin;RightMin = RightMin->_left;
}
//找到RightMin结点,替换删除
cur->_key = RightMin->_key;
//链接
if (RightMinParent->_left == RightMin)//RightMin->_left==nullptr
{RightMinParent->_left = RightMin->_right;
}
if (RightMinParent->_right == RightMin)
{RightMinParent->_right = RightMin->_right;
}
delete RightMin;
return true;
}
}
}
return false;
}

中序遍历

//搜索二叉树的中序遍历(左子树-->根-->右子树)
//外部需要将_root传递给root,但是外部无法访问_root
void _InOrder(Node* root)
{if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);
}
void InOrder()
{_InOrder(_root);cout << endl;
}

析构函数

由于结点在堆区申请空间，所以需要手动释放空间；

//首先销毁左子树,其次销毁右子树,最后销毁根结点;
void Destroy(Node* root)
{if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;
}
~BinarySearchTree()
{Destroy(_root);
}

拷贝构造函数

结点指针为自定义类型，涉及浅拷贝，导致同一块空间被析构两次,需要实现深拷贝与深赋值；

BinarySearchTree<int> t1(t);

  思路:

1.     创建一个新二叉搜索树，作为拷贝的目标树；
2.     从始树的根节点开始，递归地复将其插入到目标树中；
3.     对于每个节点，复制其值，并递归地复制其左子树和右子树；
4.     返回一个拷贝后的二叉搜索树的根节点；

Node* copy(Node* root)
{if (root == nullptr){return nullptr;}Node* NewRoot = new Node(root->_key);NewRoot->_left = copy(root->_left);NewRoot->_right = copy(root->_right);return NewRoot;
}
BinarySearchTree(const BinarySearchTree<K>& t)
{_root = copy(t._root);
}

赋值运算符重载

//BinarySearchTree<int> t2 = t1;
BinarySearchTree<K>& operator=(const BinarySearchTree<K>& t)
{swap(_root, t._root);return *this;
}

构造函数

//构造函数
BinarySearchTree() = default;//强制生成默认构造

---

欢迎大家批评指正，博主会持续输出优质内容，谢谢各位观众老爷观看，码字画图不易，希望大家给个一键三连支持~ 你的支持是我创作的不竭动力~