污水处理厂网站建设,排版设计图,网站建设从建立服务器开始,舆情系统排名文章目录 什么是二叉搜索树二叉搜索树的接口1.查找操作2.插入操作3.中序遍历4.删除操作 所有代码总结 什么是二叉搜索树
二叉搜索树#xff08;Binary Search Tree, BST#xff09;是一种特殊的二叉树#xff0c;其每个节点最多有两个子节点#xff0c;分别称为左子节点和… 文章目录 什么是二叉搜索树二叉搜索树的接口1.查找操作2.插入操作3.中序遍历4.删除操作 所有代码总结 什么是二叉搜索树
二叉搜索树Binary Search Tree, BST是一种特殊的二叉树其每个节点最多有两个子节点分别称为左子节点和右子节点。BST具有以下性质
左子树的所有节点值都小于根节点的值即对于每一个节点其左子树上所有节点的值都比该节点的值小。右子树的所有节点值都大于根节点的值即对于每一个节点其右子树上所有节点的值都比该节点的值大。每个子树也是二叉搜索树这意味着BST的定义在每个节点的子树上都成立。
形如下面这棵树就是一颗二叉搜索树 8/ \3 10/ \ \1 6 14/ \ /4 7 13
二叉搜索树的接口
要写二叉搜索树的接口我们先得定义一颗二叉搜索树
定义二叉搜索树的节点
templateclass K
struct BSTreeNode
{K _key;BSTreeNodeK* _left;BSTreeNodeK* _right;BSTreeNode(const K key):_key(key), _left(nullptr), _right(nullptr){}
};定义二叉搜索树
templateclass K
class BSTree
{typedef BSTreeNodeK Node;
public:
private:Node* _root nullptr;
};1.查找操作
由于二叉搜索树的性质所以这里我们可以直接用while循环来查找不需要进行递归来查找
bool Find(const K key)
{Node* cur _root;while (cur){//小于当前节点在左子树if (cur-_key key)cur cur-_left;//大于当前节点在右子树else if (cur-_key key) cur cur-_right;//等于当前节点返回trueelse return true;}return false;
}2.插入操作
插入操作我们只需要找到插入的位置然后插入节点即可如果没有找到则返回false如果找到了并成功插入了则返回true。
bool Insert(const K key)
{//没有根节点的情况if (_root nullptr){_root new Node(key);return true;}//遍历节点Node* cur _root;//记录当前节点的父节点Node* parent nullptr;while (cur){parent cur;if (cur-_key key)cur cur-_left;else if (cur-_key key) cur cur-_right;else return false;}//找到插入的地方直接newcur new Node(key);//判断插入到父节点的左节点还是右节点if (parent-_key key) parent-_right cur;else parent-_left cur;return true;
}3.中序遍历
对于中序遍历我们需要写一个辅助函数来传递当前this指针对应的root。
void InOrder()
{_InOrder(_root);
}
void _InOrder(Node* root)
{if (root nullptr) return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);
}4.删除操作
插入操作分三种情况 我们拿下面这个二叉搜索树为例子
将节点进行归类 我们先讨论删除没有孩子的节点对于没有孩子的节点我们可以直接进行删除。 其次我们来讨论删除一个孩子的节点假如我们删除14我们需要知道14的父亲将10和14的左孩子串起来。 可以将一个孩子的节点归结为这几种情况。 接下来就是有两个孩子的节点 我们拿3这个节点为例子
删除3节点我们应该用左子树最大或者右子树最小进行替换然后转化成删除左子树最大或者右子树最小的节点就相当于把删除有两个孩子的节点转换成删除一个孩子的节点或者没有孩子的节点。
bool Erase(const K key)
{//三种情况//1.一个孩子//2.没有孩子//3.两个孩子左子树的最大右子树的最小//左子树的最左右子树的最右Node* cur _root;Node* parent nullptr;while (cur){if (cur-_key key){parent cur;cur cur-_left;}else if (cur-_key key){parent cur;cur cur-_right;}else{//删除//0-1个孩子的情况if (cur-_left nullptr){//删除根节点的情况if (parent nullptr)_root cur-_right;else{if (parent-_left cur) parent-_left cur-_right;else parent-_right cur-_right;}delete cur;return true;}else if (cur-_right nullptr){//删除根节点if (parent nullptr) _root cur-_left;else{if (parent-_left cur)parent-_left cur-_left;else parent-_left cur-_left;}delete cur;return true;}//两个孩子的情况else{//找右子树最小的节点作为最大的节点Node* rightminp nullptr;Node* rightmin cur-_right;//left不为空就一直向left走while (rightmin-_left ! nullptr){rightminp rightmin;rightmin rightmin-_left;}cur-_key rightmin-_key;if (rightminp ! nullptr) rightminp-_left rightmin-_right;else cur-_right rightmin-_right;delete rightmin;return true;}}}return false;
}删除成功返回true删除失败没找到则返回false。
所有代码
#pragma once
#includeiostream
using namespace std;
templateclass K
struct BSTreeNode
{K _key;BSTreeNodeK* _left;BSTreeNodeK* _right;BSTreeNode(const K key):_key(key), _left(nullptr), _right(nullptr){}
};templateclass K
class BSTree
{typedef BSTreeNodeK Node;
public:bool Insert(const K key){if (_root nullptr){_root new Node(key);return true;}Node* cur _root;Node* parent nullptr;while (cur){parent cur;if (cur-_key key)cur cur-_left;else if (cur-_key key) cur cur-_right;else return false;}cur new Node(key);if (parent-_key key) parent-_right cur;else parent-_left cur;return true;}bool Find(const K key){Node* cur _root;while (cur){if (cur-_key key)cur cur-_left;else if (cur-_key key) cur cur-_right;else return true;}return false;}bool Erase(const K key){//三种情况//1.一个孩子//2.没有孩子//3.两个孩子左子树的最大右子树的最小//左子树的最左右子树的最右Node* cur _root;Node* parent nullptr;while (cur){if (cur-_key key){parent cur;cur cur-_left;}else if (cur-_key key){parent cur;cur cur-_right;}else{//删除//0-1个孩子的情况if (cur-_left nullptr){//删除根节点的情况if (parent nullptr)_root cur-_right;else{if (parent-_left cur) parent-_left cur-_right;else parent-_right cur-_right;}delete cur;return true;}else if (cur-_right nullptr){//删除根节点if (parent nullptr) _root cur-_left;else{if (parent-_left cur)parent-_left cur-_left;else parent-_left cur-_left;}delete cur;return true;}//两个孩子的情况else{//找右子树最小的节点作为最大的节点Node* rightminp nullptr;Node* rightmin cur-_right;//left不为空就一直向left走while (rightmin-_left ! nullptr){rightminp rightmin;rightmin rightmin-_left;}cur-_key rightmin-_key;if (rightminp ! nullptr) rightminp-_left rightmin-_right;else cur-_right rightmin-_right;delete rightmin;return true;}}}return false;}void InOrder(){_InOrder(_root);}
private:void _InOrder(Node* root){if (root nullptr) return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}Node* _root nullptr;
};总结
二叉搜索树BST是一种在计算机科学中广泛应用的数据结构具有高效的查找、插入和删除操作。通过遵循节点值的有序性规则BST能够在平均情况下实现对数时间复杂度的操作使其成为处理动态数据集的理想选择。
在本篇博客中我们详细介绍了二叉搜索树的定义和性质并通过示例展示了其基本结构。我们还探讨了BST的三大主要操作插入、查找和删除并分析了这些操作的实现方法和时间复杂度。
尽管二叉搜索树在平衡状态下具有高效的性能但在最坏情况下BST可能会退化成链表。因此在实际应用中经常需要采用自平衡二叉搜索树如AVL树和红黑树来保证其性能。
通过对BST的深入理解和实践相信你能够在各种编程场景中灵活运用这一重要的数据结构从而提高程序的效率和性能。如果你对二叉搜索树有任何疑问或希望了解更多高级应用欢迎在评论区留言讨论。
