代码算法训练营day14 | 理论基础、递归遍历

day14:

  • 理论基础
    • 二叉树的分类:
    • 二叉树的种类:
      • 满二叉树
      • 完全二叉树
      • 二叉搜索树
      • 平衡二叉搜索树
    • 二叉树的存储方式:
      • 链式存储
      • 顺序存储
    • 二叉树的遍历方式:
      • 深度优先和广度优先遍历实现方式
    • 二叉树的定义:
  • 递归遍历
    • 递归三要素:
    • 举例子:
    • 前序遍历:
    • 中序遍历:
    • 后序遍历:

理论基础

二叉树的分类:

二叉树分类

二叉树的种类:

满二叉树

满二叉树:如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。
满二叉树
这棵二叉树为满二叉树,也可以说深度为k,有2^k-1个节点的二叉树。(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底层实现是哈希表。

二叉树的存储方式:

二叉树可以链式存储,也可以顺序存储。
那么链式存储方式就用指针, 顺序存储的方式就是用数组。
顾名思义就是顺序存储的元素在内存是连续分布的,而链式存储则是通过指针把分布在各个地址的节点串联一起。

链式存储

在这里插入图片描述

顺序存储

在这里插入图片描述
如果父节点的数组下标是 i,那么它的左孩子就是 i * 2 + 1,右孩子就是 i * 2 + 2。
但是用链式表示的二叉树,更有利于我们理解,所以一般我们都是用链式存储二叉树。

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

二叉树的遍历方式:

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

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

这两种遍历是图论中最基本的两种遍历方式。
深度优先遍历
3. 前序遍历(递归法,迭代法)
4. 中序遍历(递归法,迭代法)
5. 后序遍历(递归法,迭代法)
广度优先遍历
6. 层次遍历(迭代法)

这里前中后序,其实指的就是中间节点的遍历顺序,只要大家记住 前中后序指的就是中间节点的位置就可以了。
看如下中间节点的顺序,就可以发现,中间节点的顺序就是所谓的遍历方式:

  • 前序遍历:中左右
  • 中序遍历:左中右
  • 后序遍历:左右中
    在这里插入图片描述

深度优先和广度优先遍历实现方式

我们做二叉树相关题目,经常会使用递归的方式来实现深度优先遍历,也就是实现前中后序遍历,使用递归是比较方便的。
之前我们讲栈与队列的时候,就说过栈其实就是递归的一种实现结构,也就说前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。
而广度优先遍历的实现一般使用队列来实现,这也是队列先进先出的特点所决定的,因为需要先进先出的结构,才能一层一层的来遍历二叉树。

二叉树的定义:

我们来看看链式存储的二叉树节点的定义方式:

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

大家会发现二叉树的定义 和链表是差不多的,相对于链表 ,二叉树的节点里多了一个指针, 有两个指针,指向左右孩子。
TreeNode(int x) : val(x), left(NULL), right(NULL) {}的意思是创建一个新的TreeNode对象,其值为x,并且它的左右子节点都被初始化为NULL。


递归遍历

递归三要素:

介绍前后中序的递归写法,要通过简单题目把方法论确定下来,有了方法论,后面才能应付复杂的递归。
这里确定下来递归算法的三个要素。每次写递归,都按照这三要素来写:

  1. 确定递归函数的参数和返回值: 确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数, 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
  2. 确定终止条件: 写完了递归算法, 运行的时候,经常会遇到栈溢出的错误,就是没写终止条件或者终止条件写的不对,操作系统也是用一个栈的结构来保存每一层递归的信息,如果递归没有终止,操作系统的内存栈必然就会溢出。
  3. 确定单层递归的逻辑: 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

举例子:

以前序遍历为例:(中左右)
4. 确定递归函数的参数和返回值: 因为要打印出前序遍历节点的数值,所以参数里需要传入vector数组来放节点的数值,还要再放一个根节点,除此之外就不需要再处理什么数据了也不需要有返回值,所以递归函数返回类型就是void,代码如下:

void traversal(TreeNode* cur, vector<int>& vec)
  1. 确定终止条件: 在递归的过程中,如何算是递归结束了呢,当然是当前遍历的节点是空了,那么本层递归就要结束了,所以如果当前遍历的这个节点是空,就直接return,返回到上一层的递归中,代码如下:
if (cur == NULL) return;

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

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);    // 中
}

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

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

相关文章

Mac钥匙串无法导出.p12证书解决方案

Mac钥匙串无法导出.p12证书解决方案 原因&#xff1a; 当想要将文件导出时&#xff0c;发现.p12的选项是灰色的不被允许 解决方法&#xff1a; 切换到我的证书、或者是证书的一栏&#xff0c;然后在导出&#xff0c;就是.p12的证书文件了。

LeetCode-118. 杨辉三角【数组 动态规划】

LeetCode-118. 杨辉三角【数组 动态规划】 题目描述&#xff1a;解题思路一&#xff1a;Python 动态规划解题思路二&#xff1a;解题思路三&#xff1a;0 题目描述&#xff1a; 给定一个非负整数 numRows&#xff0c;生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中&…

什么是多路复用器滤波器

本章将更深入地介绍多路复用器滤波器&#xff0c;以及它们如何用于各种应用中。您将了解到多路复用器如何帮助设计人员创造出更复杂的无线产品。 了解多路复用器 多路复用器是一组射频(RF)滤波器&#xff0c;它们组合在一起&#xff0c;但不会彼此加载&#xff0c;可以在输出之…

基于Java+SpringBoot+Vue煤矿信息管理系统(源码+文档+部署+讲解)

一.系统概述 系统根据现有的管理模块进行开发和扩展&#xff0c;采用面向对象的开发的思想和结构化的开发方法对煤矿信息管理的现状进行系统调查。采用结构化的分析设计&#xff0c;该方法要求结合一定的图表&#xff0c;在模块化的基础上进行系统的开发工作。在设计中采用“自…

每日OJ题_两个数组dp⑥_力扣97. 交错字符串

目录 力扣97. 交错字符串 解析代码 力扣97. 交错字符串 97. 交错字符串 难度 中等 给定三个字符串 s1、s2、s3&#xff0c;请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。 两个字符串 s 和 t 交错 的定义与过程如下&#xff0c;其中每个字符串都会被分割成若干 非空 子…

Windows摄像头推流-RTSP

0.背景&#xff1a; 调试rtsp视频流时&#xff0c;没有网络摄像头怎么办&#xff0c;只需要在同一个局域网下&#xff0c;用windows推送rtsp流&#xff0c;就可以在linux进行接收。 1.下载资源包 资源包链接&#xff1a;https://pan.baidu.com/s/1008I7TKazE4JgFiozhtekg?pw…

深入理解Linux veth虚拟网络设备:原理、应用与在容器化架构中的重要性

在Linux网络虚拟化领域&#xff0c;虚拟以太网设备&#xff08;veth&#xff09;扮演着至关重要的角色&#x1f310;。veth是一种特殊类型的网络设备&#xff0c;它在Linux内核中以成对的形式存在&#xff0c;允许两个网络命名空间之间的通信&#x1f517;。这篇文章将从多个维…

动态路由-基于vue-admin-template

基于 vue-admin-template的动态路由 1. 拆分静态路由与动态路由 静态路由----所有人都可以访问—首页/登录/404 动态路由–有权限的人才可以访问—组织/角色/员工/权限 2. 根据用户权限添加动态路由 获取对应的权限标识(vuex中actions中把用户资料通过return 进行返回&…

基于遗传优化的SVD水印嵌入提取算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 5.完整程序 1.程序功能描述 基于遗传优化的的SVD水印嵌入提取算法。对比遗传优化前后SVD水印提取性能&#xff0c;并分析不同干扰情况下水印提取效果。 2.测试软件版本以及运行结果展示 MA…

通过系统防火墙,禁用同网段主机互访

要通过系统防火墙禁止同网段主机之间的互访&#xff0c;您可以在Windows操作系统中使用高级防火墙规则来实现。以下是在Windows环境中创建一条规则以阻止本地同一子网内的计算机互相访问的基本步骤&#xff1a; 对于Windows防火墙&#xff08;适用于Windows 7至Windows 11&…

Postman —— postman的介绍和安装

Postman的介绍 Postman 是一款谷歌开发的接口测试工具,使API的调试与测试更加便捷。 它提供功能强大的 Web API & HTTP 请求调试。它能够发送任何类型的HTTP 请求 (GET, HEAD, POST, PUT..)&#xff0c;附带任何数量的参数 headers postman是一款支持http协议的接口调试与…

TypeScript系列之-理解TypeScript类型系统画图讲解

TypeScript的输入输出 如果我们把 Typescript 编译器看成一个黑盒的话。其输入则是使用 TypeScript 语法书写的文本或者文本集合。 输出是编译之后的 JS 文件 和 .d.ts 的声明文件 其中 JS 是将来需要运行的文件(里面是没有ts语法&#xff0c;有一个类型擦除的操作)&#xff0…

谁懂!微信自动化操作,让你事半功倍!

作为一名有多个微信号的人来说&#xff0c;懂得使用工具来提高微信的管理和办公效率是非常有必要的&#xff01; 今天就给大家分享一个可以实现微信自动化操作的工具——微信管理系统&#xff0c;让大家都能高效办公&#xff01;下面一起来看看它都有哪些自动化功能吧&#xf…

工业机器人AGV底盘核心技术分享

AGV&#xff08;Automated Guided Vehicle&#xff09;工业机器人的底盘技术是其核心组成部分之一&#xff0c;它决定了机器人的移动性能、稳定性和适应性。AGV底盘技术的核心包括以下几个方面&#xff1a; 1、导航系统&#xff1a;AGV底盘通常配备有各种导航系统&#xff0c;…

C++中高阶数据结构(AVL树的原理讲解)

AVL树 AVL树的定义 avl本质是搜索树,是高度平衡二叉搜索树.特点是:任何树的左右子树的高度差不超过1.最大的高度差值最大也只能是1,也称之为平衡因子, 平衡因子就是右子树减去左子树的值,这个值的绝对值的最大值只能是1.这个平衡因子不是必须的,只是一种控制方式,方便我们更…

赛氪网|2024中国翻译协会年会“AI科技时代竞赛与就业”分论坛

在2024年中国翻译协会年会期间&#xff0c;赛氪网与中西部翻译协会共同体多边合作平台共同承办&#xff0c;于3月30日下午在长沙成功举办了“AI科技时代竞赛与就业分论坛”。该论坛汇聚了众多翻译界、科技界和教育界的专家学者&#xff0c;共同探讨科技、实践、就业与竞赛人才培…

FreeRTOS学习 -- 再识

工作中一直使用FreeRTOS进行着开发&#xff0c;但是没有进行过系统的总结过。现在将快速使用几天时间将FreeRTOS相关知识点加以总结。 官网&#xff1a; https://www.freertos.org/zh-cn-cmn-s/ 参看资料&#xff1a; 正点原子 STM32F1 FreeRTOS开发手册_V1.2.pdf The FreeRTOS…

OpenCV与AI深度学习 | 实战 | 使用OpenCV确定对象的方向(附源码)

本文来源公众号“OpenCV与AI深度学习”&#xff0c;仅用于学术分享&#xff0c;侵权删&#xff0c;干货满满。 原文链接&#xff1a;实战 | 使用OpenCV确定对象的方向(附源码) 导读 本文将介绍如何使用OpenCV确定对象的方向(即旋转角度&#xff0c;以度为单位)。 1 先决条件…

Clarity AI:免费开源的AI无损图片放大图像升级器和增强工具

可以作为Magnific AI的平替版本。Magnific AI是一款基于人工智能技术的图像处理工具&#xff0c;主要功能包括图像放大、像素级AI重绘、灵活的设置调整以及多种优化场景。它能够支持最高放大至16倍&#xff0c;甚至可以达到1亿像素的分辨率。此外&#xff0c;Magnific AI还具备…

lua学习笔记13(一些特殊用法的学习和三目运算符的实现)

print("*****************************一些特殊用法的学习*******************************") print("*****************************多变量赋值*******************************") local a,b,c114514,8848,"凌少" print(a) print(b) print(c) -…