当前位置: 首页 > news >正文

网站开发和网站建设/新平台推广

网站开发和网站建设,新平台推广,用php做视频网站有哪些,三门峡网站开发文章目录 一:实现链式结构二叉树1.1前中后序遍历1.1.1遍历规则1.1.2代码实现 1.2结点个数以及高度等1.2.1二叉树结点个数1.2.2二叉树叶子结点个数1.2.3二叉树第k层结点个数1.2.4二叉树的深度/高度1.2.5 二叉树查找值为x的结点1.2.6二叉树的销毁 1.3层序遍历1.4判断是…

文章目录

  • 一:实现链式结构二叉树
    • 1.1前中后序遍历
      • 1.1.1遍历规则
      • 1.1.2代码实现
    • 1.2结点个数以及高度等
      • 1.2.1二叉树结点个数
      • 1.2.2二叉树叶子结点个数
      • 1.2.3二叉树第k层结点个数
      • 1.2.4二叉树的深度/高度
      • 1.2.5 二叉树查找值为x的结点
      • 1.2.6二叉树的销毁
    • 1.3层序遍历
    • 1.4判断是否为完全二叉树
  • 二:结语

欢迎大家阅读我的博客,给生活加点impetus,!!
在这里插入图片描述
今天我们学习二叉树的实现,感受递归的魅力!!

一:实现链式结构二叉树

链表来表⽰⼀棵⼆叉树,即⽤链来指⽰元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成数据域和左右指针域,左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址

我们先来定义链式结构二叉树的结构。

在这里插入图片描述

链式结构二叉树是由结点组成的,定义二叉树的结构就是定义结点的结构

在数据结构初阶的学习过程中中,前期对于二叉树的插入代码不会深入研究,在后期c++阶段学习红黑树,平衡树等会对二叉树数据的插入操作进行研究。

我们需要了解二叉树的遍历方式有哪些

1.1前中后序遍历

为了后方我们能够理解深刻,我们先依据下列图示来手动创建一个二叉树

在这里插入图片描述
这里我们的存储类型为char类型,因为存储的是字符。
创建结点:
在这里插入图片描述
构造链式二叉树:
在这里插入图片描述
接下来我们来深入讲解各种遍历方法的规则。

1.1.1遍历规则

按照规则,⼆叉树的遍历有:前序/中序/后序的递归结构遍历:
1)前序遍历(Preorder Traversal 亦称先序遍历):访问根结点的操作发⽣在遍历其左右⼦树之前
访问顺序为:根结点、左⼦树、右⼦树
2)中序遍历(Inorder Traversal):访问根结点的操作发⽣在遍历其左右⼦树之中(间)
访问顺序为:左⼦树、根结点、右⼦树
3)后序遍历(Postorder Traversal):访问根结点的操作发⽣在遍历其左右⼦树之后
访问顺序为:左⼦树、右⼦树、根结点

接下来依靠规则自行先思考上述二叉树的遍历顺序,先来说明结果

在这里插入图片描述
前序遍历:首先从根结点进入,依照前序遍历规则–根左右首先A结点是根结点,可以直接打印,左方为B结点,B同样也是根结点,所以打印B后会继续向下遍历,直到找到不为根结点的结点,其实就是叶子结点NULL,右的话就是D结点右子树NULL,此时B结点的整个左子树遍历完全,同样方法遍历右子树,直至A结点的左子树全部遍历完毕。同理遍历右子树。

顺序为A B D NULL NULL NULL C E NULL NULL F NULL NULL

中序遍历:首先从根结点进入,依照前序遍历规则–左根右首先A结点是根结点,不能打印,会继续向左遍历,直至找到不为任何子树的结点(度为0的结点,即叶子结点),先打印D的左子树,再打印D,最后打印D的右子树,随后B的整个左子树打印完毕,打印B后,再打印B的右子树,随后A的整个左子树打印完毕打印A后,随后打印A的右子树,同理。

顺序为NULL D NULL B NULL A NULL E NULL C NULL F NULL

后序遍历:首先从根结点进入,依照前序遍历规则–左右根首先A结点是根结点,不能打印,会继续向左遍历,直至找到不为任何子树的结点(度为0的结点,即叶子结点),先打印D的左子树,再打印D的右子树,再打印D,随后B的整个左子树打印完毕,打印B的右子树NULL,随后打印B,A的整个左子树打印完毕,同理打印A的右子树。

打印顺序:NULL NULL D NULL B NULL NULL E NULL NULL F C A

所以遍历时我们需要注意:

1:除叶子结点以外,其他结点都是根结点,当层次很多时,1到h-1层都是层次>=2的树或子树
2:遍历时主要是涉及递归函数

1.1.2代码实现

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

图解(前序遍历):

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

细节:
1:遍历只能从根结点开始遍历,且一定要根据口诀的顺序
2:遍历都是先经过包含叶子结点的二叉树
3:叶子结点其实是递归的结束条件
4:递推回归时与函数栈帧创建的联系
5:遍历时某结点看做根结点,该棵树一定要延伸到叶子结点,才能看做一棵树。

1.2结点个数以及高度等

1.2.1二叉树结点个数

大部分人想到的都是设置计数器,那我们来看看这个算法的好坏。

方法一:

在这里插入图片描述

在这里插入图片描述

所以这个地方我们需要传地址,而且,size既不能做全局变量,也不能做局部变量那我们索性添加一个参数

来看下面这段代码:
在这里插入图片描述

方法二:直接来返回int
思路:结点个数=根结点(1)+左子树结点+右子树结点

在这里插入图片描述
我们来画图演示一下:
在这里插入图片描述
逐步递推,逐步回归、
方法二同样能够实现预期结果,并且思路更加简单。

总结:
1:函数栈帧销毁:函数执行完全或者return提前返回
:2:局部变量+static生命周期延长,仍然存在作用域,上例修饰size时仍然错误

1.2.2二叉树叶子结点个数

思路**:左子树叶子结点个数+右子树叶子结点个数**

在这里插入图片描述

1.2.3二叉树第k层结点个数

思路:深度优先遍历,k自减,准确找到第k层,最后返回个数

在这里插入图片描述

1.2.4二叉树的深度/高度

思路:根结点+max{左子树,右子树}

在这里插入图片描述

最好使用变量接收一下,因为我们需要比较大小

1.2.5 二叉树查找值为x的结点

思路:查找左子树与右子树,同时该结点是否为X

在这里插入图片描述

1.2.6二叉树的销毁

思路:只能后序遍历,因为每一个结点malloc都要释放,如果先释放根结点,孩子结点就找不到了
在这里插入图片描述
注意:优先级高低:->大于*。
free之后及时置空,防止成为野指针

1.3层序遍历

前方的所有遍历都是涉及前中后序遍历,都是深度优先遍历
下面我们来讲解广度优先遍历(层序遍历),我们来看这样一个题目:
在这里插入图片描述
如果我们仍然按照深度优先来遍历的话,肯定是不行的,因为只有当该部分函数栈帧销毁之后,才会继续进入到上一个函数栈帧

思路:借助数据结构–队列根结点入队列,循环判断队列是否为空
不为空取队头出队头,将队头的左右且不为空的孩子入队列

我们来画图演示一下:
在这里插入图片描述
再来看一张:
在这里插入图片描述
下面是代码部分:
在这里插入图片描述

细节
1:我们涉及到了Queue,我们需要重新添加Queue.c和Queue.h文件
2:队列中存储的是二叉树结点指针类型,需要将Queue中定义的int改为struct BTNode
3:typedef重定义的是数据类型一定要加struct加以声明,只写BTNode会报错。
4:存储指针是因为结构体访问成员是指针类型(左孩子,右孩子),如果直接存储结构体会报错
5:如果也把空孩子加入,就会退出循环

1.4判断是否为完全二叉树

性质:
1:除最后一层外,其余结点的度都为2
2:有序

我们需要使用层序遍历

思路:层序遍历,根结点入队列,循环判断队列是否为空不为空取队头出队头,将队头的左右孩子入队列,不管是不是空遇到空停止循环比较队列剩余元素,如果还有非空元素,则为非完全二叉树,反之是完全二叉树

我们来画图理解观察区别,层序遍历部分我将不再演示:
在这里插入图片描述
接下来来看代码:
在这里插入图片描述

细节:
1:层序遍历入得都是top(队头)的左右孩子,如果写成root->left,这将面临死循环。
:2:这里的队列并不是依次相连的,中间有很多断开的,而最开始的Queue结点是一个一个依次相连的

二:结语

最后,感谢大家的阅读,欢迎大家有更多的思路与我交流,同时不足之处欢迎指正!!
逆水行舟–不进则退!!!加油,希望早日看见最好的自己!!
在这里插入图片描述

相关文章:

二叉树03(数据结构初阶)

文章目录 一:实现链式结构二叉树1.1前中后序遍历1.1.1遍历规则1.1.2代码实现 1.2结点个数以及高度等1.2.1二叉树结点个数1.2.2二叉树叶子结点个数1.2.3二叉树第k层结点个数1.2.4二叉树的深度/高度1.2.5 二叉树查找值为x的结点1.2.6二叉树的销毁 1.3层序遍历1.4判断是…...

ComfyUI工作流 图像反推生成人像手办人像参考(SDXL版)

文章目录 图像反推生成人像手办人像参考SD模型Node节点工作流程效果展示开发与应用图像反推生成人像手办人像参考 本工作流旨在通过利用 Stable Diffusion XL(SDXL)模型和相关辅助节点,实现高效的人像参考生成和手办设计。用户可通过加载定制的模型、LORA 调整和控制节点对…...

【01】共识机制

BTF共识 拜占庭将军问题 拜占庭将军问题是一个共识问题 起源 Leslie Lamport在论文《The Byzantine Generals Problem》提出拜占庭将军问题。 核心描述 军中可能有叛徒,却要保证进攻一致,由此引申到计算领域,发展成了一种容错理论。随着…...

sentinel的限流原理

Sentinel 的限流原理基于 流量统计 和 流量控制策略,通过动态规则对系统资源进行保护。其核心设计包括以下几个关键点: 流量统计模型:滑动时间窗口 Sentinel 使用 滑动时间窗口算法 统计单位时间内的请求量,相比传统的固定时间窗…...

ZOJ 1007 Numerical Summation of a Series

原题目链接 生成该系列值的表格 对于x 的 2001 个值,x 0.000、0.001、0.002、…、2.000。表中的所有条目的绝对误差必须小于 0.5e-12(精度为 12 位)。此问题基于 Hamming (1962) 的一个问题,当时的大型机按今天的微型计算机标准来…...

『 C 』 `##` 在 C 语言宏定义中的作用解析

文章目录 ## 运算符的基本概念可变参数宏与 ## 的应用可变参数宏简介## 处理可变参数的两种情况可变参数列表为空可变参数列表不为空 示例代码验证 在 C 和 C 编程里,宏定义是个很有用的工具。今天咱们就来聊聊 ## 这个预处理器连接运算符在宏定义中的作用&#xff…...

独立成分分析 (ICA):用于信号分离或降维

人工智能例子汇总:AI常见的算法和例子-CSDN博客 独立成分分析 (Independent Component Analysis, ICA) 是一种用于信号分离和降维的统计方法,常用于盲源分离 (Blind Source Separation, BSS) 问题,例如音频信号分离或脑电信号 (EEG) 处理。…...

为什么会有函数调用参数带标签的写法?Swift函数调用的参数传递需要加前缀是否是冗余?函数调用?函数参数?

为什么会有函数调用参数带标签的写法? ObjC函数参数形式与众不同,实参前会加前缀,尤其参数很多的情况,可读性很强。例如: [person setAge: 29 setSex:1 setClass: 35]; 这种参数前面加前缀描述也被叫标签(Label). 注意&#xff0…...

实际操作 检测缺陷刀片

号he 找到目标图像的缺陷位置,首先思路为对图像进行预处理,灰度-二值化-针对图像进行轮廓分析 //定义结构元素 Mat se getStructuringElement(MORPH_RECT, Size(3, 3), Point(-1, -1)); morphologyEx(thre, tc, MORPH_OPEN, se, Point(-1, -1), 1); …...

使用Pygame制作“青蛙过河”游戏

本篇博客将演示如何使用 Python Pygame 从零开始编写一款 Frogger 风格的小游戏。Frogger 是一款早期街机经典,玩家需要帮助青蛙穿越车水马龙的马路到达对岸。本示例提供了一个精简原型,包含角色移动、汽车生成与移动、碰撞检测、胜利条件等关键点。希望…...

BUU17 [RoarCTF 2019]Easy Calc1

自用 源代码 $(#calc).submit(function(){$.ajax({url:"calc.php?num"encodeURIComponent($("#content").val()),type:GET,success:function(data){$("#result").html(<div class"alert alert-success"><strong>答案:&l…...

堆的实现——对的应用(堆排序)

文章目录 1.堆的实现2.堆的应用--堆排序 大家在学堆的时候&#xff0c;需要有二叉树的基础知识&#xff0c;大家可以看我的二叉树文章&#xff1a;二叉树 1.堆的实现 如果有⼀个关键码的集合 K {k0 , k1 , k2 , …&#xff0c;kn−1 } &#xff0c;把它的所有元素按完全⼆叉树…...

新生讲课——图和并查集

1.图的存储 &#xff08;1&#xff09;.邻接矩阵 邻接矩阵可以借助stl中的vector,我们通过开一个二维矩阵,g[u]中存储的是u可以到达的点,定义如下 const int N 2e5 10; vector<int> g[N] 若是遇到带权图则定义如下 const int N 2e5 10; vector <pair <int ,…...

基于深度学习的视觉检测小项目(十七) 用户管理后台的编程

完成了用户管理功能的阶段。下一阶段进入AI功能相关。所有的资源见文章链接。 补充完后台代码的用户管理界面代码&#xff1a; import sqlite3from PySide6.QtCore import Slot from PySide6.QtWidgets import QDialog, QMessageBoxfrom . import user_manage # 导入使用ui…...

实战:利用百度站长平台加速网站收录

本文转自&#xff1a;百万收录网 原文链接&#xff1a;https://www.baiwanshoulu.com/33.html 利用百度站长平台加速网站收录是一个实战性很强的过程&#xff0c;以下是一些具体的步骤和策略&#xff1a; 一、了解百度站长平台 百度站长平台是百度为网站管理员提供的一系列工…...

web-XSS-CTFHub

前言 在众多的CTF平台当中&#xff0c;作者认为CTFHub对于初学者来说&#xff0c;是入门平台的不二之选。CTFHub通过自己独特的技能树模块&#xff0c;可以帮助初学者来快速入门。具体请看官方介绍&#xff1a;CTFHub。 作者更新了CTFHub系列&#xff0c;希望小伙伴们多多支持…...

【C++】P1957 口算练习题

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 &#x1f4af;前言&#x1f4af;题目描述输入格式&#xff1a;输出格式&#xff1a; &#x1f4af;我的做法代码实现&#xff1a; &#x1f4af;老师的做法代码实现&#xff1a; &#x1f4af;对比分析&am…...

第二十三章 MySQL锁之表锁

目录 一、概述 二、语法 三、特点 一、概述 表级锁&#xff0c;每次操作锁住整张表。锁定粒度大&#xff0c;发生锁冲突的概率最高&#xff0c;并发度最低。应用在MyISAM、InnoDB、BDB等存储引擎中。 对于表级锁&#xff0c;主要分为以下三类&#xff1a; 1. 表锁 2. 元数…...

linux 进程补充

环境变量 基本概念 环境变量(environment variables)一般是指在操作系统中用来指定操作系统运行环境的一些参数 如&#xff1a;我们在编写C/C代码的时候&#xff0c;在链接的时候&#xff0c;从来不知道我们的所链接的动态静态库在哪 里&#xff0c;但是照样可以链接成功&#…...

渗透测试之文件包含漏洞 超详细的文件包含漏洞文章

目录 说明 通常分为两种类型&#xff1a; 本地文件包含 典型的攻击方式1&#xff1a; 影响&#xff1a; 典型的攻击方式2&#xff1a; 包含路径解释&#xff1a; 日志包含漏洞&#xff1a; 操作原理 包含漏洞读取文件 文件包含漏洞远程代码执行漏洞: 远程文件包含…...

Java 大视界 -- Java 大数据在智能医疗影像诊断中的应用(72)

💖亲爱的朋友们,热烈欢迎来到 青云交的博客!能与诸位在此相逢,我倍感荣幸。在这飞速更迭的时代,我们都渴望一方心灵净土,而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识,也期待你毫无保留地分享独特见解,愿我们于此携手成长,共赴新程!💖 一、…...

Web - CSS3浮动定位与背景样式

概述 这篇文章主要介绍了 CSS3 中的浮动定位、背景样式、变形效果等内容。包括 BFC 规范与创建方法、浮动的功能与使用要点、定位的多种方式及特点、边框与圆角的设置、背景的颜色、图片等属性、多种变形效果及 3D 旋转等&#xff0c;还提到了浏览器私有前缀。 BFC规范与浏览…...

ConcurrentHashMap线程安全:分段锁 到 synchronized + CAS

专栏系列文章地址&#xff1a;https://blog.csdn.net/qq_26437925/article/details/145290162 本文目标&#xff1a; 理解ConcurrentHashMap为什么线程安全&#xff1b;ConcurrentHashMap的具体细节还需要进一步研究 目录 ConcurrentHashMap介绍JDK7的分段锁实现JDK8的synchr…...

系统学习算法:专题九 穷举vs暴搜vs深搜vs回溯vs剪枝

其中标题的深搜&#xff0c;回溯&#xff0c;剪枝我们之前专题都已经有过学习和了解&#xff0c;这里多了两个穷举和暴搜&#xff0c;其实意思都差不多&#xff0c;穷举就是穷尽力气将所有情况都列举出来&#xff0c;暴搜就是暴力地去一个一个情况搜索&#xff0c;所以就是全部…...

解决 Pandas DataFrame 索引错误:KeyError:0

在使用 Pandas 处理数据时&#xff0c;KeyError 是一个常见的问题&#xff0c;尤其是在尝试通过索引访问数据时。本文将通过一个实际案例&#xff08;使用SKLearn中的MINIST数据集为例&#xff09;&#xff0c;详细分析 KeyError 的原因&#xff0c;并提供解决方法。 1 问题背…...

deepseek的对话风格

概述 deepseek的对话风格&#xff0c;比一般的模型的回答多了思考过程&#xff0c;这是它比较可爱的地方&#xff0c;模型的回答有了思考过程&#xff0c;对用户而言大模型的回答不完全是一个黑盒。 deepseek的对话风格 train_prompt_style """Below is an…...

制造业设备状态监控与生产优化实战:基于SQL的序列分析与状态机建模

目录 1. 背景与挑战 2. 数据建模与采集 2.1 数据表设计 设备状态表(记录设备实时状态变更)...

Javaweb学习之Mysql(Day5)

(一)Mysql概述 (1)MYSQL通用语法 SQL语句可以单行或多行书写,以分号结尾。 SQL语句可以使用空格/缩进来增强语句的可读性(即,空格和缩进不影响代码的执行)。 MySQL数据库的SQL语句不区分大小写。 注释: 1. 单行注释: -- 注释内容 或 # 注释内容 (MySQL 特有 …...

C++ Primer 迭代器

欢迎阅读我的 【CPrimer】专栏 专栏简介&#xff1a;本专栏主要面向C初学者&#xff0c;解释C的一些基本概念和基础语言特性&#xff0c;涉及C标准库的用法&#xff0c;面向对象特性&#xff0c;泛型特性高级用法。通过使用标准库中定义的抽象设施&#xff0c;使你更加适应高级…...

Java的String与StringBuilder例题

​​ package com.jiachen.StringBuilderDemo1;import java.util.Scanner;public class Exercise2 {public static void main(String[] args) {Scanner scanner new Scanner(System.in);String s scanner.nextLine().trim(); // 读取输入并去除前后空格String result;// 根据…...