🐧主页详情：Choice~的个人主页
📢作者简介：🏅物联网领域创作者🏅 and 🏅阿里专家博主🏅 and 🏅华为云享专家🏅
✍️人生格言：最慢的步伐不是跬步，而是徘徊；最快的脚步不是冲刺，而是坚持。
🧑‍💻人生目标：成为一名合格的程序员，做未完成的梦：实现财富自由。
🚩技术方向：NULL
🀄如果觉得博主的文章还不错的话，请三连支持一下博主哦
💬给大家介绍一个我一直在用的求职刷题收割offe👉点击进入网站

二叉搜索树

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

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

int a [] = {5,3,4,1,7,8,2,6,0,9};

使用价值：搜索

template <class K>//为了统一类型

二叉树包含左子树和右子树和值：并且希望哪里都可以访问，我们定义一个结构体struct BSTNode默认是公有访问

template <class K>
struct BSTNode
{BSTNode<K>*_right;BSTNode<K> *_left;K _key;};

然后开始创建对象class BSTree，为了方便typedef BSTNode Node * _root;简写成typedef BSTNode<K> Node; Node* _root;整体框架：

class BSTree
{typedef BSTNode<K> Node;public:BSTree() :_root(nullptr){}
private:Node* _root;};

增删查改接口：

void InOrder(){}//中序遍历
bool Insert(const K&key){}
Node*find(const K&key){}
bool Erase(const K &key){}

中序遍历(Inorder)

这里为了可以在类里面访问私有成员变量，我们写一个方法把_root传参_：

void InOrder(){_InOrder(_root);cout << endl;}

void _InOrder(Node*root){if (root == nullptr)return;//中序遍历_InOrder(root->_left);cout << root->_key<< " ";_InOrder(root->_right);}

根据完全二叉树的特性，可以把数组5, 3, 4, 1, 7, 8, 2, 6, 0, 9构成下图逻辑结构：

中序的遍历规则是：先遍历左孩子然后是父亲最后是右孩子

插入节点

插入第一个节点，根节点现在为空，判断一下，如果是第一次插入就是根节点：

if (_root == nullptr){_root = new Node(key);return true;}

这里用了new 开辟空间，需要自己写一个构造函数并初始化

BSTNode(const K& key):_right(nullptr), _left(nullptr), _key(key){}

我们需要有个节点cur指向根节点Node* cur = _root;

对cur指向的值进行判断是否比插入的节点小，根据二叉搜索树特性，左孩子小于右孩子；如果cur指向的值比新插入的小，那我们cur指向右孩子cur = cur->_right;，如果cur指向的值比新插入的大，那我们cur指向左孩子cur = cur->_left;，最后一种就是它们相等，那就返回假；

while(cur)if (cur->_key < key){cur = cur->_right;}else if (cur->_key>key){	cur = cur->_left;}else{return false;}
}

左孩子和右孩子已经分出来了，那结合起来的它们父亲该谁做呢？我们就需要定义一个父亲：Node*parent = nullptr;，并判断父亲指向的值是大还是小

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

查找节点

查找很简单，通过比大小，大的在右边，小的在左边：

Node*find(const K&key){Node*cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}elsereturn cur;}return NULL;}

删除节点：

我们删除节点需要找到那个节点，那怎么找呢？这里我们也和插入一样使用用双指针，通过cur指向的节点可以找到父亲和左右孩子，但是删除有3种情况：

解决方案：

1：删除自己，父亲指向自己位置的指针置空

2：删除节点，把孩子交给父亲，顶替自己的位置

3：替换法删除。去孩子里面找一个值能替换自己位置的节点，替换自己删除

第一种情况：删除8，我们需要通过8这个值找到父亲，并判断父亲指向这个值是左孩子还是右孩子，看图8这个父亲有个右孩子9，删除8之后，右孩子8的父亲也要指向右孩子9

第二种就是相反：

第三种就需要找删除树的最小的节点，我们假设在右子树，我们也定义两个指针，一个是最小值的父亲和最小值的右子树Node* minParent = cur;Node* minRight = cur->_right;，当然最小的一个节点一定是在最左边

while (minRight->_left)
{minRight = minRight->_left;
}

找到最小的值后 和删除的值替换

cur->_key = minRight->_key;//替换

//删除替换节点
if (minParent->_left == minRight)//如果父亲有左孩子minParent->_left = minRight->_right;
else//如果是右孩子minParent->_right = minRight->_right;
delete minRight;

删除测试：

但是仔细一看会有一个bug：那就是全部删除之后，我们没有处理为空树的情况会怎么样；

我们需要在前面判断，要是删除到根节点，就让根节点指向左子树还是右子树

//找到了，准备删除if (cur->_left == nullptr)//左为空{if (cur == _root){_root=cur->_right;//指向右树}else{if (parent->_left == cur){parent->_left = cur->_right;}elseparent->_right = cur->_right;}delete cur;}else if (cur->_right == nullptr)//右为空{if (cur == _root){_root = cur->_left;//指向左树}else{if (parent->_left == cur){parent->_left = cur->_left;}elseparent->_right = cur->_right;}

key/value模型

我们再加一个模板class V

template <class K,class V>

实现中英文翻译

template <class K,class V>
struct BSTNode
{BSTNode<K,V>*_right;BSTNode<K,V> *_left;K _key;V _value;BSTNode(const K& key,const V& value):_right(nullptr), _left(nullptr), _key(key), _value(value){}
};
template <class K,class V>
class BSTree
{typedef BSTNode<K,V> Node;public:BSTree() :_root(nullptr){}Node* Insert(const K&key,const V&value){if (_root == nullptr){_root = new Node(key,value);return nullptr;}Node* cur = _root;Node*parent = nullptr;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key>key){parent = cur;cur = cur->_left;}else{return nullptr;}}cur = new Node(key,value);if (parent->_key < key)parent->_right = cur;else parent->_left = cur;return cur;}Node*find(const K&key){Node*cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}elsereturn cur;}return NULL;}bool Erase(const K &key){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{//找到了，准备删除if (cur->_left == nullptr)//左为空{if (cur == _root){_root=cur->_right;//指向右树}else{if (parent->_left == cur){parent->_left = cur->_right;}elseparent->_right = cur->_right;}delete cur;}else if (cur->_right == nullptr)//右为空{if (cur == _root){_root = cur->_left;//指向左树}else{if (parent->_left == cur){parent->_left = cur->_left;}elseparent->_right = cur->_right;}}else{//找到右子树的最小节点Node* minParent = cur;//这里不能等于nullprt，当cur的右节点没有左孩子，循环不进去，删除替换节点就会出错Node* minRight = cur->_right;while (minRight->_left){minRight = minRight->_left;}cur->_key = minRight->_key;//替换//删除替换节点if (minParent->_left == minRight)//如果父亲有左孩子minParent->_left = minRight->_right;else//如果是右孩子minParent->_right = minRight->_right;delete minRight;}return true;}}return false;}void _InOrder(Node*root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key<< " ";_InOrder(root->_right);}void InOrder(){_InOrder(_root);cout << endl;}private:Node* _root=nullptr;};

翻译效果

修改节点

知道为什么才开始修改节点吗？因为我们可以通过K/V模型修改，Key是不能修改的；假设修改根节点值为0，那树的结构全乱了，但是有了value值后可以对它进行修改，

• 如果对大家有帮助，请三连支持一下！
• 有问题欢迎评论区留言，及时帮大家解决！