代码随想录day13| 二叉树理论基础| 递归遍历|迭代遍历| 统一迭代 |层序遍历

devtools/2025/1/14 19:22:35/

请添加图片描述
二叉树是一种每个节点最多有两个子节点的树结构，它由若干节点构成，每个节点包含数据部分和两个子节点的引用（指向左子节点和右子节点）。常见的二叉树类型包括完全二叉树、满二叉树和平衡二叉树等。

1. 二叉树的种类

二叉树有两种主要的形式：满二叉树和完全二叉树。

满二叉树

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

在这里插入图片描述
这棵二叉树为满二叉树，也可以说深度为k，有2^k-1个节点的二叉树。

完全二叉树

什么是完全二叉树？

完全二叉树的定义如下：
在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。

请添加图片描述
优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

二叉搜索树

前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉排序树请添加图片描述

平衡二叉搜索树

平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。请添加图片描述
最后一棵 不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了1。

2. 二叉树的存储方式

二叉树可以链式存储，也可以顺序存储。

那么链式存储方式就用指针， 顺序存储的方式就是用数组。

顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。

链式存储如图：请添加图片描述

顺序存储如图：用数组来存储二叉树
请添加图片描述
用数组来存储二叉树如何遍历的呢？

如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。

所以大家要了解，用数组依然可以表示二叉树。

3. 二叉树的遍历方式

二叉树主要有两种遍历方式：

1.深度优先遍历：先往深走，遇到叶子节点再往回走。

2.广度优先遍历：一层一层的去遍历。

这两种遍历是图论中最基本的两种遍历方式

那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：

深度优先遍历

前序遍历（递归法，迭代法）
中序遍历（递归法，迭代法）
后序遍历（递归法，迭代法）

前中后序指的就是中间节点的位置。
即：
前序遍历：中左右
中序遍历：左中右
后序遍历：左右中

广度优先遍历

层次遍历（迭代法）

请添加图片描述
前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。

而广度优先遍历的实现一般使用队列实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。

二叉树的定义

二叉树有两种存储方式顺序存储，和链式存储，顺序存储就是用数组来存

链式存储的二叉树节点的定义方式：

// 定义二叉树节点类
class TreeNode {int val;          // 节点的值TreeNode left;    // 左子节点TreeNode right;   // 右子节点// 构造函数TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}

二叉树的应用使用较多的思想是递归，后续着重学习递归思想。

二叉树的递归遍历

Pre-order Traversal

二叉树的前序遍历（Pre-order Traversal）是指按照“根节点 -> 左子树 -> 右子树”的顺序遍历二叉树。在递归方法中，我们会首先访问当前节点的值，然后递归遍历左子树，再递归遍历右子树。
首先，我们定义一个二叉树节点的类 TreeNode。然后，在 preOrderTraversal 方法中使用递归来实现前序遍历。
二叉树节点类；

class TreeNode {int val;          // 节点的值TreeNode left;    // 左子节点TreeNode right;   // 右子节点// 构造函数public TreeNode(int val) {this.val = val;this.left = null;this.right = null;}
}

前序遍历的递归实现；

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>();  // 创建一个列表来存储遍历结果preorder(root, result);  // 调用递归函数进行前序遍历return result;  // 返回最终的遍历结果}public void preorder(TreeNode root, List<Integer> result) {if (root == null) {  // 基础情况：如果当前节点为空，直接返回return;}result.add(root.val);  // 访问根节点，添加其值到结果列表中preorder(root.left, result);  // 递归遍历左子树preorder(root.right, result);  // 递归遍历右子树}
}

在这里插入图片描述

二叉树的迭代遍历

二叉树的迭代遍历，通过使用栈来模拟递归过程，避免了函数调用的堆栈开销。
迭代遍历主要有前序遍历、中序遍历和后续遍历等。

前序遍历

前序遍历的顺序是：根节点–>左子树—>右子树。
在递归版本中，是通过先访问根节点，再递归访问左右子树来实现的，迭代版本则可以通过栈来模拟这一过程。

算法步骤：

  • 使用栈保存遍历节点。
  • 每次弹出栈顶元素，访问该节点。
  • 如果右子节点存在，先将右子节点压入栈中，再将左子节点压入栈中（因为栈是后进先出，所以先压入左子节点确保它在右子节点之前被访问）。
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();  // 用来存储遍历结果if (root == null) {return result;}Stack<TreeNode> stack = new Stack<>();  // 使用栈来模拟递归stack.push(root);  // 将根节点压入栈while (!stack.isEmpty()) {TreeNode node = stack.pop();  // 弹出栈顶元素result.add(node.val);  // 将当前节点的值加入到结果列表// 因为栈是后进先出（LIFO），所以先压右子节点，再压左子节点if (node.right != null) {stack.push(node.right);  // 右子节点先入栈}if (node.left != null) {stack.push(node.left);  // 左子节点后入栈}}return result;  // 返回遍历结果}
}

解释：

  • 该方法通过栈实现前序遍历。
  • 初始时，将根节点压入栈中。
  • 在循环中，每次从栈中弹出节点并访问它。
  • 如果该节点有右子节点，右子节点先压入栈；左子节点压入栈的顺序在右子节点之后，以确保左子节点在右子节点之前被访问。

注意：如果不判断 node != null，在访问一个 null 节点时会抛出空指针异常。
右子节点先入栈，左子节点后入栈，因为栈是后进先出（LIFO）的结构，这样可以保证左子节点在右子节点之前被访问。

中序遍历（迭代）

中序遍历的顺序是：左子树 → 根节点 → 右子树。在递归版本中，访问左子树是通过递归方式完成的。对于迭代版本，使用栈来模拟递归过程中的“回溯”。

算法步骤：

从根节点开始，一直遍历左子树并将节点压入栈中。
当没有左子节点时，从栈中弹出一个节点，访问它。
然后，遍历该节点的右子树，重复该过程。
代码实现：

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;// 用来存储遍历结果stack<TreeNode*> st;  // 栈用来模拟递归的过程TreeNode* cur = root; // 当前节点从根节点开始while (cur != NULL || !st.empty()) { // 循环直到栈为空且当前节点为NULLif (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;}
};

解释：

这个方法使用栈模拟递归的回溯过程。
先将当前节点以及其所有左子节点压入栈中。
当没有左子节点时，从栈中弹出节点并访问它，然后将该节点的右子节点作为新的当前节点。

二叉树的层序遍历

给你 一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有的节点）。
请添加图片描述
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。
需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

public void checkFun02(TreeNode node) {if (node == null) return;  // 如果树为空，直接返回// 队列，用来存储树的节点Queue<TreeNode> que = new LinkedList<TreeNode>();// 将根节点加入队列que.offer(node);// 开始逐层遍历while (!que.isEmpty()) {// 用于存储当前层的节点值List<Integer> itemList = new ArrayList<Integer>();// 当前层的节点数（即队列中的元素个数）int len = que.size();// 处理当前层的所有节点while (len > 0) {// 弹出队列中的节点TreeNode tmpNode = que.poll();// 将该节点的值加入当前层的结果列表itemList.add(tmpNode.val);// 如果该节点有左子节点，将其加入队列if (tmpNode.left != null) que.offer(tmpNode.left);// 如果该节点有右子节点，将其加入队列if (tmpNode.right != null) que.offer(tmpNode.right);// 处理完当前节点，当前层节点数减一len--;}// 将当前层的结果加入最终结果列表resList.add(itemList);}
}
  1. 判断树是否为空：
if (node == null) return;

如果树的根节点为 null，意味着树为空，因此直接返回，避免执行后续的遍历逻辑。

  1. 初始化队列：
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(node);
  • 使用 LinkedList 实现 Queue 接口，que 是一个队列，用于存储待处理的节点。
  • 将根节点 node 放入队列中，开始层序遍历。
  1. 逐层遍历树的节点：
while (!que.isEmpty()) {
  • 当队列不为空时，继续处理队列中的节点。
  • 在每次处理一个新的层级时，队列中会存储该层的所有节点，处理完这一层后会处理下一层。
  1. 处理当前层的节点：
List<Integer> itemList = new ArrayList<Integer>();
int len = que.size();
  • itemList 用来存储当前层的所有节点的值。
  • len 是当前层的节点数，即队列中的节点数（当前层有多少个节点）。在遍历时，队列会依次出队节点，处理完该层后，itemList 会保存当前层的所有节点值。
  1. 遍历当前层的所有节点：
while (len > 0) {TreeNode tmpNode = que.poll();itemList.add(tmpNode.val);if (tmpNode.left != null) que.offer(tmpNode.left);if (tmpNode.right != null) que.offer(tmpNode.right);len--;
}
  • while (len > 0)：在当前层中，依次弹出每个节点。
  • TreeNode tmpNode = que.poll();：弹出队列中的节点。poll() 方法从队列中取出队头节点并删除该节点。
  • itemList.add(tmpNode.val);：将当前节点的值 tmpNode.val 添加到 itemList 中，表示该节点属于当前层。
  • 处理子节点：
    如果当前节点 tmpNode 有左子节点，将其加入队列：if (tmpNode.left != null) que.offer(tmpNode.left);
    如果当前节点 tmpNode 有右子节点，将其加入队列：if (tmpNode.right != null) que.offer(tmpNode.right);
  • 每处理一个节点，len–，直到当前层的所有节点都被处理完。
  1. 将当前层的节点值添加到最终结果中：
resList.add(itemList);
  • 当前层的所有节点都被处理完后，将 itemList（即当前层的所有节点值）添加到 resList 中。
  • resList 是一个存储每一层节点值的列表，最终会包含所有层的节点值，按层次排列。

http://www.ppmy.cn/devtools/150488.html

相关文章

将Docker运行中的容器保存为镜像并导出导入

将Docker运行中的容器保存为镜像并导出导入

在 Docker 中&#xff0c;将运行中的容器保存为镜像并导出是一个常见的操作&#xff0c;特别是在你需要迁移或备份容器配置和数据时。以下是具体步骤&#xff1a; 1. 将运行中的容器保存为镜像 首先&#xff0c;你需要通过docker commit命令将运行中的容器保存为一个新的镜像。…
阅读更多...
工程水印相机结合图纸，真实现场时间地点，如何使用水印相机，超简单方法只教一次！

工程水印相机结合图纸，真实现场时间地点，如何使用水印相机，超简单方法只教一次！

在工程管理领域&#xff0c;精准记录现场信息至关重要。水印相机拍照功能&#xff0c;为工程人员提供了强大的现场信息记录工具&#xff0c;助力工程管理和统计工程量&#xff0c;更可以将图片分享到电脑、分享给同事&#xff0c;协同工作。 一、打开图纸 打开手机版CAD快速看图…
阅读更多...
全网首发：编译libssh，产生类似undefined reference to `EVP_aes_256_ctr@OPENSSL_1_1_0‘的大量错误

全网首发：编译libssh，产生类似undefined reference to `EVP_aes_256_ctr@OPENSSL_1_1_0‘的大量错误

具体错误 前面和后面的&#xff1a; /opt/linux/x86-arm/aarch64-mix210-linux/host_bin/../lib/gcc/aarch64-linux-gnu/7.3.0/../../../../aarch64-linux-gnu/bin/ld: warning: libcrypto.so.1.1, needed by ../lib/libssh.so.4.10.1, not found (try using -rpath or -rpat…
阅读更多...
4. scala高阶之隐式转换与泛型

4. scala高阶之隐式转换与泛型

背景 上一节&#xff0c;我介绍了scala中的面向对象相关概念&#xff0c;还有一个特色功能&#xff1a;模式匹配。本文&#xff0c;我会介绍另外一个特别强大的功能隐式转换&#xff0c;并在最后介绍scala中泛型的使用 1. 隐式转换 Scala提供的隐式转换和隐式参数功能&#…
阅读更多...
Python 替换excel 单元格内容

Python 替换excel 单元格内容

要在Python中替换Excel单元格的内容&#xff0c;你可以使用openpyxl库。openpyxl是一个用于读写Excel 2010 xlsx/xlsm/xltx/xltm文件的库。 安装openpyxl 首先&#xff0c;你需要安装openpyxl库。如果还没有安装&#xff0c;可以使用pip进行安装&#xff1a; pip install ope…
阅读更多...
css 布局及动画应用（flex+transform+transition+animation）

css 布局及动画应用（flex+transform+transition+animation）

文章目录 css 布局及动画应用animationtransform&#xff0c;transition&#xff0c;animation 综合应用实例代码实例解释 css 布局及动画应用 Display用法 作用&#xff1a;用于控制元素的显示类型&#xff0c;如块级元素、内联元素、无显示等。常见属性值及示例&#xff1a;…
阅读更多...
【Docker项目实战】使用Docker部署Enclosed笔记应用程序

【Docker项目实战】使用Docker部署Enclosed笔记应用程序

【Docker项目实战】使用Docker部署Enclosed笔记应用程序 一、Enclosed介绍1.1 Enclosed简介1.2 主要特点1.3 使用场景二、本次实践规划2.1 本地环境规划2.2 本次实践介绍三、本地环境检查3.1 检查Docker服务状态3.2 检查Docker版本3.3 检查docker compose 版本四、下载Enclosed…
阅读更多...
《使用 YOLOV8 和 KerasCV 进行高效目标检测》

《使用 YOLOV8 和 KerasCV 进行高效目标检测》

《使用 YOLOV8 和 KerasCV 进行高效目标检测》 作者&#xff1a;Gitesh Chawda创建日期&#xff1a;2023/06/26最后修改时间&#xff1a;2023/06/26描述&#xff1a;使用 KerasCV 训练自定义 YOLOV8 对象检测模型。 &#xff08;i&#xff09; 此示例使用 Keras 2 在 Colab 中…
阅读更多...
最新文章

Copyright @ 2022~2023