无锡企业网站制作公司,天猫网站设计分析,永久云服务器免费领,企网官方网站#x1f525; 个人主页#xff1a;大耳朵土土垚 #x1f525; 所属专栏#xff1a;C从入门至进阶 这里将会不定期更新有关C/C的内容#xff0c;欢迎大家点赞#xff0c;收藏#xff0c;评论#x1f973;#x1f973;#x1f389;#x1f389;#x1f389; 文章目录… 个人主页大耳朵土土垚 所属专栏C从入门至进阶 这里将会不定期更新有关C/C的内容欢迎大家点赞收藏评论 文章目录 1.二叉搜索树2.二叉搜索树的功能3.二叉搜索树的实现✨二叉搜索树的结构✨插入函数Insert()✨查找函数Find()✨删除函数Erase()✨中序遍历InOrder()✨析构函数 4.二叉搜索树的应用5.二叉搜索树的性能分析6.结语 1.二叉搜索树 二叉搜索树(BST,Binary Search Tree)又称二叉排序树是一种特殊的二叉树它或者是一棵空树或者是具有以下性质的二叉树:
若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 二叉搜索树Binary Search Tree的每个节点的左子树中的所有节点都比该节点小右子树中的所有节点都比该节点大。这个特性使得二叉搜索树可以用来实现非常高效的查找、插入和删除操作。 2.二叉搜索树的功能
二叉搜索树是一种特殊的二叉树它具有以下功能
插入节点可以将一个新节点插入到二叉搜索树中。
void TestBSTree()
{
//插入节点BSTreestring, string dict;dict.Insert(insert, 插入);dict.Insert(erase, 删除);dict.Insert(select, 查找);dict.Insert(sort, 排序);
}这里实现的二叉搜索树每次插入的是两个值模拟键值对二叉搜索树的节点除了左右子节点指针也不再只存储一个值而是两个。也就是说当我们知道一个值时就可以利用它来查找另外一个值。 键值对key-value pair是指在计算机科学中用来存储和表示数据的一种结构。它由两部分组成键key和值value。键是一个唯一的标识符用来定位和访问值值是与键相关联的数据。例如一个简单的键值对可以表示一个人的姓名和年龄键是“姓名”值是“张三”键是“年龄”值是“25”。 删除节点可以删除二叉搜索树中的一个节点。
void TestBSTree()
{BSTreestring, string dict;dict.Insert(insert, 插入);dict.Insert(erase, 删除);dict.Insert(select, 查找);dict.Insert(sort, 排序);//删除节点dict.Erase(insert);
}查找节点可以根据给定的值在二叉搜索树中查找对应的节点。
void TestBSTree()
{BSTreestring, string dict;dict.Insert(insert, 插入);dict.Insert(erase, 删除);dict.Insert(select, 查找);dict.Insert(sort, 排序);dict.Erase(insert);//查找节点cout dict.Find(sort)-_value endl;
}结果如下 中序遍历的结果是有序的中序遍历二叉搜索树可以得到一个有序序列。
void TestBSTree()
{BSTreestring, string dict;dict.Insert(insert, 插入);dict.Insert(erase, 删除);dict.Insert(select, 查找);dict.Insert(sort, 排序);//中序遍历dict.InOrder();
}结果如下 中序遍历的结果按照字符串大小比较的顺序排列。 这些是二叉搜索树的一些基本功能。通过这些功能可以实现对二叉搜索树的插入、删除、查找等操作以及对二叉搜索树的遍历和查询。
3.二叉搜索树的实现 二叉搜索树的实现首先需要一个节点类包含节点的键值、左子节点和右子节点三个属性来存放一个一个的节点:
//节点类
templateclass K, class V
struct BSTreeNode
{//键值对K _key;V _value;//左右子节点struct BSTreeNode* _left;struct BSTreeNode* _right;//默认构造BSTreeNode(const K key K(), const V value V()):_key(key),_value(value),_left(nullptr),_right(nullptr){}};✨二叉搜索树的结构
templateclass K, class V
class BSTree
{typedef BSTreeNodeK, V Node;
public:bool Insert(const K key, const V value);//插入Node* Find(const K key);//查找bool Erase(const K key);//删除void InOrder();//中序遍历~BSTree();//析构
private:void _InOrder(Node* root);Node* _root nullptr;
};
测试代码如下
//测试代码
void TestBSTree()
{BSTreestring, string dict;dict.Insert(insert, 插入);dict.Insert(erase, 删除);dict.Insert(select, 查找);dict.Insert(sort, 排序);string str;while (cinstr){auto ret dict.Find(str);if (ret){cout str : ret-_value endl;}else{cout 单词拼写错误 endl;}}string strs[] { 苹果, 西瓜, 苹果, 樱桃, 苹果, 樱桃, 苹果, 樱桃, 苹果 };// 统计水果出现的次BSTreestring, int countTree;for (auto str : strs){auto ret countTree.Find(str);if (ret NULL){countTree.Insert(str, 1);}else{ret-_value;}}countTree.InOrder();
}✨插入函数Insert() 插入新节点时我们首先需要借助节点的类来构建新节点然后判断插入二叉搜索树的位置因为二叉树的左子树的节点总是小于根节点右子树总是大于根节点所以不能随便插入确定好插入位置后将新节点插入到二叉搜索树中。
bool Insert(const K key, const V value)
{//创建新节点Node* newnode new Node(key, value);//当二叉搜索树为空时if (_root nullptr){_root newnode;return true;}//二叉搜索树不为空Node* cur _root;Node* parent _root;//记录父节点//遍历节点找到插入位置while (cur! nullptr){if (cur-_key key){parent cur;cur cur-_left;}else if (key cur-_key){parent cur;cur cur-_right;}else{//相等时插入失败return false;}}//判断是插入parent节点的左节点还是右节点if(keyparent-_key){parent-_right newnode;}else{parent-_left newnode;}return true;
}因为二叉搜索树的性质所以我们只需要比较节点的_key值即可如果插入的节点的_key值比当前节点大就往当前节点的右子树寻找反正就往左子树寻找合适的位置如果相等就插入失败返回false因为这里的二叉搜索树不能存储相同的节点。 其次找到合适位置后我们还需要记录该位置的父节点一遍将新节点与二叉搜索树链接在一起有了插入位置的父节点然后判断是插入左边还是右边即可完成插入返回true。 ✨查找函数Find() 查找函数其实在插入函数时确定新节点插入的位置就已经实现了类似的逻辑不同的是如果插入时找到相同的节点则插入失败而查找时找到相同的节点则查找成功返回该节点的指针即可。
Node* Find(const K key)
{Node* cur _root;while (cur! nullptr){if (cur-_key key){cur cur-_left;}else if (key cur-_key){cur cur-_right;}else{//相等时找到了return cur;}}//这里表示没找到return nullptr;
}这里使用循环遍历二叉搜索树来查找当root不为空并且还没有找到时就会一直查找而当root为空并且还没有找到此时就可以返回空指针表示当前二叉搜索树不存在要查找的节点。 ✨删除函数Erase() 删除函数的逻辑较为复杂一些首先要查找到删除的节点没有找到就返回False如果找到那么我们需要根据该节点的位置或者说该节点有几个子节点来实现不同的删除逻辑。 如果被删除的节点没有子节点或是只有一个子节点都比较容易解决只有把父节点指向该节点的子节点即可如果没有子节点则让父节点指向空即可所以一个节点和没有节点的情况可以综合起来考虑上述代码为了逻辑清晰分开考虑了大家也可以根据自己的想法选择。 如果有两个子节点删除该节点那他的两个孩子该怎么办呢所以我们应该从其右子树所有节点中选择最小的那一个minright节点替代被删除的节点root这样替代后左子树的所有节点依然小于minright右子树的所有节点依然大于minright满足二叉搜索树的性质。当然也可以选择左子树的最大节点maxleft来替代root。 替代可以选择交换节点内部的键值也可以直接交换节点的指针交换键值较容易一些这里选择交换键值。 bool Erase(const K key)
{//没有节点if (_root nullptr){return false;}//先找到再删除释放Node* cur _root;Node* parent _root;//记录父节点while (cur ! nullptr){if (cur-_key key){parent cur;cur cur-_left;}else if (key cur-_key){parent cur;cur cur-_right;}else{//找到判断要被删除的节点有几个子节点//1.没有子节点if (cur-_left nullptr cur-_right nullptr){//判断该节点是在父节点的左边还是右边if (parent-_key cur-_key){//在左边parent-_left nullptr;delete cur;}else if(cur-_key parent-_key){//在右边parent-_right nullptr;delete cur;}else{//就是根节点delete cur;_root nullptr;}}//2.只有一个节点else if (cur-_right nullptr){//先看只有左节点的情况//判断该节点是在父节点的左边还是右边if (parent-_key cur-_key){//在左边parent-_left cur-_left;delete cur;}else if(cur-_key parent-_key){//在右边parent-_right cur-_left;delete cur;}else{//根节点_root cur-_left;delete cur;}}//2.只有一个节点else if (cur-_left nullptr){//只有右节点的情况//判断该节点是在父节点的左边还是右边if (parent-_key cur-_key){//在左边parent-_left cur-_right;delete cur;}else if(cur-_key parent-_key){//在右边parent-_right cur-_right;delete cur;}else{//根节点_root cur-_right;delete cur;}}//3.有两个节点的情况else{//先找右边最小的值交换Node* minright cur-_right;Node* pminright cur;//记录父节点while (minright-_left){Node* pminright minright;//记录父节点minright minright-_left;}//找到后,将minright节点的位置删除if (pminright-_right minright){pminright-_right minright-_right;}else{pminright-_left minright-_right;}//交换节点的值即可cur-_key minright-_key;cur-_value minright-_value;delete minright;}return true;}}//没找到删除失败return false;}删除同样需要将删除的节点的父节点与子节点链接起来所以需要一个parent指针来记录删除节点的父节点当然如果父节点就是自己那么表示删除的是根节点这时我们又要另外考虑。 ✨中序遍历InOrder() 中序遍历就可以使用我们学习二叉树时的递归来实现非常简单。 void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_key : root-_value endl;_InOrder(root-_right);}这里因为递归需要传递根节点的参数而我们在使用时_root是私有的我们没办法直接传参所以我们可以在类中嵌套一层函数将需要传参的函数设为私有这样对外我们就不需要再传参了。 ✨析构函数 析构函数也直接使用递归删除节点即可但是注意要使用后序遍历最后释放根节点如果先释放根节点会找不到子节点会报错。 ~BSTree(){_Order(_root);}
private:void _Order(Node* root){if (root nullptr){return;}_Order(root-_left);_Order(root-_right);delete root;}4.二叉搜索树的应用
比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对
void TestBSTree()
{BSTreestring, string dict;dict.Insert(insert, 插入);dict.Insert(erase, 删除);dict.Insert(select, 查找);dict.Insert(sort, 排序);//dict.InOrder();string str;while (cin str){auto ret dict.Find(str);if (ret){cout str : ret-_value endl;}else{cout 单词拼写错误 endl;}}
}再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word, count就构成一种键值对
void TestBSTree()
{
string strs[] { left, left, up, down, left, right, left, up, right };
// 统计单词出现的次数
BSTreestring, int countTree;
for (auto str : strs)
{auto ret countTree.Find(str);if (ret NULL){countTree.Insert(str, 1);}else{ret-_value;}
}
countTree.InOrder();
}结果如下 5.二叉搜索树的性能分析 插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数即结点越深则比较次数越多。 但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为 l o g 2 N log_2 N log2N 最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为 N 2 \frac{N}{2} 2N
6.结语 二叉搜索树可以帮助我们实现排序和去重但是需要注意的是二叉搜索树的性能取决于树的形状。如果树的形状接近于链表性能可能会下降最坏情况下时间复杂度可能达到O(n)其中n为树中的结点数。为了避免这种情况可以采用平衡二叉搜索树如AVL树、红黑树等保持树的平衡性从而提高操作的效率。以上就是今天所有的内容啦~ 完结撒花~
