当前位置： 首页 > news >正文

南京建站平台网站打不开 ...

news 2025/9/17 2:44:08
南京建站平台,网站打不开 ...,品牌的佛山网站建设价格,王也高清壁纸第三季目录 一、二叉搜索树 1.1 概念 1.2 二叉搜索树操作 二、二叉搜索树实现 2.1 框架总览 2.2 实现接口总览 2.2.1 构造函数 2.2.2 拷贝构造 2.2.3 赋值重载 2.2.4 析构函数 2.2.5 二叉搜索树的遍历 2.2.6 插入函数 2.2.7 查找函数 2.2.8 删除函数 2.3 二叉搜索数完整…

目录

一、二叉搜索树

1.1 概念

1.2 二叉搜索树操作

二、二叉搜索树实现

2.1 框架总览

2.2 实现接口总览

2.2.1 构造函数

2.2.2 拷贝构造

2.2.3 赋值重载

2.2.4 析构函数

2.2.5 二叉搜索树的遍历

2.2.6 插入函数

2.2.7 查找函数

2.2.8 删除函数

 2.3 二叉搜索数完整代码

三、二叉搜索树的应用

3.1 K模型

3.2 KV模型

四、二叉搜索树的性能分析

前言：二叉搜索树是数据结构初阶二叉树的一部分，二叉搜索树为后序所学的 map 和 set 做准备

一、二叉搜索树

1.1 概念

        二叉搜索树（BST，Binary Search Tree）又称二叉排序树，它或者是一棵空树，二叉树搜索树具有以下性质:

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

比如，下面就是一颗二叉搜索树 

左子树小于根节点，右子树大于根节点，每颗子树都保持这样的特性，这样的树就称为二叉搜索树

        二叉搜索树进行中序遍历，遍历出来的结果是有序的（升序），二叉搜索树一般都是去重的，即没有相同的值

1.2 二叉搜索树操作

二叉搜索树的主要接口就是插入、查找、删除、遍历

（1）查找（Find）

  1. 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找
  2. 最多查找高度次，走到到空，还没找到，这个值不存在

（2）插入（Insert）

插入一个节点，插入后保持二叉搜索树的性质，二叉搜索树实现下面解释

（3）删除（Erase）

删除一个节点，删除后保持二叉搜索树的性质，二叉搜索树实现下面解释

（4）遍历（InOrder）

使用中序遍历即可，遍历结果为升序序列

二、二叉搜索树实现

2.1 框架总览

        要实现二叉搜索树，我们首先需要实现一个节点类，结点类当中包含三个成员变量：结点的值、左指针、右指针，结点类当中只需实现一个构造函数即可

 二叉搜索树类（BSTree）里面的成员变量只要包含一个根节点 _root 即可

为了书写简单，对 BSTreeNode<K> 进行 typedef 为 Node

typedef BSTreeNode<K> Node

template<class K>
struct BSTreeNode
{BSTreeNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}K _key;BSTreeNode<K>* _left;BSTreeNode<K>* _right;
};template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public:private:Node* _root;
};

2.2 实现接口总览

template<class K>
struct BSTreeNode
{BSTreeNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}K _key;BSTreeNode<K>* _left;BSTreeNode<K>* _right;
};template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public://构造函数BSTree(){}//拷贝构造BSTree(const BSTree<K>& t){}//赋值重载BSTree<K>& operator=(BSTree<K> t){}//析构~BSTree(){}bool Insert(const K& key){}bool Find(const K& key){}bool Erase(const K& key){}//遍历搜索树void InOrder(){}private:Node* _root;
};

2.2.1 构造函数

构造函数非常简单，构造一个空树即可

//构造函数BSTree():_root(nullptr){}

2.2.2 拷贝构造

由于要进行递归操作，就不能把递归操作写在拷贝构造函数里面，需要另写一个函数，这个函数设置为私有，拷贝构造也是深拷贝

//拷贝构造
BSTree(const BSTree<K>& t)
{_root = Copy(t._root);
}private:Node* Copy(Node* root){if (root == nullptr){return nullptr;}Node* newRoot = new Node(root->_key);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}

2.2.3 赋值重载

赋值重载直接使用现代写法，复用拷贝构造，不解释了，赋值重载也是深拷贝

//赋值重载
BSTree<K>& operator=(BSTree<K> t)
{swap(_root, t._root);return *this;
}

2.2.4 析构函数

析构函数也是如此，需要进行递归操作，需要另写一个函数进行递归操作

//析构
~BSTree()
{Destroy(_root);_root = nullptr;
}private:void Destroy(Node* root){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;}

2.2.5 二叉搜索树的遍历

遍历使用中序遍历即可，遍历出来的结果是升序的，因为无法使用类成员变量，就无法传根进行递归遍历，所以也需要另写一个函数

代码如下： 

//遍历搜索树
void InOrder()
{_InOrder(_root);cout << endl;
}private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}

2.2.6 插入函数

根据二叉搜索树的性质，其插入操作非常简单：

  1. 如果是空树，则直接将插入结点作为二叉搜索树的根结点
  2. 如果不是空树，则按照二叉搜索树的性质进行结点的插入

若不是空树，插入结点的具体操作如下：

  • 若待插入结点的值小于根结点的值，则需要将结点插入到左子树当中
  • 若待插入结点的值大于根结点的值，则需要将结点插入到右子树当中
  • 若待插入结点的值等于根结点的值，则插入结点失败（二叉搜索树）

插入成功返回 true，插入失败返回 false 

代码如下： 

bool Insert(const K& key){//_root为空树if (_root == nullptr){_root = new Node(key);return true;}//不为空树，进行查找Node* parent = nullptr;Node* cur = _root;while (cur)//遇到空就结束{if (_root->_key > key)//在左子树{parent = cur;cur = cur->_left;}else if (_root->_key < key)//在右子树{parent = cur;cur = cur->_right;}else//相等，直接返回，不允许插入相同值{return false;}}cur = new Node(key);if (parent->_key > key)//parent节点的_key比key大，插入到左边{parent->_left = cur;}else//parent节点的_key比key小，插入到右边{parent->_right = cur;}return true;}

2.2.7 查找函数

根据二叉搜索树的特性,，分以下几种情况：

  1. 若树为空树，则查找失败，返回 false
  2. 若key值小于当前结点的值，则应该在该结点的左子树当中进行查找
  3. 若key值大于当前结点的值，则应该在该结点的右子树当中进行查找
  4. 若key值等于当前结点的值，则查找成功，返回 true
  5. 查找完了，还是没有找到，返回 false

代码如下： 

    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;}

2.2.8 删除函数

        二叉搜索树的删除函数是最难实现的，若是在二叉树当中没有找到待删除结点，则直接返回 false 表示删除失败即可，但若是找到了待删除结点，此时就有以下三种情况：

  1. 待删除结点的左子树为空
  2. 待删除结点的右子树为空
  3. 待删除结点的左右子树均不为空

下面进行一对一处理：

（1）待删除结点的左子树为空，即右子树不为空

        若待删除结点的左子树为空，那么当我们在二叉搜索树当中找到该结点后，只需先让其父结点指向该结点的右孩子结点，然后再将该结点释放便完成了该结点的删除，进行删除操作后仍保持二叉搜索树的特性

动图演示：

 （2）待删除结点的右子树为空，即左子树不为空

        若待删除结点的右子树为空，那么当我们在二叉搜索树当中找到该结点后，只需先让其父结点指向该结点的左孩子结点，然后再将该结点释放便完成了该结点的删除，进行删除操作后仍需要保持二叉搜索树的特性

动图演示：

 （3）待删除结点的左右子树均不为空

        若待删除结点的左右子树均不为空，那么当我们在二叉搜索树当中找到该结点后，可以使用替换法进行删除

有两种替换方法：可以将让待删除结点左子树当中值最大的结点，或是待删除结点右子树当中值最小的结点代替待删除结点被删除（下面都以最小的结点代替待删除为例）

        然后将待删除结点的值改为代替其被删除的结点的值即可，而代替待删除结点被删除的结点，必然左右子树当中至少有一个为空树，因此删除该结点的方法与前面说到的情（1）（2）的方法相同

注意：只能是待删除结点左子树当中值最大的结点，或是待删除结点右子树当中值最小的结点代替待删除结点被删除，因为只有这样才能使得进行删除操作后的二叉树仍保持二叉搜索树的特性

动图演示：

代码如下：

bool Erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else//找到了要删除的节点{//左为空,右不为空if (cur->_left == nullptr){if (cur == _root)//要删除的为根节点{_root = cur->_right;}else//非根节点{parent->_right = cur->_right;}delete cur;}else if (cur->_right == nullptr)//左不为空，右为空{if (cur == _root)//要删除的为根节点{_root = cur->_left;}else//非根节点{parent->_left = cur->_left;}delete cur;}else//左右不为空，替换删除{//左右不为空，需要左子树的最大值 或 右子树的左小值充当新的根（对被删除节点进行值替换，然后进行删除）Node* minParent = cur;Node* minRight = cur->_right;//这里选用最小值进行替换while (minRight->_left){minParent = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;//值替换，minRight换不换没影响，minRight是要被删除的//分两种情况if (minRight == minParent->_left){minParent->_left = minRight->_right;}else{minParent->_right = minRight->_right;}delete minRight;}return true;}}return false;
}

 2.3 二叉搜索数完整代码

BSTree.h

#pragma oncetemplate<class K>
struct BSTreeNode
{BSTreeNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}K _key;BSTreeNode<K>* _left;BSTreeNode<K>* _right;
};template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public://构造函数BSTree():_root(nullptr){}//拷贝构造BSTree(const BSTree<K>& t){_root = Copy(t._root);}//赋值重载BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}//析构~BSTree(){Destroy(_root);_root = nullptr;}bool Insert(const K& key){//_root为空树if (_root == nullptr){_root = new Node(key);return true;}//不为空树，进行查找Node* parent = nullptr;Node* cur = _root;while (cur)//遇到空就结束{if (_root->_key > key)//在左子树{parent = cur;cur = cur->_left;}else if (_root->_key < key)//在右子树{parent = cur;cur = cur->_right;}else//相等，直接返回，不允许插入相同值{return false;}}cur = new Node(key);if (parent->_key > key)//parent节点的_key比key大，插入到左边{parent->_left = cur;}else//parent节点的_key比key小，插入到右边{parent->_right = 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){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else//找到了要删除的节点{//左为空,右不为空if (cur->_left == nullptr){if (cur == _root)//要删除的为根节点{_root = cur->_right;}else//非根节点{parent->_right = cur->_right;}delete cur;}else if(cur->_right == nullptr)//左不为空，右为空{if (cur == _root)//要删除的为根节点{_root = cur->_left;}else//非根节点{parent->_left = cur->_left;}delete cur;}else//左右不为空，替换删除{//左右不为空，需要左子树的最大值 或 右子树的左小值充当新的根（对被删除节点进行值替换，然后进行删除）Node* minParent = cur;Node* minRight = cur->_right;//这里选用最小值进行替换while (minRight->_left){minParent = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;//值替换，minRight换不换没影响，minRight是要被删除的//分两种情况if (minRight == minParent->_left){minParent->_left = minRight->_right;}else{minParent->_right = minRight->_right;}delete minRight;}return true;}}return false;}//遍历搜索树void InOrder(){_InOrder(_root);cout << endl;}
private:void Destroy(Node* root){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;}Node* Copy(Node* root){if (root == nullptr){return nullptr;}Node* newRoot = new Node(root->_key);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}
private:Node* _root;
};

Test.cpp

#include <iostream>
using namespace std;#include "BSTree.h"void Test()
{BSTree<int> t;t.Insert(4);t.Insert(3);t.Insert(5);t.Insert(4);t.Insert(6);t.Insert(1);t.Insert(7);t.Insert(9);t.InOrder();//拷贝构造BSTree<int> t2 = t;t2.InOrder();//查找cout << t2.Find(1) << endl;cout << t2.Find(8) << endl;//赋值重载BSTree<int> t3;t3 = t;t3.InOrder();//删除t3.Erase(4);t3.InOrder();t3.Erase(5);t3.InOrder();t3.Erase(3);t3.InOrder();t3.Erase(7);t3.InOrder();
}int main()
{Test();return 0;
}

三、二叉搜索树的应用

3.1 K模型

K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

  1. 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
  2. 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误 

3.2 KV模型

KV模型：每一个关键码 Key，都有与之对应的值 Value，即<Key, Value>的键值对，通过Key查找 Value

该种方式在现实生活中非常常见：
        比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；

        再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对

四、二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能

        对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树

对于有n个结点的二叉搜索树：

  1. 最优的情况下，二叉搜索树为完全二叉树，其平均比较次数为：O(logN)
  2. 最差的情况下，二叉搜索树退化为单支树，其平均比较次数为：O(N / 2)

所以实际上，二叉搜索树在极端情况下是没办法保证效率的，因此由二叉搜索树又衍生出来了AVL树、红黑树，后面准备学 

----------------我是分割线---------------

文章到这里就结束了，下一篇即将更新

http://www.yayakq.cn/news/442250/

相关文章：

  • 网站模版源码市场部网页设计西安
  • 做网站需要会什么软件软件开发专业学校
  • 设计专业新手网站app界面设计总结
  • 网站与网站做外链好吗有没有教做帽子的网站
  • 做私活一个网站大概多少钱中国做跨境电商出口的网站
  • 具有价值的专业网站建设平台做网站前端需要编程基础吗
  • 浙江广发建设有限公司网站江门住房与城乡建设局官方网站
  • 建网站企业百姓畅言六安杂谈
  • 保险网站导航wordpress关键词调用
  • 自己模板做网站靖州建设局网站
  • 做网站在哪个地方买空间frontpage可以做网站吗
  • 国外刺绣图案设计网站网站建设整体设计流程
  • wordpress网站数据库seo营销策划
  • 陕西的网站建设公司自己做个网站需要几个软件
  • 可以做物理题的网站对网站的界面设计分析
  • 网站是否被kwordpress后台缺少菜单
  • 商城网站建设方案流程洛阳信息网
  • 锐酷网站建设教程网站建设开发合同模板
  • 合作建站方案制作搜索类网站
  • 企业网站建设会计分录对话弹窗在网站上浮动
  • 网站开发学哪一个好义乌网站建设多少钱
  • 想学做网站学什么编程语言html网页制作软件有哪些
  • 甘肃省住房城乡建设厅网站首页如何检查网站死链
  • 医院网站和微信公众号建设方案电子商务网站设计心得
  • 网站域名登录绿色主色调网站
  • 企业门户网站方案怎么新增网站推广
  • 建设银行网站背景上海企业联系方式
  • 建设网站是否等于开展网络营销动漫设计属于什么大类
  • 织梦末班和dw建设网站哪个方便优化做php网站开发能赚钱吗
  • 代做一个网站多少钱学编程哪家培训机构好