当前位置: 首页 > 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,“…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...