树与二叉树堆:链式二叉树的实现

目录

链式二叉树的实现:

前提须知:

前序:

中序:

后序:

链式二叉树的构建: 

定义结构体:

初始化: 

构建左右子树的指针指向:

前序遍历的实现: 

中序遍历的实现: 

后序遍历的实现: 

 求二叉树结点个数:

写法1: 

写法2: 

求树的叶子结点个数: 

求树的高度: 

求第K层结点: 

链式二叉树的实现:

前提须知:

链式二叉树的实现主要服务于那些不能被数组存储的非满二叉树和非完全二叉树,而在这些二叉树中,我们又将它们的组成结构进行拆分,分别是根、左子树、右子树。

而左子树和右子树又可以根据该结构划分为它们的根、左子树、右子树。 

前序:

 是将二叉树以根、左子树、右子树顺序进行结构划分遍历的遍历方式。

如图所示:其中N表示结点是NULL

以数字表示为:1 2 3 N N N 4 5 N N 6 N N

中序:

 是将二叉树以左子树、根、右子树顺序进行结构划分遍历的遍历方式。

如图所示:其中N表示结点是NULL

以数字表示为N 3 N 2 N 1 N 5 N 4 N 6 N

后序:

 是将二叉树以左子树、右子树、根顺序进行结构划分遍历的遍历方式。

如图所示:其中N表示结点是NULL

 以数字表示为N N 3 N 2 N N 5 N N 6 4 1

链式二叉树的构建: 

万恶之源~递归! 

定义结构体:

一个链式二叉树,需要有存放结点元素的data、需要有两个分别指向左子树、右子树的指针。

初始化: 

 开辟空间构建结点:

记得将构建的结点的左右子树指针进行初始化,以及结点元素进行赋值。 

构建左右子树的指针指向:

构建的结点如上图的二叉树结构所示。

前序遍历的实现: 

前序遍历的思路是,根、左子树、右子树,所以先要打印根,在前往根的左子树,而根的左子树又可以进行前序的遍历,因此使用递归的思想,先不断地进行调用以此抵达最左边的结点,随后逐级的递归,然后再迈向右子树进行相同的操作,也就是调用进入左子树,然后逐级递归…… 

二叉树走向图 

代码调用思路图 

中序遍历的实现: 

中序的遍历思想是左子树、根、右子树,所以再打印上是先打印左子树而后再打印根结点,最后再打印右子树,所以利用递归的思想,想要遍历到最左的结点,之后打印,随后进入右子树中,接着遍历左子树,以此类推……

 二叉树走向图

代码思路调用图

后序遍历的实现: 

后序就是中序的指向右子树和打印结点子树互换顺序即可 

 求二叉树结点个数:

用递归的思想,将问题化解为左子树的结点个数+右子树的结点个数+根结点的结点个数。

  • 而左右子树的结点个数又可以划分为左子树的结点个数+右子树的结点个数+根结点的结点个数。
  • 因此,本题就可以变为如果当前结点不是NULL那++size,如果是NULL则返回return。
  • 而再递归中return 也仅仅只是跳出了这一回的进程,返回上一次调用的进程并进入下一条代码中。
写法1: 

图解

写法2: 

 写法2就是彻底的简化了写法1,使用了三目运算符,将++size问题彻底变为了1的累加。

如果root = NULL 则返回0,如果不等于NULL 则进行调用 进入左子树的递归调用和右子树的递归调用

求树的叶子结点个数: 

叶子结点概念:树与二叉树堆:树-CSDN博客 

该问题的核心可以拆分为 树的叶子结点个数 =  左子树叶子结点个数+右子树叶子结点个数 

本问题其实是上一个问题的进阶版本,本质上多了两个条件,也就是当结点的左右子树指针指向的是NULL时便返回1,表示该节点是叶子节点,而非叶子节点则进入调用,分别进入结点的左右子树进行递归调用,知道root == NULL 或者是叶子节点,进行return 返回上一个结点开始逐级返回……

求树的高度: 

 本问题可以转化为求树的高度是左子树、右子树二者中高度最大的+1 ,这个1是根结点,由此可以化为1的累加问题。

也便是通过 root == NULL 进行逐级的返回,和+1来达成1的累加。

  1. 如上代码所示,进入了最左边的结点后,以root == NULL 为返回条件
  2. 当最左边结点的左子树的leftheight因为root == NULL 返回0, 结束后返回到了上一个结点(最左结点),并进入了该结点(最左结点)的右子树
  3. 随后右子树又以root == NULL 返回后,进入两个子树的高度对比
  4. 因为NULL 所以这里的两个返回值是 0 +1 和 0 + 1 进行对比,所以最后返回1 到本结点(最左结点)的上一个节点 (最左结点的父亲结点)

使用特殊函数进行比较 

求第K层结点: 

 假设,如果再根节点是求第K层,那么再根结点的左右子树的根结点来看是k-1层

  • 又因为 条件 root ==NULL 表示树是空的,所以返回0,而k == 1表示树只有一个根结点,所以只有一个结点
  • 又因为树可以拆分左右子树和根,而左右子树又可以继续拆分,而又是求第K层的结点个数,所以可以通过K==1这个条件进行返回进行回代数值。 
  • 也因此可以使用k>1和k-1进行不断地调用到第K层,然后进行回代返回值

注意,是带回返回值,而不是将返回值进行累加

思路图 


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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Android String.xml 设置加粗字体/修改字体颜色/动态设置修改文案

之前经常使用Spannable 这次主要在String.xml使用&#xff1a;<![CDATA[和]]> 效果&#xff1a; <resources><string name"str_bianse"><![CDATA[变色 <font color"#ff0000">曲项向天歌</font> 白毛浮绿水]]></st…

Leetcode—266.回文排列【简单】Plus

2023每日刷题&#xff08;四十&#xff09; Leetcode—266.回文排列 C语言实现代码 char chara[26] {0};int calculate(char *arr) {int nums 0;for(int i 0; i < 26; i) {nums arr[i];}return nums; }bool canPermutePalindrome(char* s) {int len strlen(s);for(in…

InstructDiffusion-多种视觉任务统一框架

论文:《InstructDiffusion: A Generalist Modeling Interface for Vision Tasks》 github&#xff1a;https://github.com/cientgu/InstructDiffusion InstructPix2Pix&#xff1a;参考 文章目录 摘要引言算法视觉任务统一引导训练集重构统一框架 实验训练集关键点检测分割图像…

Vue3的项目创建到启动

Vue3的项目创建 检查node版本创建 npm init vuelatest 安装依赖 项目启动 启动成功

OpenAI再次与Sam Altman谈判;ChatGPT Voice正式上线

11月22日&#xff0c;金融时报消息&#xff0c;OpenAI迫于超过700名员工联名信的压力&#xff0c;再次启动了与Sam Altman的谈判&#xff0c;希望他回归董事会。 在Sam确定加入微软后&#xff0c;OpenAI超700名员工签署了一封联名信&#xff0c;要求Sam和Greg Brockman&#x…

Spring---对象的存储和读取

文章目录 Spring对象的存储创建Bean对象将Bean对象存储到spring中添加配置文件存储Bean对象 Spring对象的读取得到Spring上下文对象从Spring中取出Bean对象使用Bean对象 Spring对象的存储 创建Bean对象 Bean对象其实就是一个普通的Java对象。我们按照创建Java对象的方式来创建…

【云原生】什么是 Kubernetes ?

什么是 Kubernetes &#xff1f; Kubernetes 是一个开源容器编排平台&#xff0c;管理着一系列的 主机 或者 服务器&#xff0c;它们被称作是 节点&#xff08;Node&#xff09;。 每一个节点运行了若干个相互独立的 Pod。 Pod 是 Kubernetes 中可以部署的 最小执行单元&#x…

USB驱动开发基础

USB标准 USB1.0&#xff0c; 1996&#xff0c;低速1.5Mbps和高速12Mbps&#xff0c;USB1.1 iMac G3&#xff0c;Type A和Type B接口USB 2.0 2000&#xff0c; 480Mpbs&#xff0c;Type A/B/C接口、Micro A/BUSB 3.0 5Gbps, 随着USB 3.2命名规定&#xff0c;现在也叫USB 3.2 Ge…

Linux网络——数据链路层

目录 一.认识以太网 二.以太网帧格式 三.认识MAC地址 四.认识MTU 五.以太局域网的通信原理 六.其他重要协议 1.DNS协议 2.域名简介 3.ICMP协议 4.NAT技术 5.NAT技术的缺陷 6.NAT和代理服务器 一.认识以太网 "以太网" 不是一种具体的网络, 而是一种技术标…

docker (简介、dcoker详细安装步骤、容器常用命令)一站打包- day01

一、 为什么出现 Docker是基于Go语言实现的云开源项目。 Docker的主要目标是“Build&#xff0c;Ship and Run Any App,Anywhere”&#xff0c;也就是通过对应用组件的封装、分发、部署、运行等生命周期的管理&#xff0c;使用户的APP&#xff08;可以是一个WEB应用或数据库应…

数据库的重要你了解多少?如何保障数据库的安全?

随着信息技术的快速发展&#xff0c;数据库已经成为企业、组织以及个人日常生活中不可或缺的一部分。然而&#xff0c;随着数据库的广泛应用&#xff0c;其安全性问题也日益凸显。数据库的安全性主要包括数据的完整性、保密性和可用性。本文将探讨数据库安全性的重要性、以及如…

常使用的定时任务

常使用的定时任务 一、 linux自带的定时任务 1、crontab 有这样一个需求&#xff1a;我们使用Java写一个工具jar包在系统空闲的时候去采集已经部署在Linux系统上的项目的一 些数据&#xff0c;可以使用 linux 系统的 crontab。 运行crontab -e&#xff0c;可以编辑定时器&…

C语言——深入理解指针(3)

目录 1. 字符指针 2. 数组指针 2.1 数组指针变量 2.2 数组指针变量的初始化 3.二维数组传参&#xff08;本质&#xff09; 4. 函数指针 4.1 函数指针变量的创建 4.2 函数指针的使用 4.3 typedef 5. 函数指针数组 6. 转移表&#xff08;函数指针数组的使用&#xff…

sqli-labs(7)

32. 看到“前面有了\这里使用宽字节注入 当字符的大小为一个字节时为窄字节 当字符的大小为两个字节时为宽字节 英文字符的大小为一个字节&#xff0c;汉字为两个 漏洞产生的成因在sql中使用像GB2312,GBK,GB18030,BIG5,Shift_JIS这些宽字节编码而php使用utf-8编码 为了防止注…

token认证机制,基于JWT的Token认证机制实现,安全性的问题

文章目录 token认证机制几种常用的认证机制HTTP Basic AuthOAuthCookie AuthToken AuthToken Auth的优点 基于JWT的Token认证机制实现JWT的组成认证过程登录请求认证 对Token认证的五点认识JWT的JAVA实现 基于JWT的Token认证的安全问题确保验证过程的安全性如何防范XSS Attacks…

基于YOLOv5的人群计数系统设计系统

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介系统概述系统功能核心技术系统架构系统优势 二、功能三、系统四. 总结  总结 一项目简介 基于YOLOv5的人群计数系统设计是一个非常有趣且具有挑战性的项目…

第20章 多线程

创建线程 继承Thread 类 Thread 类时 java.lang 包中的一个类&#xff0c;从类中实例化的对象代表线程&#xff0c;程序员启动一个新线程需要建立 Thread 实例。 Thread 对象需要一个任务来执行&#xff0c;任务是指线程在启动时执行的工作&#xff0c;start() 方法启动线程&am…

java开发需要用到的软件,必备软件工具一览

java开发需要用到的软件&#xff0c;必备软件工具一览 如果你对Java编程感兴趣或已经是一名Java开发者&#xff0c;你需要一些必备的软件工具来提高你的生产力和简化开发过程。在本文中&#xff0c;我们将探讨Java开发所需的关键软件工具&#xff0c;并通过具体示例来解释它们的…

人力资源管理后台 === 上传+权限数据

目录 1.员工详情-封装员工头像组件 2.员工详情-上传图片-创建腾讯云存储桶 3.员工详情-使用cos-sdk完成上传 4. 权限管理-搭建权限页面 5.权限管理-获取数据转化树形 6.权限管理-作业 7.权限应用-权限概念 8.权限应用-员工分配角色-弹出层 9.权限应用-员工分配角色-回…

15:00面试,15:06就出来了,问的问题有点变态。。。

从小厂出来&#xff0c;没想到在另一家公司又寄了。 到这家公司开始上班&#xff0c;加班是每天必不可少的&#xff0c;看在钱给的比较多的份上&#xff0c;就不太计较了。没想到8月一纸通知&#xff0c;所有人不准加班&#xff0c;加班费不仅没有了&#xff0c;薪资还要降40%…