C++进阶：搜索树

server/2024/9/25 15:24:31/

目录

  • 1. 二叉搜索树
    • 1.1 二叉搜索树的结构
    • 1.2 二叉搜索树的接口及其优点与不足
    • 1.3 二叉搜索树自实现
      • 1.3.1 二叉树结点结构
      • 1.3.2 查找
      • 1.3.3 插入
      • 1.3.4 删除
      • 1.3.5 中序遍历
  • 2. 二叉树进阶相关练习
    • 2.1 根据二叉树创建字符串
    • 2.2 二叉树的层序遍历I
    • 2.3 二叉树层序遍历II
    • 2.4 二叉树最近公共祖先结点
    • 2.5 二叉树搜索与双向链表
    • 2.6 从前序与中序遍历序列构造二叉树
    • 2.7 从中序与后序遍历序列构造二叉树
    • 2.8 二叉树前序遍历（非递归）
    • 2.9 二叉树中序遍历（非递归）
    • !!!3.10 二叉树后序遍历（非递归）

1. 二叉搜索树

1.1 二叉搜索树的结构

  1. 搜索二叉树中的所有结点都满足
    <1> 若左子树不为空，则其所有结点的键值都小于父结点
    <2> 若右子树不为空，则其所有结点的键值都大于父节点
    <3> 左右子树都为二叉搜索树

在这里插入图片描述

1.2 二叉搜索树的接口及其优点与不足

  1. 搜索二叉树的功能接口
    <1> 数据插入（Insert）
    <2> 数据删除（Erase）
    <3> 数据查寻（Find）
    <4> 中序遍历（InOrder）
  1. 二叉搜索树的优点：
    <1> 正如其名，此种数据存储结构，尤其擅长数据搜索，其进行数据搜索的效率极高。
    <2> 在其结构为近似完全二叉树或满二叉树的情况时，其的搜索效率可以达到O( l o g N logN logN)
    <3> 当以中序遍历的方式遍历整棵搜索树时，得到的数据即为升序序列

在这里插入图片描述

  1. 二叉搜索树的不足：
    <1> 根据二叉搜索树的插入逻辑，当数据以完全升序或降序插入时，会使得二叉树退化为单枝结构，此种结构下其搜索效率也退化为O(N)

在这里插入图片描述

1.3 二叉搜索树自实现

1.3.1 二叉树结点结构

  1. 搜索树结点：由左右孩子结点指针与key组成
  2. 搜索树：由根节点与类方法构成
template<class T>
struct BinarySearchNode
{typedef BinarySearchNode<T> BSNode;BSNode* _left;BSNode* _right;T _key;BinarySearchNode(T key):_left(nullptr),_right(nullptr),_key(key){}
};template<class T>
class BinarySearchTree
{
public:typedef BinarySearchNode<T> BSNode;//查找bool Find(T key);//插入bool Insert(T key);//删除bool Erase(T key);//中序遍历void InOrder();private:BSNode* _root = nullptr;
};

1.3.2 查找

  1. 查找实现：在一颗搜索树中搜寻一个数据是否存在
  2. 查找逻辑：
    <1> 若查找值小于当前结点的key值，向左搜寻，向左孩子查找
    <2> 若查找值大于当前结点的key值，向右搜寻，向右孩子查找
    <3> 查找遍历至空结点，则证明搜索树中不存在此值
//非递归
bool Find(T key)
{BSNode* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}else{return true;}}return false;
}//递归
bool _FindR(BSNode* cur, T key)
{if (cur == nullptr){return false;}if (key < cur->_key){return _FindR(cur->_left, key);}else if (key > cur->_key){return _FindR(cur->_right, key);}else{return true;}//补全返回路径assert(true);return -1;
}bool FindR(T key)
{return _FindR(_root, key);
}

1.3.3 插入

  1. 搜寻插入位置：
    <1> key小向左
    <2> key大向右
    <3> 直至遍历到空
  2. <1> 若遇key相同的结点，停止插入，返回false
    <2> 遍历至空，创建结点，链接结点
//非递归
bool Insert(T key)
{//特殊处理根结点插入if (_root == nullptr){_root = new BSNode(key);return true;}BSNode* cur = _root;BSNode* parent = nullptr;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{return false;}}//确定插入位置if (key < parent->_key){parent->_left = new BSNode(key);}else{parent->_right = new BSNode(key);}return true;
}//递归
bool _InsertR(BSNode*& cur, T key)
{//存在单子树的情况，导致段错误//传引用if (cur == nullptr){cur = new BSNode(key);return true;}if (key < cur->_key){return _InsertR(cur->_left, key);}else if (key > cur->_key){return _InsertR(cur->_right, key);}else{return false;}assert(true);return false;
}bool InsertR(T key)
{if (_root == nullptr){_root = new BSNode(key);return true;}return _InsertR(_root, key);
}

1.3.4 删除

  1. 删除结点后，不能破坏搜索树的结构
  2. 删除不同类型结点的场景，删除逻辑：
    <1> 叶子结点，直接删除，父节点链接指针置空
    <2> 单子树结点，托孤，即，将自己的子树链接给父结点
    <3> 双子树结点，寻找key值最接近的结点（左子树的最右结点，右子树的最左结点），值替换被删除的结点，而后删除被替换的结点
  1. 叶子结点
    在这里插入图片描述
  2. 单子树结点
    在这里插入图片描述
  3. 双子树结点
    在这里插入图片描述
//非递归
bool Erase(T key)
{BSNode* cur = _root;BSNode* parent = nullptr;while (cur){//查找到删除结点的位置if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else//找到了{//叶子结点与单子树结点的删除//可以合并共用一套逻辑if (cur->_left == nullptr || cur->_right == nullptr)//叶子结点/单子树{//根结点特殊处理if (cur == _root){if (cur->_left){_root = cur->_left;}else{_root = cur->_right;}delete cur;}else//普通结点{//托孤if (cur->_left)//左单子树{if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}delete cur;}else//右单子树/叶子节点{if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}delete cur;}}return true;}else//双子树{//寻找右子树的最左结点BSNode* RightParent = cur;BSNode* RightMin = cur->_right;while (RightMin->_left){RightParent = RightMin;RightMin = RightMin->_left;}//值替换cur->_key = RightMin->_key;//删除被替换结点//删除结点的左孩子一定为空，所以按照右子树结点处理//托孤if (RightMin == RightParent->_left){RightParent->_left = RightMin->_right;}else{RightParent->_right = RightMin->_right;}//删除delete RightMin;return true;}}}//未找到return false;
}//递归
bool _EraseR(BSNode*& cur, T key)
{if (cur == nullptr){return false;}//寻找删除结点if (key < cur->_key){return _EraseR(cur->_left, key);}else if (key > cur->_key){return _EraseR(cur->_right, key);}else//找到了{//使用传引用后，对操作的优化if (cur->_left == nullptr || cur->_right == nullptr)//叶子结点/单子树结点{BSNode* del = cur;if (cur->_left){cur = cur->_left;}else{cur = cur->_right;}delete del;return true;}else//双子树{//寻找右子树的最左结点BSNode* RightMin = cur->_right;while (RightMin->_left){RightMin = RightMin->_left;}//值替换cur->_key = RightMin->_key;//值替换后，删除结点传值改变//转化为单子树删除，调用单子树删除处理_EraseR(cur->_right, cur->_key);}}assert(true);return false;
}

1.3.5 中序遍历

void _InOrder(BSNode* cur)
{if (cur == nullptr){return;}//左根右_InOrder(cur->_left);cout << cur->_key << " ";_InOrder(cur->_right);
}void InOrder()
{_InOrder(_root);cout << endl;
}

2. 二叉树进阶相关练习

2.1 根据二叉树创建字符串

  1. 题目信息：
    在这里插入图片描述
  2. 题目连接：
    根据二叉树创建字符串
class Solution 
{
public:void _tree2str(string& str, TreeNode* cur){if(cur == nullptr){return;}//字符串转字符串stoi（整形），stod（浮点型）str += to_string(cur->val);//除左空右不空的情况外，其余省略if(cur->left || cur->right){str += "(";_tree2str(str, cur->left);str += ")";}if(cur->right){str += "(";_tree2str(str, cur->right);str += ")";}}string tree2str(TreeNode* root) {string ret;//递归_tree2str(ret, root);return ret;}
};

2.2 二叉树的层序遍历I

  1. 题目信息：
    在这里插入图片描述
  2. 题目连接：
    二叉树的层序遍历I
  3. 思路：levelsize计数
class Solution
{
public:vector<vector<int>> levelOrder(TreeNode* root){//levelsize计数vector<vector<int>> ret;queue<TreeNode*> q;int levelsize = 1;q.push(root);//可能为空树if(root == nullptr){return ret;}while (!q.empty()){vector<int> count;while (levelsize--){//记录TreeNode* top = q.front();q.pop();count.push_back(top->val);//插入新结点if (top->left)q.push(top->left);if (top->right)q.push(top->right);}levelsize = q.size();ret.push_back(count);}return ret;}
};

2.3 二叉树层序遍历II

  1. 题目信息：
    在这里插入图片描述
  2. 题目连接：
    二叉树层序遍历II
  3. 思路：反转自上至下的层序遍历
class Solution 
{
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {//全部压栈，无法判断层//得出自上至下的序列，然后逆置vector<vector<int>> ret;if(root == nullptr){return ret;}queue<TreeNode*> q;int levelsize = 1;q.push(root);while(!q.empty()){vector<int> count;while(levelsize--){TreeNode* cur = q.front();q.pop();count.push_back(cur->val);if(cur->left)q.push(cur->left);if(cur->right)q.push(cur->right);}levelsize = q.size();ret.push_back(count);}reverse(ret.begin(), ret.end());return ret;}
};

2.4 二叉树最近公共祖先结点

  1. 题目信息：
    在这里插入图片描述
  2. 二叉树最近公共祖先结点
  3. 思路：
    <1> 方法1：p与q一定分别在祖先结点的左侧与右侧，祖先结点可能是自己
    <2> 方法2：栈记录遍历路径，路径上的所有祖先结点
//方法1：
class Solution 
{
public:bool SearchNode(TreeNode* cur, TreeNode* search){if(cur == nullptr){return false;}if(cur == search){return true;}return SearchNode(cur->left, search) || SearchNode(cur->right, search);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {bool qInleft = false;bool qInright = false;bool pInleft = false;bool pInright = false;TreeNode* cur = root;while(cur){//可能最近祖先结点是自己if(cur == p){pInleft = pInright = true;}else if(SearchNode(cur->left, p)){pInleft = true;pInright = false;}else{pInright = true;pInleft = false;}if(cur == q){qInleft = qInright = true;}else if(SearchNode(cur->left, q)){qInleft = true;qInright = false;}else{qInright = true;qInleft = false;}if((pInleft && qInright) || (pInright && qInleft))break;else if(pInleft && qInleft)cur = cur->left;elsecur = cur->right;}return cur;}
};//方法2：
class Solution 
{
public:bool PreOrder(TreeNode* cur, TreeNode* search, stack<TreeNode*>& count){if(cur == nullptr){return false;}count.push(cur);if(cur == search){return true;}if(!PreOrder(cur->left, search, count) && !PreOrder(cur->right, search, count)){count.pop();}else{return true;}assert(true);return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//栈记录遍历路径,所有祖先结点//到达指定结点的路径只有一条//深度优先遍历stack<TreeNode*> p_st;stack<TreeNode*> q_st;PreOrder(root, p, p_st);PreOrder(root, q, q_st);//路径上的相交结点while(p_st.size() != q_st.size()){if(p_st.size() > q_st.size())p_st.pop();elseq_st.pop();}while(p_st.top() != q_st.top()){p_st.pop();q_st.pop();}return p_st.top();}
};

2.5 二叉树搜索与双向链表

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    二叉搜索树与双向链表
  3. 思路：记录前置结点，中序遍历，注意调整指针链接的时机
class Solution 
{
public:void InOrder(TreeNode* cur, TreeNode*& pre){if(cur == nullptr){return;}InOrder(cur->left, pre);cur->left = pre;if(pre)pre->right = cur;pre = cur;InOrder(cur->right, pre);}TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree == nullptr){return nullptr;}TreeNode* pre = nullptr;InOrder(pRootOfTree, pre);while(pRootOfTree->left){pRootOfTree = pRootOfTree->left;}return pRootOfTree;}
};

2.6 从前序与中序遍历序列构造二叉树

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    从前序与中序遍历序列构造二叉树
  3. 思路：根据根分割出左右子树，区域分割，引用
class Solution 
{
public:TreeNode* buildNode(vector<int>& preorder, vector<int>& inorder, int& i, int left, int right){if(left > right){return nullptr;}//在中序中找到需构建结点int j = 0;while(inorder[j] != preorder[i]){j++;}//根左右//构建TreeNode* newnode = new TreeNode(preorder[i++]);//分割域，判断，构建左孩子newnode->left = buildNode(preorder, inorder, i, left, j - 1);//分割域，判断，构建右孩子newnode->right = buildNode(preorder, inorder, i, j + 1, right);return newnode;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i = 0;return buildNode(preorder, inorder, i, 0, inorder.size() - 1);}
};

2.7 从中序与后序遍历序列构造二叉树

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    从中序与后序遍历序列构造二叉树
  3. 思路：区域分割判断，引用，逆向遍历，根右左
class Solution 
{
public:TreeNode* buildNode(vector<int>& inorder, vector<int>& postorder, int& i, int left, int right){if(left > right){return nullptr;}int j = 0;while(inorder[j] != postorder[i]){j++;}TreeNode* newnode = new TreeNode(postorder[i--]);newnode->right = buildNode(inorder, postorder, i, j + 1, right);newnode->left = buildNode(inorder, postorder, i, left, j - 1);return newnode;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {//逆向遍历，根右左int i = postorder.size() - 1;return buildNode(inorder, postorder, i, 0, postorder.size() - 1);}
};

2.8 二叉树前序遍历（非递归）

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    二叉树前序遍历
  3. 思路：根左右，插入右子树时就将根删除，栈记录
class Solution 
{
public:vector<int> preorderTraversal(TreeNode* root) {//非递归，前序遍历，根左右vector<int> ret;TreeNode* cur = root;stack<TreeNode*> st;while(cur || !st.empty()){while(cur){st.push(cur);ret.push_back(cur->val);cur = cur->left;}TreeNode* top = st.top();st.pop();cur = top->right;}return ret;}
};

2.9 二叉树中序遍历（非递归）

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    二叉树中序遍历
  3. 思路：插入时机，删除时插入，左右根
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {//中序，左右根vector<int> ret;stack<TreeNode*> st;TreeNode* cur = root;//插入时机，删除时插入while(cur || !st.empty()){while(cur){st.push(cur);cur = cur->left;}TreeNode* top = st.top();st.pop();ret.push_back(top->val);cur = top->right;}return ret;}
};

!!!3.10 二叉树后序遍历（非递归）

  1. 题目信息：
    在这里插入图片描述
  2. 题目链接：
    二叉树后续遍历
  3. 思路：二次遍历时删除，删除时插入，何时删除
class Solution 
{
public:vector<int> postorderTraversal(TreeNode* root) {//左右根vector<int> ret;stack<TreeNode*> st;TreeNode* cur = root;TreeNode* pre = nullptr;while(cur || !st.empty()){//左while(cur){st.push(cur);cur = cur->left;}//根TreeNode* top = st.top();//cur = st.top();if(top->right == nullptr || pre == top->right)//if(cur->right == nullptr || pre == cur->right){st.pop();pre = top;//pre = cur;ret.push_back(top->val);//ret.push_back(cur->val);}else{//右，死循环cur = top->right;//cur调整错误//cur = cur->right;}}return ret;}
};

http://www.ppmy.cn/server/17429.html

相关文章

Pycharm破解流程

Pycharm破解流程

1.下载pycharm 网上很多&#xff0c;随便找一个&#xff0c;懒得找的话&#xff0c;或者去我传上去的资源pycharm部分直接取 2.下载文件 文件部分&#xff0c;我放在pycharm文件里面一起 打开下载好的激活包 3.执行脚本 先执行unisntall-all-users.vbs,直接双击打开&#xff0c…
阅读更多...
使用MySQL和SQL Server生成最近七周和最近七个月的日期数据

使用MySQL和SQL Server生成最近七周和最近七个月的日期数据

在数据库管理和数据处理中&#xff0c;生成特定时间范围内的数据是一项常见的任务。本文将介绍如何使用MySQL和SQL Server编写代码来生成最近七周和最近七个月的日期数据。 MySQL示例&#xff1a;生成最近七周和最近七个月的日期 在MySQL中&#xff0c;我们可以通过日期函数和…
阅读更多...
Spring Gateway 网关常见配置说明

Spring Gateway 网关常见配置说明

前言 Spring Gateway 是基于 Spring Framework 的 API 网关&#xff0c;它为微服务架构提供了路由、监控、弹性以及安全性等功能。Spring Gateway 使用非阻塞 API 和高性能的反应式编程模型来提供服务。 版本说明 本文的选项在多个最近的 Spring Cloud Gateway 版本中都是有…
阅读更多...
【EBS】财务系统总账模块（GL）会计期间状态总结

【EBS】财务系统总账模块（GL）会计期间状态总结

EBS财务系统中的会计期间主要有5种状态&#xff0c;其关系是&#xff1a;从未打开 -> 将来录入 -> 打开 <-> 关闭 -> 永久关闭&#xff0c;这个关系中&#xff0c;“打开”状态和“关闭”状态是可以双向的&#xff0c;而其他的都是单向的&#xff0c;比如对于“…
阅读更多...
TaskWeaver使用记录

TaskWeaver使用记录

TaskWeaver使用记录 1. 基本介绍2. 总体结构与流程3. 概念细节3.1 Project3.2 Session3.3 Memory3.4 Conversation3.5 Round3.6 Post3.7 Attachment3.8 Plugin3.9 Executor 4. 代码特点5. 使用过程5.1 api调用5.2 本地模型使用5.3 添加插件 6. 存在的问题与使用体验6.1 判别模型…
阅读更多...
【threejs教程7】threejs聚光灯、摄影机灯和汽车运动效果

【threejs教程7】threejs聚光灯、摄影机灯和汽车运动效果

【图片完整效果代码位于文章末】 在上一篇文章中我们实现了汽车模型的加载&#xff0c;这篇文章主要讲如何让汽车看起来像在运动。同时列出聚光灯和摄像机灯光的加载方法。 查看上一篇&#x1f449;【threejs教程6】threejs加载glb模型文件&#xff08;小米su7&#xff09;&…
阅读更多...
聚类分析字符串数组

聚类分析字符串数组

聚类分析字符串数组 对多个字符串进行聚类分析旨在根据它们之间的相似度将这些字符串划分成若干个类别&#xff0c;使得同一类别内的字符串彼此相似度高&#xff0c;而不同类别间的字符串相似度低 小结 数据要清洗。清洗的足够准确&#xff0c;可能不需要用聚类分析了数据要…
阅读更多...
跨境电商无货源模式汇总

跨境电商无货源模式汇总

跨境电商无货源模式是指在跨境电商业务中&#xff0c;不需要自己拥有实际的货物库存&#xff0c;而是通过与供应商或批发商建立合作关系&#xff0c;直接将订单信息传递给供应商&#xff0c;由供应商直接发货给最终客户的一种模式。本文将跨境电商无货源的几种模式与大家一同探…
阅读更多...
最新文章

Copyright @ 2022~2023