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

Java数据结构第十二期:走进二叉树的奇妙世界(一)

专栏:数据结构(Java版)

个人主页:手握风云

目录

一、树型结构

1.1. 树的定义

1.2. 树的基本概念

1.3. 树的表示形式

二、二叉树

2.1. 概念

2.2. 两种特殊的二叉树

2.3. 二叉树的性质

2.4. 二叉树的存储

三、二叉树的基本操作


一、树型结构

1.1. 树的定义

        树是⼀种⾮线性的数据结构,它是由n(n>=0)个有限结点组成⼀个具有层次关系的集合。把它叫做 树是因为它看起来像⼀棵倒挂的树,也就是说它是根朝上,⽽叶朝下的。它具有以下的特点:

  1. 有⼀个特殊的结点,称为根结点,根结点没有前驱结点
  2. 除根结点外,其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm,其中每⼀个集合Ti (1 <= i <= m) ⼜是⼀棵与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱,可以有0个或多个后继
  3. 树是递归定义的

       注意,在树型结构中,子树与子树之间不能有交集,否则就不是树型结构。

1.2. 树的基本概念

结点的度:⼀个结点含有⼦树的个数称为该结点的度; 如上图,A的度为2

树的度:⼀棵树中,所有结点度的最⼤值称为树的度;如上图,树的度为3

叶子结点或终端结点:度为0的结点称为叶结点;如上图,G、H、I、J都是叶结点

父结点:若⼀个结点含有⼦结点,则这个结点称为其⼦结点的⽗结点;如上图,A是B的父节点

子结点:⼀个结点含有的⼦树的根结点称为该结点的⼦结点; 如上图,B是A的子结点

根结点:⼀棵树中,没有父结点的结点;如上图,A

结点的层次:从根开始定义起,根为第1层,根的⼦结点为第2层,以此类推

树的高度或深度:树中结点的最大层次;如上图,树的高度是4

1.3. 树的表示形式

       树结构相对线性表就比较复杂了,要存储表示起来就⽐较麻烦了,实际中树有很多种表示⽅式,如:双亲表示法,孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这⾥就简单的了解其中最常用的孩子兄弟表示法。

class Node{int val;//树中储存的数据Node firstChild;//第一个孩子引用Node nextBrother;//下一个兄弟引用
}

二、二叉树

2.1. 概念

        一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的⼆叉树组成。

       从上图中可以看出:⼆叉树不存在度⼤于2的结点;⼆叉树的⼦树有左右之分,次序不能颠倒,因此⼆叉树是有序树。

       注意:对于任意的⼆叉树都是由以下⼏种情况复合⽽成的。

2.2. 两种特殊的二叉树

  1. 满二叉树:如果一棵二叉树的层数为K,且结点总数是2^{k}-1 ,则它就是满⼆叉树。
  2. 完全二叉树:完全⼆叉树是由满⼆叉树⽽引出来的。对于深度 为K的,有n个结点的⼆叉树,当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从0⾄n-1的结点一一对应。满二叉树是一种特殊的完全二叉树。

2.3. 二叉树的性质

  1. 若规定根结点的层数为1,则⼀棵⾮空⼆叉树的第i层上最多有(i>0)个结点
  2. 若规定只有根结点的⼆叉树的深度为1,则深度为K的⼆叉树的最⼤结点数是(k>=0)
  3. 对任何⼀棵⼆叉树, 如果其叶结点个数为 n0, 度为2的⾮叶结点个数为 n2,则有n0=n2+1
  4. 具有n个结点的完全⼆叉树的深度k为上取整

2.4. 二叉树的存储

        二叉树的存储方式分为:顺序结构和类似于链式的结构。我们这里主要介绍链式存储。⼆叉树的链式存储是通过⼀个⼀个的节点引⽤起来的。

//孩子表示法
class Node{int val;//数据域Node left;//左孩子引用Node right;//右孩子引用
}//孩子双亲表示法
class Node{int val;Node left;Node right;Node parent;//当前节点的根节点
}

三、二叉树的基本操作

我们可以自己创建一个二叉树,我们可以参照之前创建链表、栈、队列的方式来手动创建二叉树。

public class BinaryTree {static class TreeNode{public char val;public TreeNode left;//左孩子结点引用public TreeNode right;//右孩子结点引用public TreeNode(char val) {this.val = val;}}public TreeNode CreateTree(){TreeNode A = new TreeNode('A');TreeNode B = new TreeNode('B');TreeNode C = new TreeNode('C');TreeNode D = new TreeNode('D');TreeNode E = new TreeNode('E');TreeNode F = new TreeNode('F');TreeNode G = new TreeNode('G');TreeNode H = new TreeNode('H');A.left = B;A.right = C;B.left = D;B.right = E;C.left = F;C.right = G;E.right = H;return A;}
}
public class Test {public static void main(String[] args) {BinaryTree binaryTree = new BinaryTree();BinaryTree.TreeNode root = binaryTree.CreateTree();//因为是静态内部类System.out.println("========");}
}

        我们在打印这一行大一个断点进行调试。先走完A结点,再通过递归的方法,去遍历左孩子结点B和右孩子结点C,以此类推,再去遍历B的左孩子结点E和右孩子结点F。

       二叉树可以空树也可以是非空树。非空树由根节点的左子树、根节点的右子树组成的。从概念中可以看出,⼆叉树定义是递归式的,因此后序基本操作中基本都是按照该概念实现的。

相关文章:

Java数据结构第十二期:走进二叉树的奇妙世界(一)

专栏&#xff1a;数据结构(Java版) 个人主页&#xff1a;手握风云 目录 一、树型结构 1.1. 树的定义 1.2. 树的基本概念 1.3. 树的表示形式 二、二叉树 2.1. 概念 2.2. 两种特殊的二叉树 2.3. 二叉树的性质 2.4. 二叉树的存储 三、二叉树的基本操作 一、树型结构 1.…...

Web的增删改查

准备环境 1. 添加web 点击项目右键——>选择**添加框架**选择**web应用程序** 2.创建lib目录 在web应用程序的**WEB-INF目录下**创建lib目录添加jar包(5个)解压&#xff1a;右键——>选择**添加库** 3.创建Dao层 在src目录下创建包com.zmq在该包下创建dao层添加工具…...

Java 前后端时间格式转换

在 Web 开发里&#xff0c;时间格式处理既常见又关键。由于前端和后端对时间的表示、处理方式存在差异&#xff0c;熟练掌握时间格式的转换方法就显得尤为重要。这篇文章会深入探讨 Java 前后端时间格式转换的相关知识&#xff0c;特别是 Java 时间转换的多种方式&#xff0c;其…...

【用deepseek和chatgpt做算法竞赛】——还得DeepSeek来 -Minimum Cost Trees_5

往期 【用deepseek和chatgpt做算法竞赛】——华为算法精英实战营第十九期-Minimum Cost Trees_0&#xff1a;介绍了题目和背景【用deepseek和chatgpt做算法竞赛】——华为算法精英实战营第十九期-Minimum Cost Trees_1&#xff1a;题目输入的格式说明&#xff0c;选择了邻接表…...

C++ 互斥锁的使用

mutex std::mutex 是C标准库中用于线程同步的互斥锁机制&#xff0c;主要用于保护共享资源&#xff0c;避免多个线程同时访问导致的竞态条件。 它提供了以下功能&#xff1a; 加锁&#xff08;lock&#xff09;&#xff1a;阻塞当前线程&#xff0c;直到获取锁。 解锁&#…...

【Elasticsearch】Retrieve inner hits获取嵌套查询的具体的嵌套文档来源,以及父子文档的来源

Retrieve inner hits 是 Elasticsearch 中的一个功能&#xff0c;用于在嵌套查询或父子查询中&#xff0c;返回导致主文档匹配的具体嵌套对象或子/父文档的详细信息&#xff0c;帮助用户更直观地理解查询结果的来源。 在 Elasticsearch 中&#xff0c;Retrieve inner hits是一…...

C语言中的typedef关键字详解

C语言中的typedef关键字详解 在C语言编程中&#xff0c;typedef 关键字是一个非常实用的特性&#xff0c;它可以帮助我们创建新的类型名&#xff0c;从而简化代码&#xff0c;提高可读性。本文将详细解析typedef的使用方法、场景以及注意事项。 1. typedef简介 typedef 是Ty…...

怎麼利用靜態ISP住宅代理在指紋流覽器中管理社媒帳號?

靜態ISP住宅代理是一種基於真實住宅IP的代理服務。這類代理IP通常由互聯網服務提供商&#xff08;ISP&#xff09;分配&#xff0c;具有非常高的真實性&#xff0c;與普通數據中心代理相比&#xff0c;更不容易被平臺檢測到為“虛假IP”或“代理IP”&#xff0c;靜態ISP住宅代理…...

【多语言生态篇一】【DeepSeek×Java:Spring Boot微服务集成全栈指南 】

(手把手带你从零实现AI能力调用,万字长文预警,建议收藏实操) 一、环境准备:别输在起跑线上 1.1 硬件软件全家桶 JDK版本:必须 ≥17(Spring Boot 3.2+强制要求,低版本直接报错)IDE推荐:IntelliJ IDEA终极版(社区版缺Spring AI插件支持)构建工具:Maven 3.9+ / Grad…...

IOS UITextField 无法隐藏键盘问题

设置UITextField 键盘按钮返回键为“完成”&#xff0c;即return key 设置done .m代码设置代理 //设置代理协议 UITextFieldDelegate&#xff0c; self.mobileTextField.delegate self; ///点击完成键隐藏键盘 - (BOOL)textFieldShouldReturn:(UITextField *)textField{//取…...

einops测试

文章目录 1. einops2. code3. pytorch 1. einops einops 主要是通过爱因斯坦标记法来处理张量矩阵的库&#xff0c;让矩阵处理上非常简单。 conda : conda install conda-forge::einopspython: 2. code import torch import torch.nn as nn import torch.nn.functional as…...

25轻化工程研究生复试面试问题汇总 轻化工程专业知识问题很全! 轻化工程复试全流程攻略 轻化工程考研复试真题汇总

轻化工程复试心里没谱&#xff1f;学姐带你玩转面试准备&#xff01; 是不是总觉得老师会问些刁钻问题&#xff1f;别焦虑&#xff01;其实轻化工程复试套路就那些&#xff0c;看完这篇攻略直接掌握复试通关密码&#xff01;文中有重点面试题可直接背~ 目录 一、这些行为赶紧避…...

小米路由器 AX3000T 降级后无法正常使用,解决办法

问题描述 买了个 AX3000T 路由器&#xff0c;想安装 OpenWRT 或者 安装 Clash 使用&#xff0c;看教程说是需要降级到 v1.0.47 版本。 结果刷机之后路由器无法打开了&#xff0c;一直黄灯亮&#xff0c;中间灭一下&#xff0c;又是黄灯长亮&#xff0c;没有 WIFI 没有连接。以…...

qt5实现表盘的旋转效果,通过提升QLabel类

因为工作需要&#xff0c;需要实现温度的表盘展示效果 实现思路&#xff1a; 通过提示声QLabel控价类&#xff0c;实现报盘的旋转和展示效果 1. 编写一个QLabel的类MyQLabel,实现两个方法 1. void paintEvent(QPaintEvent *event); //重绘函数 2. void valueChanged(int va…...

【HeadFirst系列之HeadFirst设计模式】第7天之命令模式:封装请求,轻松实现解耦!

命令模式&#xff1a;封装请求&#xff0c;轻松实现解耦&#xff01; 大家好&#xff01;今天我们来聊聊设计模式中的命令模式&#xff08;Command Pattern&#xff09;。如果你曾经需要将请求封装成对象&#xff0c;或者希望实现请求的撤销、重做等功能&#xff0c;那么命令模…...

HTTPS(下)

主要讲加密算法RSA&#xff0c;ECDHE TLS的握手涉及四次通信&#xff0c;根据不同的密钥交换算法&#xff0c;TLS 握手流程也会不一样的&#xff0c;现在常用的密钥交换算法有两种&#xff1a;RSA 算法和 ECDHE 算法 正常情况下&#xff0c;需要先TCP三次握手后进行TLS四次握手…...

vue2 和 vue3 中 computer 计算属性的用法

Vue 2 中的 computed 在 Vue 2 中&#xff0c;计算属性是响应式的&#xff0c;并且基于 getter 进行缓存&#xff0c;只有依赖的响应式数据发生变化时才会重新计算。 基本用法 <template><div><p>原始消息&#xff1a;{{ message }}</p><p>反…...

【STM32学习】标准库实现STM32 ADC采集1路、2路、多路

目录 ADC采集 ADC配置步骤 STM32F103C8T6的ADC 输入通道 ​编辑 1路ADC&#xff08;A4 ADC 通道4&#xff09; 1路ADC源码代码链接&#xff1a; 2路ADC&#xff08;A4 ADC 通道4、A5 ADC 通道5&#xff09;基于DMA实现 多路ADC实现采集 ADC采集 ADC配置步骤 使能GPIO…...

【STM32】外部时钟|红外反射光电开关

1.外部时钟 单片机如何对外部触发进行计数&#xff1f;先看一下内部时钟&#xff0c;内部时钟是接在APB1和APB2时钟线上的&#xff0c;APB1,APB2来自stm32单片机内部的脉冲信号&#xff0c;也叫内部时钟。我们用来定时。同样我们可以把外部的信号接入单片机&#xff0c;来对其…...

【语音科学计算器】当前汇率

JSON_MARKER_HORN{“base”:“USD”,“rates”:{“EUR”:0.9758,“JPY”:157.68,“GBP”:0.8190,“CNY”:7.3327,“HKD”:7.7872,“AUD”:1.6260,“CAD”:1.4422,“CHF”:0.9157,“SGD”:1.3714,“KRW”:1473.05,“NZD”:1.7992,“THB”:34.54,“MYR”:4.4930,“PHP”:57.32,“…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

【深度学习新浪潮】什么是credit assignment problem?

Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...

链式法则中 复合函数的推导路径 多变量“信息传递路径”

非常好&#xff0c;我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题&#xff0c;统一使用 二重复合函数&#xff1a; z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y))​ 来全面说明。我们会展示其全微分形式&#xff08;偏导…...

命令行关闭Windows防火墙

命令行关闭Windows防火墙 引言一、防火墙:被低估的"智能安检员"二、优先尝试!90%问题无需关闭防火墙方案1:程序白名单(解决软件误拦截)方案2:开放特定端口(解决网游/开发端口不通)三、命令行极速关闭方案方法一:PowerShell(推荐Win10/11)​方法二:CMD命令…...

UE5 音效系统

一.音效管理 音乐一般都是WAV,创建一个背景音乐类SoudClass,一个音效类SoundClass。所有的音乐都分为这两个类。再创建一个总音乐类&#xff0c;将上述两个作为它的子类。 接着我们创建一个音乐混合类SoundMix&#xff0c;将上述三个类翻入其中&#xff0c;通过它管理每个音乐…...