【数据结构】二叉搜索树

大家好，欢迎来到IT知识分享网。

✨✨欢迎大家来到Celia的博客✨✨

🎉🎉创作不易，请点赞关注，多多支持哦🎉🎉

所属专栏：数据结构

个人主页：Celia’s blog~

目录

 一、二叉搜索树

1.1 二叉搜索树的定义

1.2 为什么要用二叉搜索树

二、实现二叉搜索树

2.1 节点结构定义

2.2 插入函数Insert

2.3 查找函数Find

2.4 删除函数Enrase

2.4.1 特殊情况处理

2.5 遍历二叉搜索树

三、源码

 一、二叉搜索树

1.1 二叉搜索树的定义

  二叉搜索树是一颗二叉树，但是这颗二叉树的左右节点具有一定的要求：左子树所有的值要小于根节点的值，右子树所有的值要大于根节点的值。这样一来，当查找一个值的时候，如果比当前节点的值小，就向左遍历；如果比当前节点的值大，就向右遍历。这样的搜索模式最好的时间复杂度为logN。

1.2 为什么要用二叉搜索树

  二叉搜索树的遍历方式类似于二分查找，但是二分查找的应用有三个致命的缺点：

1. 存储数据的底层结构必须是数组。
2. 如果有插入、删除等操作，数组需要大量挪动数据。
3. 数组元素必须有序。

想要弥补这些缺点，就可以用到二叉搜索树，解决了存储结构的限制，插入、删除操作相对便捷，插入每一个元素时，按照一定的规则插入即可。

二、实现二叉搜索树

2.1 节点结构定义

template<class K> class BSTNode //每个节点的定义 { public: K val; BSTNode<K>* left; BSTNode<K>* right; BSTNode(const K& val) :val(val) ,left(nullptr) ,right(nullptr){} }; template<class K> class BSTree //树 { public: typedef BSTNode<K> Node; //成员函数... private: Node* root = nullptr; };

2.2 插入函数Insert

在树中插入一个节点，主要分为两类：

1. 插入的节点是第一个节点（根节点）。
2. 插入的节点不是根节点。

我们对于第一种情况，只需要做出简单的判断即可。对于第二种情况，则需要再分为两种情况：

1. 插入的元素如果大于当前节点，向右遍历。
2. 插入的元素如果小于当前节点，向左遍历。

直到遍历到叶子节点后，判断插入的元素与当前叶子节点的值的大小，比节点值大，插入在右边；比节点值小，插入在左边。

//在BSTree类中： bool Insert(const K& data) { Node* newnode = new Node(data); if (root == nullptr) { //插入的节点是根节点 root = newnode; } else { //插入的节点不是根节点 Node* cur = root; Node* parent = nullptr; while (cur != nullptr) { if (data < cur->val) { //如果小于当前节点，向左遍历 parent = cur; cur = cur->left; } else if (data > cur->val) { //如果大于当前节点，向右遍历 parent = cur; cur = cur->right; } else { //与当前节点值相等，不做处理，当作插入失败 cout << "Insert fail!" << endl; return false; } } //跳出循环时，cur的指向为空，实际上要在其父节点上插入新的节点，故需要记录父节点 //重新比较父节点与新节点的值的大小关系 if (data < parent->val) { parent->left = newnode; } else { parent->right = newnode; } } cout << "Insert success!" << endl; return true; }

2.3 查找函数Find

 查找函数与插入函数中寻找插入节点的过程类似，只不过这次若是没有比当前节点的值大，也没有比当前节点的值小，就说明已经找到了。若是正常跳出循环，则说明没有找到。

//在BSTree类中： bool Find(const K& data) { if (root == nullptr) { cout << "Find fail!" << endl; return false; } else { Node* cur = root; while (cur != nullptr) { if (data < cur->val) { cur = cur->left; } else if (data > cur->val) { cur = cur->right; } else { //找到了 cout << "Find success! The value is " << cur->val << endl; return true; } } //跳出循环说明没找到 cout << "Find fail!" << endl; return false; } }

2.4 删除函数Enrase

  删除函数比较复杂，主要分为四类：

1. 节点的左右孩子都为空，直接删除该节点。
2. 节点的左孩子为空，右孩子不为空，把该节点的右孩子赋值给该节点的父节点。删除该节点。
3. 节点的左孩子不为空，右孩子为空，把该节点的左孩子赋值给该节点的父节点。删除该节点。
4. 节点的左右孩子都不为空，这个时候不能直接删除节点，因为该节点的左右孩子没有位置移动。这种情况下，需要特殊处理。

• 找到当前节点的，左子树最大值，或者右子树最小值的节点replace。
• 把replace节点的值赋值给当前节点。
• 再连接replace父节点与replace子节点。
• 删除replace节点。

其中，1、2、3情况可以当作一种情况处理。 

图解： 

2.4.1 特殊情况处理

//在BSTree类中： bool Enrase(const K& data) { if (root == nullptr) { cout << "Enrase fail!" << endl; return false; } else { //第1、2、3种情况当作一种处理 //先寻找到该节点 Node* cur = root; Node* parent = nullptr; while (cur != nullptr) { if (data < cur->val) { parent = cur; cur = cur->left; } else if (data > cur->val) { parent = cur; cur = cur->right; } else { //找到了，分情况讨论 if (cur->left == nullptr) { //左边为空的情况 if (parent == nullptr) { //说明没有更新节点，删除的是头节点 root = cur->right; //移动根指针 K v = cur->val; delete cur; cout << "Enrase success! The val is " << v << endl; return true; } //这里判断的是parent和cur的关系，cur在parent的哪边 //链接cur孩子节点就链接在parent的哪边 if (parent->left == cur) { parent->left = cur->right; } else if (parent->right == cur) { parent->right = cur->right; } K v = cur->val; delete cur; cout << "Enrase success! The val is " << v << endl; return true; } else if (cur->right == nullptr) { //右边为空的情况 if (parent == nullptr) { //说明没有更新节点，删除的是头节点 root = cur->left; //移动根指针 K v = cur->val; delete cur; cout << "Enrase success! The val is " << v << endl; return true; } //这里判断的是parent和cur的关系，cur在parent的哪边 //链接cur孩子节点就链接在parent的哪边 if (parent->left == cur) { parent->left = cur->left; } else if (parent->right == cur) { parent->right = cur->left; } K v = cur->val; delete cur; cout << "Enrase success! The val is " << v << endl; return true; } else { //两边都不为空的情况 //先找到当前节点左子树的最大值，或者右子树的最小值 //左子树最大值，左子树一直往右走 //右子树最小值，右子树一直往左走 Node* replace = cur->right; Node* replaceParent = cur; while (replace->left != nullptr) { replaceParent = replace; replace = replace->left; } //这个时候，replace已经指向了右子树的最小值，进行赋值 K v = cur->val; cur->val = replace->val; //接下来链接replace父节点和replace孩子节点 //之所以分类讨论是因为有可能删除的是头节点，这种时候replaceParent //是没有刷新值的，为了避免空指针，replaceParent初始化值为cur的值 //由于链接需要判断：replaceParent和replace的位置关系，决定replace //的孩子节点链接到replaceParent的哪个节点上（left / right） //需要分类讨论 if (replaceParent->left == replace) { replaceParent->left = replace->right; } else if (replaceParent->right == replace) { replaceParent->right = replace->right; } delete replace; cout << "Enrase success! The value is " << v << endl; return true; } } } //走到这里说明没找到，无法删除 cout << "Enrase fail!" << endl; return false; } }

2.5 遍历二叉搜索树

  二叉搜索树由于左子树的值都小于根节点的值，右子树都大于根节点的值，所以需要用中序遍历来打印。

public： void InOrder() //由于root根节点私有，外面拿不到，所以多套一层，在类中就能拿到了 { InOrder(root); cout << endl; } private： void InOrder(Node* root) { if (root == nullptr) { return; } InOrder(root->left); cout << root->val << ' '; InOrder(root->right); }

三、源码

#include<iostream> using namespace std; template<class K> class BSTNode { public: K val; BSTNode<K>* left; BSTNode<K>* right; BSTNode(const K& val) :val(val) ,left(nullptr) ,right(nullptr){} }; template<class K> class BSTree { public: typedef BSTNode<K> Node; bool Insert(const K& data) { Node* newnode = new Node(data); if (root == nullptr) { //插入的节点是根节点 root = newnode; } else { //插入的节点不是根节点 Node* cur = root; Node* parent = nullptr; while (cur != nullptr) { if (data < cur->val) { //如果小于当前节点，向左遍历 parent = cur; cur = cur->left; } else if (data > cur->val) { //如果大于当前节点，向右遍历 parent = cur; cur = cur->right; } else { //与当前节点值相等，不做处理，当作插入失败 cout << "Insert fail!" << endl; return false; } } //跳出循环时，cur的指向为空，实际上要在其父节点上插入新的节点，故需要记录父节点 //重新比较父节点与新节点的值的大小关系 if (data < parent->val) { parent->left = newnode; } else { parent->right = newnode; } } cout << "Insert success!" << endl; return true; } bool Find(const K& data) { if (root == nullptr) { cout << "Find fail!" << endl; return false; } else { Node* cur = root; while (cur != nullptr) { if (data < cur->val) { cur = cur->left; } else if (data > cur->val) { cur = cur->right; } else { //找到了 cout << "Find success! The value is " << cur->val << endl; return true; } } //跳出循环说明没找到 cout << "Find fail!" << endl; return false; } } bool Enrase(const K& data) { if (root == nullptr) { cout << "Enrase fail!" << endl; return false; } else { //第1、2、3种情况当作一种处理 //先寻找到该节点 Node* cur = root; Node* parent = nullptr; while (cur != nullptr) { if (data < cur->val) { parent = cur; cur = cur->left; } else if (data > cur->val) { parent = cur; cur = cur->right; } else { //找到了，分情况讨论 if (cur->left == nullptr) { //左边为空的情况 if (parent == nullptr) { //说明没有更新节点，删除的是头节点 root = cur->right; //移动根指针 K v = cur->val; delete cur; cout << "Enrase success! The val is " << v << endl; return true; } //这里判断的是parent和cur的关系，cur在parent的哪边 //链接cur孩子节点就链接在parent的哪边 if (parent->left == cur) { parent->left = cur->right; } else if (parent->right == cur) { parent->right = cur->right; } K v = cur->val; delete cur; cout << "Enrase success! The val is " << v << endl; return true; } else if (cur->right == nullptr) { //右边为空的情况 if (parent == nullptr) { //说明没有更新节点，删除的是头节点 root = cur->left; //移动根指针 K v = cur->val; delete cur; cout << "Enrase success! The val is " << v << endl; return true; } //这里判断的是parent和cur的关系，cur在parent的哪边 //链接cur孩子节点就链接在parent的哪边 if (parent->left == cur) { parent->left = cur->left; } else if (parent->right == cur) { parent->right = cur->left; } K v = cur->val; delete cur; cout << "Enrase success! The val is " << v << endl; return true; } else { //两边都不为空的情况 //先找到当前节点左子树的最大值，或者右子树的最小值 //左子树最大值，左子树一直往右走 //右子树最小值，右子树一直往左走 Node* replace = cur->right; Node* replaceParent = cur; while (replace->left != nullptr) { replaceParent = replace; replace = replace->left; } //这个时候，replace已经指向了右子树的最小值，进行赋值 K v = cur->val; cur->val = replace->val; //接下来链接replace父节点和replace孩子节点 //之所以分类讨论是因为有可能删除的是头节点，这种时候replaceParent //是没有刷新值的，为了避免空指针，replaceParent初始化值为cur的值 //由于链接需要判断：replaceParent和replace的位置关系，决定replace //的孩子节点链接到replaceParent的哪个节点上（left / right） //需要分类讨论 if (replaceParent->left == replace) { replaceParent->left = replace->right; } else if (replaceParent->right == replace) { replaceParent->right = replace->right; } delete replace; cout << "Enrase success! The value is " << v << endl; return true; } } } //走到这里说明没找到，无法删除 cout << "Enrase fail!" << endl; return false; } } void InOrder() { InOrder(root); cout << endl; } private: void InOrder(Node* root) { if (root == nullptr) { return; } InOrder(root->left); cout << root->val << ' '; InOrder(root->right); } Node* root = nullptr; };