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

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

article 2025/1/13 21:01:17

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

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()) { // 循环直到栈为空且当前节点为NULL
            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;
    }
};

解释：

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

二叉树的层序遍历

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

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.kler.cn/a/501252.html

相关文章：

  • 网络原理（三）—— 传输层 之 UDP 和 TCP协议
  • Docker 安装开源的IT资产管理系统Snipe-IT
  • Spring Boot 支持哪些日志框架
  • 初步了解JSON的基础概念
  • MPLS原理及配置
  • Redis持久化双雄
  • 第25章 汇编语言--- 信号量与互斥锁
  • 什么是数据分析？
  • asp.net core webapi 并发请求时 怎么保证实时获取的用户信息是此次请求的？
  • 【网络安全 | 漏洞挖掘】通过监控调试模式实现价值$15k的RCE
  • 基于单片机的粮仓环境监测系统设计
  • 第32天：Web开发-PHP应用文件操作安全上传下载任意读取删除目录遍历文件包含
  • SpringCloud：gateway分发服务报302，Network Error
  • Rabbit Rocket kafka 怎么实现消息有序消费和延迟消费的
  • css 布局及动画应用（flex+transform+transition+animation）
  • 【Rust】切片类型
  • 【Pandas】pandas Series rtruediv
  • CentOS 和 Ubantu你该用哪个
  • 微信小程序mp3音频播放组件，仅需传入url即可
  • C++:string
  • 鸿蒙UI（ArkUI-方舟UI框架）
  • Python爬虫-爬取汽车之家全部汽车品牌的brandid（品牌ID）
  • 在 C# 中使用预处理器指令
  • VB.NET 正则表达式完全指南
  • 机器学习之避免过拟合的验证方法
  • HTML - 其他标签