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

【二叉树】1-5,理论基础、前中后序遍历的递归法和迭代法、层序遍历

理论基础、前中后序遍历的递归法和迭代法、层序遍历

  • 1,二叉树的种类
    • 满二叉树
    • 完全二叉树
    • 二叉搜索树
    • 平衡二叉搜索树
  • 2,存储方式
    • 链式存储
    • 线式存储
  • 3,二叉树的遍历
    • 深度优先搜索
      • 前序遍历(递归法、迭代法)
      • 中序遍历(递归法、迭代法)
      • 后序遍历(递归法、迭代法)
    • 广度优先搜索
      • 层次遍历(迭代法、递归法)
  • 4,二叉树的定义

1,二叉树的种类

满二叉树

除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树。
请添加图片描述

完全二叉树

一个深度为k的有n个节点的二叉树,对树中的节点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。
请添加图片描述

二叉搜索树

二叉搜索树(Binary Search Tree),又名二叉排序树(Binary Sort Tree)。

二叉搜索树是具有有以下性质的二叉树:

若左子树不为空,则左子树上所有节点的值均小于或等于它的根节点的值。
若右子树不为空,则右子树上所有节点的值均大于或等于它的根节点的值。
左、右子树也分别为二叉搜索树。
请添加图片描述

平衡二叉搜索树

平衡二叉搜索树的任何结点的左子树和右子树高度最多相差1。,并且左右两个子树都是一棵平衡二叉树。
请添加图片描述

容器map、set、multimap、multiset的底层原理都是平衡二叉搜索树
所以map中key和set中的元素都是有序的

unordered map和unordered set的底层原理为哈希表

2,存储方式

分为链式存储和线式存储

链式存储

链式存储方式就用指针
请添加图片描述

线式存储

(用的少了解即可)

顺序存储的方式就是用数组。
请添加图片描述

线式存储时,有一点i,他的左孩子下标为2i+1,他的右孩子下标为2i+2

3,二叉树的遍历

分为深度优先搜索和广度优先搜索

深度优先搜索

分为前序遍历、中序遍历、后续遍历
请添加图片描述
写法可以分为递归法和迭代法

递归的底层原理是栈

确定递归函数的参数和返回值
确定终止条件
确定单层递归的逻辑

迭代法就是模拟递归的过程,因为递归的底层原理为栈,所以迭代法用栈展示

面试简单的可能需要写出简单的非递归代码

前序遍历(递归法、迭代法)

中左右
递归法:

class Solution {
public:void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;vec.push_back(cur->val);    // 中traversal(cur->left, vec);  // 左traversal(cur->right, vec); // 右}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};

迭代法:
因为模拟栈的过程,前序遍历是中左右,但是栈是先进后出的,所以入栈顺序为右左中

访问顺序和处理顺序相同(后续遍历也是如此,所以稍作改动就可以变为后续遍历)

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> result;if (root == NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node = st.top();                       // 中st.pop();result.push_back(node->val);if (node->right) st.push(node->right);           // 右(空节点不入栈)if (node->left) st.push(node->left);             // 左(空节点不入栈)}return result;}
};

中序遍历(递归法、迭代法)

左中右
递归法:

void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec);  // 左vec.push_back(cur->val);    // 中traversal(cur->right, vec); // 右
}

迭代法:
访问顺序和处理顺序不同,所以代码和前后续遍历不同

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;TreeNode* cur = root;while (cur != NULL || !st.empty()) {if (cur != NULL) { // 指针来访问节点,访问到最底层st.push(cur); // 将访问的节点放进栈cur = cur->left;                // 左} else {cur = st.top(); // 从栈里弹出的数据,就是要处理的数据(放进result数组里的数据)st.pop();result.push_back(cur->val);     // 中cur = cur->right;               // 右}}return result;}
};

后序遍历(递归法、迭代法)

左右中
递归法:

void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec);  // 左traversal(cur->right, vec); // 右vec.push_back(cur->val);    // 中
}

迭代法:
访问顺序和处理顺序相同

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> result;if (root == NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node = st.top();st.pop();result.push_back(node->val);if (node->left) st.push(node->left); // 相对于前序遍历,这更改一下入栈顺序 (空节点不入栈)if (node->right) st.push(node->right); // 空节点不入栈}reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了return result;}
};

广度优先搜索

层次遍历(迭代法、递归法)

借助一个队列,保存每一层的节点

队列记录当前层的元素个数,弹出时按队列里储存的个数弹出

迭代法:

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();vector<int> vec;// 这里一定要使用固定大小size,不要使用que.size(),因为que.size是不断变化的for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(vec);}return result;}
};

递归法:

class Solution {
public:void order(TreeNode* cur, vector<vector<int>>& result, int depth){if (cur == nullptr) return;if (result.size() == depth) result.push_back(vector<int>());result[depth].push_back(cur->val);order(cur->left, result, depth + 1);order(cur->right, result, depth + 1);}vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;int depth = 0;order(root, result, depth);return result;}
};

4,二叉树的定义

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

相关文章:

【二叉树】1-5,理论基础、前中后序遍历的递归法和迭代法、层序遍历

理论基础、前中后序遍历的递归法和迭代法、层序遍历 1&#xff0c;二叉树的种类满二叉树完全二叉树二叉搜索树平衡二叉搜索树 2&#xff0c;存储方式链式存储线式存储 3&#xff0c;二叉树的遍历深度优先搜索前序遍历&#xff08;递归法、迭代法&#xff09;中序遍历&#xff0…...

Mybatis-plus动态条件查询QueryWrapper的使用

Mybatis-plus动态条件查询QueryWrapper的使用 一&#xff1a;queryWrapper介绍 queryWrapper是mybatis plus中实现查询的对象封装操作类&#xff0c;可以封装sql对象&#xff0c;包括where条件&#xff0c;order by排序&#xff0c;select哪些字段等等&#xff0c;他的层级关…...

Redis安装配置远程连接

1. yum 安装 redis&#xff1a; 直接使用命令&#xff0c;将 redis 安装到 linux 服务器中&#xff1a; yum -y install redis 2. 启动 redis&#xff1a; 在 xshell 里&#xff0c;可以使用下面命令&#xff0c;以后台方式启动 redis&#xff1a; [rootVM-8-17-centos /]…...

pycharm中配置conda

安装好pycharm和conda后&#xff0c;打开pycharm&#xff1a;...

matlab解常微分方程常用数值解法1:前向欧拉法和改进的欧拉法

总结和记录一下matlab求解常微分方程常用的数值解法&#xff0c;本文先从欧拉法和改进的欧拉法讲起。 d x d t f ( x , t ) , x ( t 0 ) x 0 \frac{d x}{d t}f(x, t), \quad x\left(t_{0}\right)x_{0} dtdx​f(x,t),x(t0​)x0​ 1. 前向欧拉法 前向欧拉法使用了泰勒展开的第…...

SQL | 计算字段

7-创建计算字段 7.1-计算字段 存储在数据库中的数据一般不是我们所需要的字段格式&#xff0c; 需要公司名称&#xff0c;同时也需要公司地址&#xff0c;但是这两个数据存储在不同的列中。 省&#xff0c;市&#xff0c;县和邮政编码存储在不同的列中&#xff0c;但是当我们…...

leetcode做题笔记67

给你两个二进制字符串 a 和 b &#xff0c;以二进制字符串的形式返回它们的和。 思路一&#xff1a;模拟题意 void reserve(char* s) {int len strlen(s);for (int i 0; i < len / 2; i) {char t s[i];s[i] s[len - i - 1], s[len - i - 1] t;} }char* addBinary(cha…...

fastadmin 自定义搜索分类和时间范围

1.分类搜索&#xff0c;分类信息获取----php 2.对应html页面&#xff0c;页面底部加搜索提交代码&#xff08;这里需要注意&#xff1a;红框内容&#xff09; 图上代码----方便直接复制使用 <script id"countrySearch" type"text/html"><!--form…...

Oracle Data Redaction与Data Pump

如果表定义了Redaction Policy&#xff0c;导出时数据会脱敏吗&#xff1f;本文解答这个问题。 按照Oracle文档Advanced Security Guide第13章&#xff0c;13.6.5的Tutorial&#xff0c;假设表HR.jobs定义了Redaction Policy。 假设HR用户被授予了访问目录对象的权限&#xf…...

设计模式(6)原型模式

一、介绍 Java中自带的原型模式是clone()方法。该方法是Object的方法&#xff0c;native类型。他的作用就是将对象的在内存的那一块内存数据一字不差地再复制一个。我们写简单类的时候只需要实现Cloneable接口&#xff0c;然后调用Object::clone方法就可实现克隆功能。这样实现…...

pywinauto结合selenium实现文件上传

简介 PC端-Windows上的元素识别可用viewWizard工具 PC端-Windows上的元素操作可用pywinauto库 浏览器上网页的元素识别可用selenium 安装 pip installer pywinauto 使用须知 pywinauto官方文档 确定app的可访问技术 1、win32 API(backend=“win32”) 一般是MFC、VB6、VC…...

【Java多线程学习7】Java线程池技术

线程池技术 一、什么是线程池 线程池顾名思义是管理一组线程的池子。当有任务要处理时&#xff0c;直接从线程池中获取线程来处理&#xff0c;处理完之后线程不会立即销毁&#xff0c;而是等待下一个任务。 二、为什么要使用线程池? 线程池的作用&#xff1f; 1、降低资源…...

VMware虚拟机NAT模式Ubuntu无法上网解决方案

发现只要NAT模式&#xff0c;ping地址时就报网络不可达&#xff0c;且右上方网络图标消失&#xff0c;但是外部USB网络设备又只能在NAT模式下使用。。。 博主的解决方案如下&#xff1a; 按WinR键入services.msc&#xff0c; 找到VMware DHCP Service、VMware NAT Service和V…...

Linux中无法忘记mysql密码处理办法

找到/etc/my.cnf或者/etc/mysql/my.cnf文件 添加下面两行代码&#xff0c;取消密码验证 [mysqld] skip-grant-table使用命令登录&#xff1a;mysql -u root -p&#xff0c;回车&#xff0c;回车使用sql语句来修改密码 mysql>use mysql; mysql>update user set password…...

vue 使用 el-upload 上传文件(自动上传/手动上传)

vue 使用 el-upload 上传文件(自动上传/手动上传) 文章目录 1. 自动上传(选择完文件后,调用axios上传)2.手动上传 1. 自动上传(选择完文件后,调用axios上传) <el-uploadref"upload1"action:multiple"false"accept".xlsx,.csv,.xls":auto-upl…...

服务器遭受攻击之后的常见思路

哈喽大家好&#xff0c;我是咸鱼 不知道大家有没有看过这么一部电影&#xff1a; 这部电影讲述了男主是一个电脑极客&#xff0c;在计算机方面有着不可思议的天赋&#xff0c;男主所在的黑客组织凭借着超高的黑客技术去入侵各种国家机构的系统&#xff0c;并引起了德国秘密警察…...

C语言学习笔记 使用vscode外部console出现闪退-12

前言 在使用vscode的外部console时&#xff0c;会出现闪退现象&#xff0c;这是因为程序运行结束后&#xff0c;系统自动退出了终端&#xff08;终端机制决定的&#xff09;。我们可以在C程序结束后&#xff0c;使用system函数来暂停DOS终端系统&#xff0c;这样就可以完整地看…...

从Spring源码看Spring如何解决循环引用的问题

Spring如何解决循环引用的问题 关于循环引用&#xff0c;首先说一个结论&#xff1a; Spring能够解决的情况为&#xff1a;两个对象都是单实例、且通过set方法进行注入。 两个对象都是单实例&#xff0c;通过构造方法进行注入&#xff0c;Spring不能进行循环引用问题&#x…...

03 - 通过git log可以查看版本演变历史

通过git log可以查看版本演变历史 主要包括&#xff1a; commit 哈希id提交的Author信息提交的日期和时间commit info信息 git log本人常用&#xff0c;显示简洁&#xff1a; git log --oneline当log条数很多的时候&#xff0c;可以如下指定显示的数量&#xff1a; git log…...

【图论】单源最短路

算法提高课笔记。&#xff08;本篇还未更新完… 目录 单源最短路的建图方式例题热浪题意思路代码 信使题意思路代码 香甜的黄油题意思路代码 最小花费题意思路代码 最优乘车题意思路代码 昂贵的聘礼题意思路代码 单源最短路的建图方式 最短路问题可以分为以下两类&#xff1a…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

论文阅读:Matting by Generation

今天介绍一篇关于 matting 抠图的文章&#xff0c;抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法&#xff0c;已经有很多的工作和这个任务相关。这两年 diffusion 模型很火&#xff0c;大家又开始用 diffusion 模型做各种 CV 任务了&am…...

Java数组Arrays操作全攻略

Arrays类的概述 Java中的Arrays类位于java.util包中&#xff0c;提供了一系列静态方法用于操作数组&#xff08;如排序、搜索、填充、比较等&#xff09;。这些方法适用于基本类型数组和对象数组。 常用成员方法及代码示例 排序&#xff08;sort&#xff09; 对数组进行升序…...