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

wordpress建立多站点做诚信通谁给做网站

news 2025/9/18 7:12:38
wordpress建立多站点,做诚信通谁给做网站,微信电商小程序怎么做,营业推广的方式接下来我们来开始使用C来详细讲解数据结构的一些高阶的知识点 本期讲解的是二叉搜索树，对于初阶二叉树有所遗忘的同学可以看到这里： 【精选】【数据结构初阶】链式二叉树的解析及一些基本操作 讲解二叉搜索树主要是为了后面的map和set做铺垫&#xff…

接下来我们来开始使用C++来详细讲解数据结构的一些高阶的知识点

本期讲解的是二叉搜索树，对于初阶二叉树有所遗忘的同学可以看到这里：

【精选】【数据结构初阶】链式二叉树的解析及一些基本操作

讲解二叉搜索树主要是为了后面的map和set做铺垫，废话不多说我们直接上干货：

目录

一、二叉搜索树的概念

二、模拟实现二叉搜索树

2.1 插入数据

2.1.1 插入数据的非递归实现

2.2 遍历数据

2.3 查找数据

2.4 删除数据

2.4.1 删除数据的非递归实现

2.5 模拟实现二叉搜索树的全部代码

一、二叉搜索树的概念

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

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

 例如：

 

我们可以发现的一点：无论是什么样的二叉搜索树，使用中序遍历，遍历出的值都是升序排列的

二、模拟实现二叉搜索树

下面又到了我们最激动人心的代码实现环节，本次代码实现我们还是要基于链式二叉树的实现：

template<class K>
struct BSTreeNode//节点
{BSTreeNode<K>* _lchild;BSTreeNode<K>* _rchild;K _key;BSTreeNode(const K& key):_lchild(nullptr),_rchild(nullptr),_key(key){}
};

2.1 插入数据

我们可以根据二叉搜索树的规律来向其中插入数据，但是插入数据时需要注意一点：要记录插入节点的上一个父节点，将插入的节点连接上二叉树：

template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);_root->_key = key;return true;}Node* cur = _root;//使用cur遍历二叉树找到合适的插入位置Node* parent = cur;//记录cur的父节点while (cur){parent = cur;if (key < cur->_key){cur = cur->_lchild;}else if (key > cur->_key){cur = cur->_rchild;}else{return false;//这里创建的二叉搜索树不允许出现值的冗余}}cur = new Node(key);//创建//将创建的节点链接到二叉树上if (key < parent->_key){parent->_lchild = cur;}else{parent->_rchild = cur;}return true;}private:Node* _root = nullptr;//根节点
};

2.1.1 插入数据的非递归实现

递归的效率并没有循环高，那为什么要说一下插入数据的非递归实现呢

主要是非递归的数据插入的传值方法值得一说：

template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool InsertR(const K& key)//插入数据(递归){return _InsertR(_root, key);}bool _InsertR(Node*& root,const K& key)//这里使用指针的引用用来直接修改其父节点指针的指向{if (root == nullptr){root = new Node(key);return true;}if (root->_key > key){_InsertR(root->_lchild, key);}else if (root->_key < key){_InsertR(root->_rchild, key);}else{return false;}}
private:Node* _root = nullptr;//根节点
};

我们可以看到在递归时，传入的形参类型为Node*&，这样可以直接在其函数内部习惯其父节点孩子指针的指向

那为什么要写两个插入函数呢？因为如果我们直接使用_InsertR函数，无法直接使用对象对_InsertR函数进行传参

2.2 遍历数据

因为二叉搜索树的性质，这里我们采用中序遍历： 

template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key)插入数据{....}void InOrder()//中序遍历{_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == NULL)//如果是空树就直接结束{return;}_InOrder(root->_lchild);//先递归遍历其左子树cout << root->_key << " ";//再遍历其根节点_InOrder(root->_rchild);//最后递归遍历其右子树}private:Node* _root = nullptr;//根节点
};

那为什么要写两个中序遍历函数呢？因为如果我们直接使用_InOrder函数，无法直接使用对象对_InOrder函数进行传参

2.3 查找数据

template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key)//插入数据{......}void InOrder()//中序遍历{......}void _InOrder(Node* root){......}bool Find(const K& key)//查找数据{Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_rchild;}else if (cur->_key > key){cur = cur->_lchild;}else{return true;}}return false;}private:Node* _root = nullptr;//根节点
};

2.4 删除数据

对于在二叉搜索树中删除数据，我们就要好好说道说道了

下面我们有这样的一个二叉搜索树：

现在我们要删除其叶子节点，这很容易，直接删除完，再将其父节点对应的孩子指针置空即可

那我们要删只有一个孩子节点的数据呢？例如14和10

这个稍微麻烦一点，删除完该节点后将其孩子节点托付给其父节点即可：

那要删带有两个孩子节点的数据呢？例如3、6、8：

对于这种情况我们可以选择其节点下的左子树的最大节点（左子树的最右节点），或者右子树的最小节点（右子树的最左节点）来替代要删除的节点：

综上所述，要删除的结点可能分下面四种情况：

a. 要删除的结点无孩子结点

b. 要删除的结点只有左孩子结点 

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：

情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除

情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除

情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题--替换法删除

思路我们有了，下面用代码来实现一下：

template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key)//插入数据{...}void InOrder()//中序遍历{...}private:void _InOrder(Node* root){...}public:bool Find(const K& key)//查找数据{...}bool Erase(const K& key){Node* cur = _root;//使用cur遍历二叉树找到要删除元素的位置Node* parent = cur;//记录cur的父节点while (cur)//寻找需要删除的节点{if (cur->_key < key){parent = cur;cur = cur->_rchild;}else if (cur->_key > key){parent = cur;cur = cur->_lchild;}else//找到了,开始删除{if (cur->_lchild == cur->_rchild && cur->_lchild == nullptr)//删除的节点为叶子节点{if (parent == cur)//删除的是根节点{_root = nullptr;//更新根节点}//将其父节点指向的自身的指针置空else if (parent->_lchild == cur){parent->_lchild = nullptr;}else{parent->_rchild = nullptr;}//释放节点空间delete cur;cur = nullptr;}else if (cur->_rchild == nullptr)//删除的节点右孩子为空,左孩子不为空{if (parent == cur)//删除的是根节点{_root = cur->_lchild;//更新根节点}//将删除节点的左孩子交给其父节点else if (parent->_lchild == cur){parent->_lchild = cur->_lchild;}else{parent->_rchild = cur->_lchild;}//释放节点空间delete cur;cur = nullptr;}else if (cur->_lchild == nullptr)//删除的节点左孩子为空,右孩子不为空{if (parent == cur)//删除的是根节点{_root = cur->_rchild;//更新根节点}//将删除节点的右孩子交给其父节点else if (parent->_lchild == cur){parent->_lchild = cur->_rchild;}else{parent->_rchild = cur->_rchild;}//释放节点空间delete cur;cur = nullptr;}else//删除的节点左右孩子都不为空,要找到删除节点的左子树的最大节点或右子树的最小节点可将其替换{//这里找要删除节点的左子树的最大节点（右子树的最小节点也可）Node* maxleft = cur->_lchild; // 记录左子树的最大节点Node* pmaxleft = cur;//记录左子树的最大节点的父节点while (maxleft->_rchild)//查找左子树的最大节点{pmaxleft = maxleft;maxleft = maxleft->_rchild;}//将找到的节点替换要删除的节点cur->_key = maxleft->_key;if (pmaxleft->_lchild == maxleft){pmaxleft->_lchild = maxleft->_lchild;}else{pmaxleft->_rchild = maxleft->_lchild;}//释放节点空间delete maxleft;maxleft = nullptr;}return true;}}return false;//没找到要删除的节点}
private:Node* _root = nullptr;//根节点
};

2.4.1 删除数据的非递归实现

template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool EraseR(const K& key)//递归删除数据{return _EraseR(_root, key);}bool _EraseR(Node*& root, const K& key){if (root == nullptr){return false;}else if (root->_key < key){_EraseR(root->_rchild, key);}else if (root->_key > key){_EraseR(root->_lchild, key);}else{Node* del = root;if (root->_lchild == root->_rchild && root->_lchild == nullptr)//删除的节点为叶子节点{//释放节点空间delete root;//将其父节点指向的自身的指针置空root = nullptr;}else if (root->_rchild == nullptr)//删除的节点右孩子为空,左孩子不为空{//将删除节点的左孩子交给其父节点root = root->_lchild;//释放节点空间delete del;del = nullptr;}else if (root->_lchild == nullptr)//删除的节点左孩子为空,右孩子不为空{//将删除节点的右孩子交给其父节点root = root->_rchild;//释放节点空间delete del;del = nullptr;}else//删除的节点左右孩子都不为空,要找到删除节点的左子树的最大节点或右子树的最小节点将其替换{//这里找要删除节点的右子树的最小节点（左子树的最大节点也可）Node* minright = del->_rchild; // 记录右子树的最小节点while (minright->_lchild)//查找右子树的最小节点{minright = minright->_lchild;}root->_key = minright->_key;//将找到的节点替换要删除的节点return _EraseR(root->_rchild, root->_key);//继续递归删除其右子树中用来替换的节点}return true;}}private:Node* _root = nullptr;//根节点
};

 

2.5 模拟实现二叉搜索树的全部代码

#include<iostream>
using namespace std;template<class K>
struct BSTreeNode//节点
{BSTreeNode<K>* _lchild;BSTreeNode<K>* _rchild;K _key;BSTreeNode(const K& key):_lchild(nullptr),_rchild(nullptr),_key(key){}
};template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key)//插入数据{if (_root == nullptr)//如果根节点为空就直接插入{_root = new Node(key);_root->_key = key;return true;}Node* cur = _root;//使用cur遍历二叉树找到合适的插入位置Node* parent = cur;//记录cur的父节点while (cur){parent = cur;if (key < cur->_key){cur = cur->_lchild;}else if (key > cur->_key){cur = cur->_rchild;}else{return false;//这里创建的二叉搜索树不允许出现值的冗余}}cur = new Node(key);//创建//将创建的节点链接到二叉树上if (key < parent->_key){parent->_lchild = cur;}else{parent->_rchild = cur;}return true;}bool InsertR(const K& key)//插入数据(递归){return _InsertR(_root, key);}private:bool _InsertR(Node*& root,const K& key)//这里使用指针的引用用来直接修改其父节点指针的指向{if (root == nullptr){root = new Node(key);return true;}if (root->_key > key){_InsertR(root->_lchild, key);}else if (root->_key < key){_InsertR(root->_rchild, key);}else{return false;}}public:void InOrder()//中序遍历{_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){if (root == NULL)//如果是空树就直接结束{return;}_InOrder(root->_lchild);//先递归遍历其左子树cout << root->_key << " ";//再遍历其根节点_InOrder(root->_rchild);//最后递归遍历其右子树}public:bool Find(const K& key)//查找数据{Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_rchild;}else if (cur->_key > key){cur = cur->_lchild;}else{return true;}}return false;}bool Erase(const K& key)//删除数据{Node* cur = _root;//使用cur遍历二叉树找到要删除元素的位置Node* parent = cur;//记录cur的父节点while (cur)//寻找需要删除的节点{if (cur->_key < key){parent = cur;cur = cur->_rchild;}else if (cur->_key > key){parent = cur;cur = cur->_lchild;}else//找到了,开始删除{if (cur->_lchild == cur->_rchild && cur->_lchild == nullptr)//删除的节点为叶子节点{if (parent == cur)//删除的是根节点{_root = nullptr;//更新根节点}//将其父节点指向的自身的指针置空else if (parent->_lchild == cur){parent->_lchild = nullptr;}else{parent->_rchild = nullptr;}//释放节点空间delete cur;cur = nullptr;}else if (cur->_rchild == nullptr)//删除的节点右孩子为空,左孩子不为空{if (parent == cur)//删除的是根节点{_root = cur->_lchild;//更新根节点}//将删除节点的左孩子交给其父节点else if (parent->_lchild == cur){parent->_lchild = cur->_lchild;}else{parent->_rchild = cur->_lchild;}//释放节点空间delete cur;cur = nullptr;}else if (cur->_lchild == nullptr)//删除的节点左孩子为空,右孩子不为空{if (parent == cur)//删除的是根节点{_root = cur->_rchild;//更新根节点}//将删除节点的右孩子交给其父节点else if (parent->_lchild == cur){parent->_lchild = cur->_rchild;}else{parent->_rchild = cur->_rchild;}//释放节点空间delete cur;cur = nullptr;}else//删除的节点左右孩子都不为空,要找到删除节点的左子树的最大节点或右子树的最小节点可将其替换{//这里找要删除节点的左子树的最大节点（右子树的最小节点也可）Node* maxleft = cur->_lchild; // 记录左子树的最大节点Node* pmaxleft = cur;//记录左子树的最大节点的父节点while (maxleft->_rchild)//查找左子树的最大节点{pmaxleft = maxleft;maxleft = maxleft->_rchild;}//将找到的节点替换要删除的节点cur->_key = maxleft->_key;if (pmaxleft->_lchild == maxleft){pmaxleft->_lchild = maxleft->_lchild;}else{pmaxleft->_rchild = maxleft->_lchild;}//释放节点空间delete maxleft;maxleft = nullptr;}return true;}}return false;//没找到要删除的节点}bool EraseR(const K& key)//递归删除数据{return _EraseR(_root, key);}private:bool _EraseR(Node*& root, const K& key){if (root == nullptr){return false;}else if (root->_key < key){_EraseR(root->_rchild, key);}else if (root->_key > key){_EraseR(root->_lchild, key);}else{Node* del = root;if (root->_lchild == root->_rchild && root->_lchild == nullptr)//删除的节点为叶子节点{//释放节点空间delete root;//将其父节点指向的自身的指针置空root = nullptr;}else if (root->_rchild == nullptr)//删除的节点右孩子为空,左孩子不为空{//将删除节点的左孩子交给其父节点root = root->_lchild;//释放节点空间delete del;del = nullptr;}else if (root->_lchild == nullptr)//删除的节点左孩子为空,右孩子不为空{//将删除节点的右孩子交给其父节点root = root->_rchild;//释放节点空间delete del;del = nullptr;}else//删除的节点左右孩子都不为空,要找到删除节点的左子树的最大节点或右子树的最小节点将其替换{//这里找要删除节点的右子树的最小节点（左子树的最大节点也可）Node* minright = del->_rchild; // 记录右子树的最小节点while (minright->_lchild)//查找右子树的最小节点{minright = minright->_lchild;}root->_key = minright->_key;//将找到的节点替换要删除的节点return _EraseR(root->_rchild, root->_key);//继续递归删除其右子树中用来替换的节点}return true;}}private:Node* _root = nullptr;//根节点
};

本期博客到这里就结束了，代码量较大，还请各位仔细分析呀

我们下期见~

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

相关文章：

  • 合肥效果好的网站推广淮安百度网站建设
  • 南宁营销型网站建设哪家好wordpress 虎嗅2016
  • 砀山哪有做网站的红色大气企业网站
  • 网站用什么开发创意设计人才网
  • 网站设计特点环球资源网的定位
  • 网站空间租赁合同app开发比较好的公司
  • 如何建立网站管理系统58同城最新消息招聘
  • 公司网站关键词优化怎么做常州企业网站
  • 网站建设易网网站建设 不需要见面
  • 易迈互联网站建设怎么样做微信的网站有哪些功能
  • 个人网站主页设计免费logo设计自动生成器
  • 网站开发培训网wordpress的管理员权限代码
  • 印刷网站建设价格免费网络营销推广软件
  • 自己做网站上市win8风格企业网站
  • 西柏坡门户网站建设规划书郑州手机软件开发
  • 石景山上海网站建设沈阳关键词快照优化
  • wordpress上传图片兰州企业网络推广优化
  • 影视网站开发工程师展会电子商务网站如何建设
  • 世界杯视频直播网站福州seo关键字推广
  • 网站制作自学网chatgpt 链接
  • 企业网站建设专业服务小语种外贸网站
  • 为网站做seowordpress 公司模板
  • 网站建设的基本步骤是哪些互助盘网站怎么做的
  • 装企营销网站建设网站制作最
  • 一朋友做网站网站被抓了php招投标网站源码
  • 重庆宣网站建设重庆网站建设公司多少钱
  • 短网址还原网站网站建设体会心得
  • 网站制作 需要什么网络技术美工培训课程线上
  • 如何把网站做的和别人一样简历制作网址
  • 网站开发毕设需求分析网站搭建免费模板