【二叉搜索树】

二叉搜索树

一、认识二叉搜索树
二、二叉搜索树实现
- 2.1插入
- 2.2查找
- 2.3删除
总结

一、认识二叉搜索树

二叉搜索树（Binary Search Tree，简称 BST）是一种特殊的二叉树，它具有以下特征：

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

如图：
在这里插入图片描述

二、二叉搜索树实现

在实现各种操作之前，我们先创建节点，使用结构体+类模板来创建，因为结构体默认访问权限是共有的（即public），里面需要写到左子树、右子树、结点的值，再写个构造函数赋初值。

template<class K>
struct  BStreeNode
{BStreeNode<K>* _left;BStreeNode<K>* _right;K _key;BStreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}
};

2.1插入

插入操作步骤：

树为空，则直接新增节点，赋值给root指针
树不空，按二叉搜索树性质查找插入位置，插入新节点

解析：

首先while循环进行遍历,若该key值比cur值小，则向cur左树找，反之，右树找，直到叶子节点为止。如果与cur值相同，返回false（因为二叉搜索树不允许有相同的数出现）。
插入过程需要连接，创建个parent节点跟着我们需要遍历的节点（cur）完成连接过程。
跟父节点比较，比父节点大，插入到他的右边，反之，就是左边。

代码：

bool insert(const K& key)
{if (_root == nullptr){_root = new node(key);return true;}node* parent = nullptr;node* cur = _root;////cur每次要向下走，parent也跟着走while (cur){if (key< cur->_key ){parent = cur;cur = cur->_left;}else if (key> cur->_key){parent = cur;cur = cur->_right;}else{return false;}}cur = new node(key);if (parent->_key < key){//如果插入的值比目标值大，就连接在右边；parent->_right = cur;}else{parent->_left = cur;}return true;
}

2.2查找

若key大于cur->_key就从右树找
key小于cur->_key就从左子树找。
如果相等返回true；

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.3删除

1、首先定义个父节点parent和节点cur（指向根节点）
2、再循环遍历cur，先找要删除的节点。

若删除的节点左数为空，且删除的是根节点，让根结点指向原根结点的右子树。删除的不是根节点，让他的子树托孤给他的父节点。
如果右节点空，删除的是根节点，让他的根节点只想原根结点的左子树，不是根节点，就托孤给父节点
左右都不为空的情况下。父节点指向cur，leftnode（被删节点的左子树）指向cur的左子树，循环遍历leftnode右子树，交换cur与leftnode值，如果leftnode在父节点的左子树，那就将leftnode的左子树给父节点的左子树，否则就给父节点的右子树。最后将leftnode传给cur，再删除cur.

bool Erase(const K& key)
{node* parent = nullptr;node* cur = _root;//没有节点while (cur){//找if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{//找到了  左空if (cur->_left == nullptr){if (cur == _root)//如果cur没有parent，他就是根节点{_root = cur->_right;}else {if (parent->_right == cur)//如果cur右为空，并且是父亲的右节{//节点指向curparent->_right = cur->_right;}else{parent->_left = cur->_right;}}}//else if (cur->_right == nullptr)//如果cur右为空。{ 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* leftnode = cur->_left;//右边不为空的情况，一直找下去while (leftnode->_right){parent = leftnode;//每次走之前给parentleftnode = leftnode->_right;}swap(cur->_key, leftnode->_key);if (parent->_left == leftnode){parent->_left = leftnode->_left;}else{parent->_right = leftnode->_left;}cur = leftnode; }delete cur;return true;}}
}