DAY14之二叉树理论基础及递归遍历和迭代遍历

理论基础

满二叉树

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

如图所示:

这棵二叉树为满二叉树,也可以说深度为k,有2^k-1个节点的二叉树。

#完全二叉树

什么是完全二叉树?

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

大家要自己看完全二叉树的定义,很多同学对完全二叉树其实不是真正的懂了。

我来举一个典型的例子如题:

相信不少同学最后一个二叉树是不是完全二叉树都中招了。

之前我们刚刚讲过优先级队列其实是一个堆,堆就是一棵完全二叉树,同时保证父子节点的顺序关系。

#二叉搜索树

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

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  • 它的左、右子树也分别为二叉排序树

下面这两棵树都是搜索树

#平衡二叉搜索树

平衡二叉搜索树:又被称为AVL(Adelson-Velsky and Landis)树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

如图:

最后一棵 不是平衡二叉树,因为它的左右两个子树的高度差的绝对值超过了1。

C++中map、set、multimap,multiset的底层实现都是平衡二叉搜索树,所以map、set的增删操作时间时间复杂度是logn,注意我这里没有说unordered_map、unordered_set,unordered_map、unordered_set底层实现是哈希表。

所以大家使用自己熟悉的编程语言写算法,一定要知道常用的容器底层都是如何实现的,最基本的就是map、set等等,否则自己写的代码,自己对其性能分析都分析不清楚!

二叉树的存储方式

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

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

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

链式存储如图:

链式存储是大家很熟悉的一种方式,那么我们来看看如何顺序存储呢?

其实就是用数组来存储二叉树,顺序存储的方式如图:

用数组来存储二叉树如何遍历的呢?

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

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

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

#二叉树的遍历方式

关于二叉树的遍历方式,要知道二叉树遍历的基本方式都有哪些。

一些同学用做了很多二叉树的题目了,可能知道前中后序遍历,可能知道层序遍历,但是却没有框架。

我这里把二叉树的几种遍历方式列出来,大家就可以一一串起来了。

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

  1. 深度优先遍历:先往深走,遇到叶子节点再往回走。
  2. 广度优先遍历:一层一层的去遍历。

这两种遍历是图论中最基本的两种遍历方式,后面在介绍图论的时候 还会介绍到。

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

  • 深度优先遍历
    • 前序遍历(递归法,迭代法)
    • 中序遍历(递归法,迭代法)
    • 后序遍历(递归法,迭代法)
  • 广度优先遍历
    • 层次遍历(迭代法)

在深度优先遍历中:有三个顺序,前中后序遍历, 有同学总分不清这三个顺序,经常搞混,我这里教大家一个技巧。

这里前中后,其实指的就是中间节点的遍历顺序,只要大家记住 前中后序指的就是中间节点的位置就可以了。

看如下中间节点的顺序,就可以发现,中间节点的顺序就是所谓的遍历方式

  • 前序遍历:中左右
  • 中序遍历:左中右
  • 后序遍历:左右中

大家可以对着如下图,看看自己理解的前后中序有没有问题。

最后再说一说二叉树中深度优先和广度优先遍历实现方式,我们做二叉树相关题目,经常会使用递归的方式来实现深度优先遍历,也就是实现前中后序遍历,使用递归是比较方便的。

之前我们讲栈与队列的时候,就说过栈其实就是递归的一种实现结构,也就说前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。

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

这里其实我们又了解了栈与队列的一个应用场景了。

具体的实现我们后面都会讲的,这里大家先要清楚这些理论基础。

二叉树的定义

刚刚我们说过了二叉树有两种存储方式顺序存储,和链式存储,顺序存储就是用数组来存,这个定义没啥可说的,我们来看看链式存储的二叉树节点的定义方式。

C++代码如下:

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

大家会发现二叉树的定义 和链表是差不多的,相对于链表 ,二叉树的节点里多了一个指针, 有两个指针,指向左右孩子。

这里要提醒大家要注意二叉树节点定义的书写方式。

在现场面试的时候 面试官可能要求手写代码,所以数据结构的定义以及简单逻辑的代码一定要锻炼白纸写出来。

因为我们在刷leetcode的时候,节点的定义默认都定义好了,真到面试的时候,需要自己写节点定义的时候,有时候会一脸懵逼!

#总结

二叉树是一种基础数据结构,在算法面试中都是常客,也是众多数据结构的基石。

本篇我们介绍了二叉树的种类、存储方式、遍历方式以及定义,比较全面的介绍了二叉树各个方面的重点,帮助大家扫一遍

二叉树的递归遍历

主要是对递归不成体系,没有方法论,每次写递归算法 ,都是靠玄学来写代码,代码能不能编过都靠运气。

本篇将介绍前后中序的递归写法,一些同学可能会感觉很简单,其实不然,我们要通过简单题目把方法论确定下来,有了方法论,后面才能应付复杂的递归。

这里帮助大家确定下来递归算法的三个要素。每次写递归,都按照这三要素来写,可以保证大家写出正确的递归算法!

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

 确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数, 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

  1. 确定终止条件:

 写完了递归算法, 运行的时候,经常会遇到栈溢出的错误,就是没写终止条件或者终止条件写的不对,操作系统也是用一个栈的结构来保存每一层递归的信息,如果递归没有终止,操作系统的内存栈必然就会溢出。

  1. 确定单层递归的逻辑:

 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

好了,我们确认了递归的三要素,接下来就来练练手:

以下以前序遍历为例:

  1. 确定递归函数的参数和返回值:因为要打印出前序遍历节点的数值,所以参数里需要传入vector来放节点的数值,除了这一点就不需要再处理什么数据了也不需要有返回值,所以递归函数返回类型就是void,代码如下:

void traversal(TreeNode* cur, vector<int>& vec)

  1. 确定终止条件:在递归的过程中,如何算是递归结束了呢,当然是当前遍历的节点是空了,那么本层递归就要结束了,所以如果当前遍历的这个节点是空,就直接return,代码如下:

if (cur == NULL) return;

  1. 确定单层递归的逻辑:前序遍历是中左右的循序,所以在单层递归的逻辑,是要先取中节点的数值,代码如下:

vec.push_back(cur->val); // 中 traversal(cur->left, vec); // 左 traversal(cur->right, vec); // 右

单层递归的逻辑就是按照中左右的顺序来处理的,这样二叉树的前序遍历,基本就写完了,再看一下完整代码:

前序遍历:

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;
    }
};

那么前序遍历写出来之后,中序和后序遍历就不难理解了,代码如下:

中序遍历:

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

后序遍历:

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

二叉树的迭代遍历

#算法公开课

《代码随想录》算法视频公开课 (opens new window):

  • 写出二叉树的非递归遍历很难么?(前序和后序)(opens new window)
  • 写出二叉树的非递归遍历很难么?(中序)) (opens new window)相信结合视频在看本篇题解,更有助于大家对本题的理解。

看完本篇大家可以使用迭代法,再重新解决如下三道leetcode上的题目:

  • 144.二叉树的前序遍历(opens new window)
  • 94.二叉树的中序遍历(opens new window)
  • 145.二叉树的后序遍历(opens new window)

#思路

为什么可以用迭代法(非递归的方式)来实现二叉树的前后中序遍历呢?

我们在栈与队列:匹配问题都是栈的强项 (opens new window)中提到了,递归的实现就是:每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中,然后递归返回的时候,从栈顶弹出上一次递归的各项参数,所以这就是递归为什么可以返回上一层位置的原因。

此时大家应该知道我们用栈也可以是实现二叉树的前后中序遍历了。

#前序遍历(迭代法)

我们先看一下前序遍历。

前序遍历是中左右,每次先处理的是中间节点,那么先将根节点放入栈中,然后将右孩子加入栈,再加入左孩子。

为什么要先加入 右孩子,再加入左孩子呢? 因为这样出栈的时候才是中左右的顺序。

动画如下:

不难写出如下代码: (注意代码中空节点不入栈)

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;
    }
};

此时会发现貌似使用迭代法写出前序遍历并不难,确实不难。

此时是不是想改一点前序遍历代码顺序就把中序遍历搞出来了?

其实还真不行!

但接下来,再用迭代法写中序遍历的时候,会发现套路又不一样了,目前的前序遍历的逻辑无法直接应用到中序遍历上。

#中序遍历(迭代法)

为了解释清楚,我说明一下 刚刚在迭代的过程中,其实我们有两个操作:

  1. 处理:将元素放进result数组中
  2. 访问:遍历节点

分析一下为什么刚刚写的前序遍历的代码,不能和中序遍历通用呢,因为前序遍历的顺序是中左右,先访问的元素是中间节点,要处理的元素也是中间节点,所以刚刚才能写出相对简洁的代码,因为要访问的元素和要处理的元素顺序是一致的,都是中间节点。

那么再看看中序遍历,中序遍历是左中右,先访问的是二叉树顶部的节点,然后一层一层向下访问,直到到达树左面的最底部,再开始处理节点(也就是在把节点的数值放进result数组中),这就造成了处理顺序和访问顺序是不一致的。

那么在使用迭代法写中序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素。

动画如下:

中序遍历,可以写出如下代码:

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;
    }
};

后序遍历(迭代法)

再来看后序遍历,先序遍历是中左右,后续遍历是左右中,那么我们只需要调整一下先序遍历的代码顺序,就变成中右左的遍历顺序,然后在反转result数组,输出的结果顺序就是左右中了,如下图:

所以后序遍历只需要前序遍历的代码稍作修改就可以了,代码如下:

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;
    }
};

总结

此时我们用迭代法写出了二叉树的前后中序遍历,大家可以看出前序和中序是完全两种代码风格,并不像递归写法那样代码稍做调整,就可以实现前后中序。

这是因为前序遍历中访问节点(遍历节点)和处理节点(将元素放进result数组中)可以同步处理,但是中序就无法做到同步!

上面这句话,可能一些同学不太理解,建议自己亲手用迭代法,先写出来前序,再试试能不能写出中序,就能理解了。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/377173.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Pymysql之Connection中常用API

Connection中常用API 1、open() &#xff1a;检测数据库是否连接。 connect.open&#xff1a;如果数据库连接返回Trhe&#xff0c;否则返回False。 2、ping(reconnectTrue) connect.ping(reconnectTrue):如果reconnectTrue表示连接断开后&#xff0c;重新进行连接。 import…

春节假期如何高效管理Shopee虾皮本土店?技巧都给你整理好了!

EasyBoss ERP 对于中国人最重要的春节即将来临&#xff0c;但对于运营Shopee、TikTok Shop等平台的卖家而言&#xff0c;他们的客户可不会过春节。为了不影响店铺的业绩&#xff0c;很多卖家在春节期间都还是照常运营店铺&#xff0c;但又不想错过和家人团圆的机会怎么办&…

《Java程序设计》实验报告(一)之Java语言基础

实验内容及步骤&#xff1a; 编写”hello world”应用程序。&#xff08;1&#xff09;代码&#xff1a; public class HelloWorld { public static void main(String[] args) { System.out.println("Hello world!"); } } &#xff08;2&#xff09;运行…

惟客数据地产经营分析解决方案-构建数字化经营体系,提高精细化管理能力

惟客数据地产经营分析解决方案以拉通数据底座&#xff0c;以管理行为、量化考核、预警机制为核心&#xff0c;强化对经营风险的识别和解决&#xff0c;以终为始&#xff0c;通过高频高价值场景的应用适配&#xff0c;支撑企业在数字化时代中不断创新、转型&#xff0c;提升企业…

使用Pillow来生成简单的红包封面

Pillow库&#xff08;Python Imaging Library的后继&#xff09;是一个强大而灵活的图像处理库&#xff0c;适用于Python。Pillow 库&#xff08;有时也称 PIL 库&#xff09; 是 Python 图像处理的基础库&#xff0c;它是一个免费开源的第三方库&#xff0c;由一群 Python 社区…

SSL协议是什么?关于SSL和TLS的常见问题解答

SSL&#xff08;安全套接字层&#xff09;及其后继者TLS&#xff08;传输层安全&#xff09;是用于在联网计算机之间建立经过身份验证和加密的链接的协议。尽管SSL协议在 1999年已经随着TLS 1.0的发布而被弃用&#xff0c;但我们仍将这些相关技术称为“SSL”或“SSL/TLS”。那么…

VM 虚拟机和容器技术之间有什么区别?

随着云计算技术的不断发展&#xff0c;虚拟机和容器技术作为两种常见的虚拟化技术&#xff0c;被广泛应用于云计算领域。虽然虚拟机和容器技术都是虚拟化技术&#xff0c;但它们之间存在一些重要的区别。本文将详细介绍虚拟机和容器技术的区别&#xff0c;以便读者更好地了解这…

2.7:二叉树创建、先中后遍历、各个节点度的个数、深度

1.二叉树的创建、先中后遍历、各个节点度的个数、深度 程序代码&#xff1a; 1 #include<stdio.h>2 #include<string.h>3 #include<stdlib.h>4 typedef char datatype;5 typedef struct node6 {7 datatype data;8 struct node *lchild;9 struct…

如何使用数据恢复软件恢复已删除的数据

本教程介绍如何使用奇客数据恢复软件有效地从各种存储系统中恢复已删除的数据&#xff1a; 您是否曾经不小心从系统中删除了数周或数月的工作成果&#xff1f; 如果是这样&#xff0c;那么请从您并不孤单这一事实中找到安慰。这种严重且后果严重的判断错误在世界各地的计算机…

【leetcode】深搜、暴搜、回溯、剪枝(C++)1

深搜、暴搜、回溯、剪枝&#xff08;C&#xff09;1 一、全排列1、题目描述2、代码3、解析 二、子集1、题目描述2、代码3、解析 三、找出所有子集的异或总和再求和1、题目描述2、代码3、解析 四、全排列II1、题目解析2、代码3、解析 五、电话号码的字母组合1、题目描述2、代码3…

21.HarmonyOS App(JAVA)自适应布局Layout使用方法

AdaptiveBoxLayout是鸿蒙操作系统中最具有特色的布局&#xff0c;可以方便开发者对组件的自适应排布。 AdaptiveBoxLayout是自适应盒子布局&#xff0c;该布局提供了在不同屏幕尺寸设备上的自适应布局能力&#xff0c;主要用于相同级别的多个组件需要在不同屏幕尺寸设备上自动调…

LLM(5) | Encoder 和 Decoder 架构

LLM(5) | Encoder 和 Decoder 架构 文章目录 LLM(5) | Encoder 和 Decoder 架构0. 目的1. 概要2. encoder 和 decoder 风格的 transformer (Encoder- And Decoder-Style Transformers)原始的 transformer (The original transformer)编码器 (Encoders)解码器 (Decoders)编码器和…

2024三掌柜赠书活动第九期:Node.js从基础到项目实践(视频教学版)

目录 前言Node.js从基础到项目实践关于《Node.js从基础到项目实践(视频教学版)》编辑推荐内容简介作者简介图书目录书中前言/序言《Node.js从基础到项目实践(视频教学版)》全书速览结束语 前言 随着Web应用的快速发展&#xff0c;Node.js作为一种强大的JavaScript运行时环境&…

前端-Vue項目初始化

大家好我是苏麟 , 今天聊聊前端依赖 Ant Design Vue 快速初始化项目 . Ant Design Vue官网 : 快速上手 - Ant Design Vue (antdv.com) 初始化项目 找到文档->快速上手 脚手架命令 : npm install -g vue/cli 找到一个文件夹(不要在中文路径) 下打开cmd窗口输入脚手架命令 成…

Flink实战六_直播礼物统计

接上文&#xff1a;Flink实战五_状态机制 1、需求背景 现在网络直播平台非常火爆&#xff0c;在斗鱼这样的网络直播间&#xff0c;经常可以看到这样的总榜排名&#xff0c;体现了主播的人气值。 人气值计算规则&#xff1a;用户发送1条弹幕互动&#xff0c;赠送1个荧光棒免费…

Mac电脑清空特别大型旧文件如何一键清理?

在我们的数字生活中&#xff0c;Mac电脑常常承载着大量个人资料和重要文件。但当我们决定把自己的Mac送给亲人或朋友使用时&#xff0c;面临的首要任务便是彻底且高效地清空所有个人数据&#xff0c;以保证隐私安全。传统的删除方法虽然简单&#xff0c;但往往不能彻底清除所有…

WebSocket相关问题

1.WebSocket是什么&#xff1f;和HTTP的区别&#xff1f; WebSocket是一种基于TCP连接的全双工通信协议&#xff0c;客户端和服务器仅需要一次握手&#xff0c;两者之间就可以创建持久性的连接&#xff0c;并且支持双向数据的传输。WebSocket和HTTP都是基于TCP的应用层协议&am…

Pytorch+NCCL源码编译

目录 环境1. 安装cudnn2. 使用pytorch自带NCCL库进行编译3. 修改NCCL源代码并重新编译后测试&#xff0c;体现出源码更改 环境 Ubuntu 22.04.3 LTS (GNU/Linux 5.15.0-91-generic x86_64)cuda 11.8 cudnn 8python 3.10torch V2.0.1 nccl 2.14.3NVIDIA GeForce RTX 4090 *2 1.…

【C++】基础知识讲解(引用、内联、auto,基于范围for循环)

&#x1f308;个人主页&#xff1a;秦jh__https://blog.csdn.net/qinjh_?spm1010.2135.3001.5343&#x1f525; 系列专栏&#xff1a;http://t.csdnimg.cn/eCa5z 目录 引用 概念 特性 使用场景 作参数 作返回值 传值、传引用效率比较 引用和指针的区别 内联函数 概念…

git 使用 (备查)

git忽略清单 添加忽略清单 SSH免登录 ssh协议可以实现免登录操作&#xff0c;身份验证通过密钥实现。 跨团队写作 解决冲突 拉取 克隆 拉取最新版本 推送 远程仓库别名 直接使用git push推送 多人协作开发 分支命令 合并分支命令在主分支使用&#xff0c;将develop分支合并到…