代码随想录算法训练营第13天 |二叉树的学习

devtools/2024/9/25 10:31:22/

目录

二叉树

理论基础

二叉树的分类

1. 满二叉树 (Full Binary Tree)

2. 完全二叉树 (Complete Binary Tree)

3. 平衡二叉树 (Balanced Binary Tree)

5. 二叉搜索树 (Binary Search Tree, BST)

二叉树的存储

1. 链式存储 (Linked Representation)

2. 顺序存储 (Sequential Representation)

遍历方式

深度优先搜索

DFS 的工作原理

基本步骤：

广度优先搜索

BFS 的工作原理

基本步骤：

二叉树的遍历

递归遍历

前序遍历

中序遍历

后序遍历

非递归遍历

前序遍历

中序遍历

后续遍历

层序遍历

二叉树

理论基础

二叉树的分类

1. 满二叉树 (Full Binary Tree)
  • 定义：满二叉树是一种二叉树，除了叶子节点外，每个节点都有两个子节点，深度为h的完美二叉树有2^h - 1个节点
  • 特点：所有非叶子节点都有两个子节点，且所有叶子节点都在同一层。
2. 完全二叉树 (Complete Binary Tree)
  • 定义：完全二叉树是一种二叉树，所有层都被完全填满，除了可能是最后一层，且最后一层的所有节点尽可能靠左。
  • 特点：没有缺失的节点，除非是在最后一层的最右边。
3. 平衡二叉树 (Balanced Binary Tree)
  • 定义：平衡二叉树是一种二叉树，其中每个节点的左子树和右子树的高度差不超过1，空树。
  • 特点：平衡二叉树保证了二叉树的高度尽可能低，从而优化了查找、插入和删除操作的效率。
5. 二叉搜索树 (Binary Search Tree, BST)
  • 定义：二叉搜索树是一种有序二叉树，其中每个节点的值大于其左子树中所有节点的值，小于其右子树中所有节点的值。
  • 特点：在理想情况下（即树是平衡的），查找、插入、删除操作的时间复杂度为O(log n)。

二叉树的存储

二叉树的存储方式有多种，常见的主要有以下两种方法：链式存储和顺序存储。每种方法都有其适用场景和优缺点。

1. 链式存储 (Linked Representation)

链式存储是二叉树最常用的存储方式，特别适合用于动态变化的树结构。

特点：

  • 每个节点用一个对象或结构体来表示，包含节点的值、左子节点指针、右子节点指针，和（有时）指向父节点的指针。
  • 链式存储易于动态地添加或删除节点，不需要预先分配大量的连续内存。

节点结构

在典型的链式存储中，每个节点包含三个主要部分：

  • 值/数据域：存储节点的数据。
  • 左指针域：指向左子节点。
  • 右指针域：指向右子节点。
class TreeNode {int value;TreeNode left;TreeNode right;TreeNode(int value) {this.value = value;this.left = null;this.right = null;}
}
2. 顺序存储 (Sequential Representation)

顺序存储是将二叉树节点按某种规则顺序存储在数组中的方式，通常适用于完全二叉树或满二叉树。

特点

  • 二叉树的节点按照层次从上到下、从左到右存储在数组中。
  • 数组的第一个位置（通常从索引0或1开始）存储根节点，其他节点按照其在二叉树中的位置依次存储。

节点位置关系

假设父节点在数组中的索引为i，则：

  • 左子节点的索引：2*i + 1 （或 2*i，如果数组从1开始）
  • 右子节点的索引：2*i + 2 （或 2*i + 1，如果数组从1开始）
  • 父节点的索引：(i-1)/2 （对于索引从0开始的情况）

遍历方式

与图论中的深度优先搜索和广度优先搜索是一致的。

深度优先搜索

深度优先搜索（Depth-First Search，简称DFS）是一种遍历或搜索树或图数据结构的算法。它优先深入到树或图的一个分支的尽可能深的节点，然后再回溯并探索其他分支。这种策略使得DFS能够深入到数据结构的最深处，然后逐层返回，直到遍历所有节点。

前序遍历：中左右

中序遍历：左中右

后序遍历：左右中

DFS 的工作原理

DFS 使用栈结构来实现遍历的过程。栈可以通过显式使用栈数据结构来实现，也可以通过递归调用来隐式实现。

基本步骤：
  1. 访问当前节点。
  2. 标记该节点为已访问，以避免重复访问。
  3. 递归地访问该节点的未被访问的相邻节点，对于树结构来说，这意味着先访问左子树，然后访问右子树。
  4. 当节点的所有相邻节点都已被访问或没有未被访问的相邻节点时，回溯到前一个节点，然后继续访问其他未被访问的节点。
  5. 重复以上步骤，直到所有节点都被访问。

递归实现：

class TreeNode {int value;TreeNode left;TreeNode right;TreeNode(int value) {this.value = value;this.left = null;this.right = null;}
}public class DFS {public void depthFirstSearch(TreeNode node) {if (node == null) {return;}// 访问当前节点System.out.print(node.value + " ");// 递归地访问左子节点depthFirstSearch(node.left);// 递归地访问右子节点depthFirstSearch(node.right);}public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);DFS dfs = new DFS();dfs.depthFirstSearch(root);  // 输出: 1 2 4 5 3}
}

栈实现：

class TreeNode {int value;TreeNode left;TreeNode right;TreeNode(int value) {this.value = value;this.left = null;this.right = null;}
}public class DFS {public void depthFirstSearch(TreeNode node) {if (node == null) {return;}// 访问当前节点System.out.print(node.value + " ");// 递归地访问左子节点depthFirstSearch(node.left);// 递归地访问右子节点depthFirstSearch(node.right);}public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);DFS dfs = new DFS();dfs.depthFirstSearch(root);  // 输出: 1 2 4 5 3}
}

广度优先搜索

广度优先搜索（Breadth-First Search，简称 BFS）是一种遍历或搜索树或图数据结构的算法。与深度优先搜索（DFS）不同，BFS 从起始节点开始，首先访问其所有邻居节点，然后再逐层向下深入到下一级的节点。这种逐层访问的方式确保了在无权重图中，从起始节点到任意其他节点的最短路径可以通过 BFS 得到。

BFS 的工作原理

BFS 使用队列（Queue）数据结构来实现逐层遍历的过程。队列遵循先进先出（FIFO）的原则，确保先进入队列的节点先被处理。

基本步骤：
  1. 将起始节点加入队列，并标记为已访问。
  2. 从队列中取出一个节点，访问该节点，并将其所有未被访问的相邻节点加入队列。
  3. 标记这些相邻节点为已访问，以防止重复访问。
  4. 重复步骤 2 和 3，直到队列为空，表示所有节点都已被访问。

使用队列实现：

import java.util.LinkedList;
import java.util.Queue;class TreeNode {int value;TreeNode left;TreeNode right;TreeNode(int value) {this.value = value;this.left = null;this.right = null;}
}public class BFS {public void breadthFirstSearch(TreeNode root) {if (root == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();System.out.print(node.value + " ");// 将左子节点加入队列if (node.left != null) {queue.offer(node.left);}// 将右子节点加入队列if (node.right != null) {queue.offer(node.right);}}}public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);BFS bfs = new BFS();bfs.breadthFirstSearch(root);  // 输出: 1 2 3 4 5}
}

二叉树的遍历

递归遍历

1.确定递归函数的参数和返回值

2.确定终止条件

3.确定单层递归的逻辑

前序遍历
 public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();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);}
中序遍历
public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();inorder(root, result);return result;}public void inorder(TreeNode root, List<Integer> result) {if (root == null) {return;}inorder(root.left, result);result.add(root.val);inorder(root.right, result);}
后序遍历
 public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();postorder(root, result);return result;}public void postorder(TreeNode root, List<Integer> result) {if (root == null) {return;}postorder(root.left, result);postorder(root.right, result);result.add(root.val);}

非递归遍历

null在谁前就先访问谁，null后如果还要push就先访问push进去的，再访问null

前序遍历

前序遍历，访问的元素和要处理的元素一致

每次循环操纵栈中第一个节点

 public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> st = new Stack<>();//放入第一个元素，放进栈中if (root != null) {st.push(root);}while (!st.empty()) {//储存栈中的第一个节点TreeNode node = st.peek();if (node != null) {//因为在后面还要压入一次中节点st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）st.push(node);                          // 添加中节点st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。} else { // 只有遇到空节点的时候，才将下一个节点放进结果集st.pop();           // 将空节点弹出node = st.peek();    // 重新取出栈中元素st.pop();result.add(node.val); // 加入到结果集}}return result;}

中序遍历

先看节点的左孩子为空则弹出中间，右孩子也为空则继续弹出前一个节点

左孩子不为空，则继续用栈收集

左孩子为空，弹出中间，右孩子不为空，收集右孩子，再看右孩子的左孩子是否为空

 public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> st = new Stack<>();if (root != null) st.push(root);while (!st.empty()) {TreeNode node = st.peek();if (node != null) {st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）st.push(node);                          // 添加中节点st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）} else { // 只有遇到空节点的时候，才将下一个节点放进结果集st.pop();           // 将空节点弹出node = st.peek();    // 重新取出栈中元素st.pop();result.add(node.val); // 加入到结果集}}return result;}
后续遍历

将左右交换，然后再将数组颠倒

  public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> st = new Stack<>();if (root != null) st.push(root);while (!st.empty()) {TreeNode node = st.peek();if (node != null) {st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中st.push(node);                          // 添加中节点st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）         } else { // 只有遇到空节点的时候，才将下一个节点放进结果集st.pop();           // 将空节点弹出node = st.peek();    // 重新取出栈中元素st.pop();result.add(node.val); // 加入到结果集}}return result;}

层序遍历

每次循环，先得到一个队列的大小为size，然后得到左右孩子，每次弹出一个，直到弹出size个，

下次循环再得到size

// 102.二叉树的层序遍历
class Solution {public List<List<Integer>> resList = new ArrayList<List<Integer>>();public List<List<Integer>> levelOrder(TreeNode root) {//checkFun01(root,0);checkFun02(root);return resList;}//BFS--递归方式public void checkFun01(TreeNode node, Integer deep) {if (node == null) return;deep++;if (resList.size() < deep) {//当层级增加时，list的Item也增加，利用list的索引值进行层级界定List<Integer> item = new ArrayList<Integer>();resList.add(item);}resList.get(deep - 1).add(node.val);checkFun01(node.left, deep);checkFun01(node.right, deep);}//BFS--迭代方式--借助队列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);}}
}


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

相关文章

Qt/QML学习-MenuBarToolBar

Qt/QML学习-MenuBarToolBar

QML学习 MenuBar&ToolBar例程视频讲解代码 main.qml import QtQuick 2.15 import QtQuick.Window 2.15 import QtQuick.Controls 2.15Window {width: 640height: 480visible: truetitle: qsTr("MenuBar&ToolBar")// 菜单栏MenuBar {id: menuBarcontentWid…
阅读更多...
深入理解DPO（Direct Preference Optimization）算法

深入理解DPO（Direct Preference Optimization）算法

目录 1. 什么是DPO&#xff1f;2. Bradley-Terry模型2.1 奖励模型的训练 3. 从PPO到DPO4. DPO的简单实现5. 梯度分析Ref 1. 什么是DPO&#xff1f; 直接偏好优化&#xff08;Direct Preference Optimization, DPO&#xff09;是一种不需要强化学习的对齐算法。由于去除了复杂的…
阅读更多...
SAP ERP与长城汽车EDI业务集成案例（SAP CPI平台）

SAP ERP与长城汽车EDI业务集成案例（SAP CPI平台）

一、项目背景 某智能座舱公司是国内领先的智能座舱领域科技公司&#xff0c;致力于成为智能网联行业变革的领导者和推动者&#xff0c;聚焦整车域控制器产品、智能网联软件产品和运营服务产品&#xff1b; 已建成首条先进的数智化域控制器生产线&#xff0c;为客户提供最优…
阅读更多...
【ORACLE】如何使用EXPLAIN PLAN来分析 listagg() 函数的性能瓶颈？

【ORACLE】如何使用EXPLAIN PLAN来分析 listagg() 函数的性能瓶颈？

在Oracle数据库中&#xff0c;EXPLAIN PLAN 语句用于显示SQL语句的执行计划&#xff0c;这对于分析和优化查询性能至关重要。要使用 EXPLAIN PLAN 来分析包含 LISTAGG 函数的查询的性能&#xff0c;你可以按照以下步骤操作&#xff1a; 步骤 1: 生成执行计划 首先&#xff0c…
阅读更多...
Midjourney Describe API 的对接和使用

Midjourney Describe API 的对接和使用

Midjourney Describe API 的对接和使用 Midjourney Describe API 的主要功能是通过上传图片&#xff0c;获取对图片的描述。使用该 API&#xff0c;只需要传递图片文件地址&#xff0c;API 会返回图片的详细描述。无需繁琐的参数设置&#xff0c;即可获得高质量的图片描述。 …
阅读更多...
Mysql语句性能优化

Mysql语句性能优化

SQL查询过程 查询缓存&#xff1a; 执行查询语句的时候&#xff0c;会先查询缓存&#xff08;MySQL 8.0 版本后移除&#xff0c;因为这个功能不太实用&#xff09;。分析器&#xff1a; 没有命中缓存的话&#xff0c;SQL 语句就会经过分析器&#xff0c;分析器说白了就是要先看…
阅读更多...
dubbo：dubbo服务负载均衡、集群容错、服务降级、服务直连配置详解（五）

dubbo：dubbo服务负载均衡、集群容错、服务降级、服务直连配置详解（五）

文章目录 0. 引言1. dubbo负载均衡1.1 负载均衡算法1.2. dubbo负载均衡使用1.3 自定义负载均衡策略 2. dubbo服务容错2.1 8种服务容错策略2.2 自定义容错策略 3. dubbo服务降级&#xff08;mock&#xff09;4. dubbo服务直连5. 总结 0. 引言 之前我们讲解了dubbo的基本使用&am…
阅读更多...
[数据集][目标检测]电力场景输电线杆塔塔架金属锈蚀腐蚀生锈检测数据集VOC+YOLO格式1344张1类别

[数据集][目标检测]电力场景输电线杆塔塔架金属锈蚀腐蚀生锈检测数据集VOC+YOLO格式1344张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;1344 标注数量(xml文件个数)&#xff1a;1344 标注数量(txt文件个数)&#xff1a;1344 标注…
阅读更多...
最新文章

Copyright @ 2022~2023