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

【Java】二叉树：数据海洋中灯塔式结构探秘（上）

news 来源：原创 2025/8/3 14:18:19

个人主页 🌹：喜欢做梦

二叉树中有一个树，我们可以猜到他和树有关，那我们先了解一下什么是树，在来了解一下二叉树

一🍝、树型结构

1🍨.什么是树型结构？

树是一种非线性的数据结构，它是由n（n>=0）个有限节点（结点）和边组成的层次结构的集合。有一个特定的节点为根节点，其余节点通过边连接形成的分支，每个节点可以有零个或多个子节点。把它叫做树是因为它看起来像一颗倒挂的树，也就是说它是根朝上，而叶朝下的。

什么是线性结构？什么是非线性结构？

线性结构：数据元素呈现一对一的线性关系，除第一个和最后一个元素外，每个元素都有且仅有一个直接前驱和一个直接后继；

非线性结构：数据元素之间的关系不是简单的一对一，一个元素可能有多个前驱或后继，或者两者都有。

树的定义是递归的；
除根节点外的每一个结点都能引出一颗子树；
树型结构中，子树之间不能有交集，否则就不是树型结构；
除了跟节点之外，每个节点有且只有一个父节点；
一个N个节点的树有N-1条边，因为根节点的上方没有边；

2🍩.什么是非树型结构？

非树：节点间的连通性复杂，可能存在多个路径连接统一对节点，也肯存在孤立节点，即与其他节点无连接。

3🍪.树型结构的基本性质

结点的度：一个结点含有子树的个数称为该结点的度；如上图，A的度为3，C的度为2；
树的度：一颗树中，所有结点度的最大值称为结点的度；如上图，树的度为4；
叶子结点或终端结点：度为0的节点称为叶结点；如上图，E、F、G、P等结点为叶节点；
孩子结点或子结点：一个结点含有子树的根结点称为该结点的子结点即只有根节点的结点才是子节点；如上图，B是A的孩子结点；
双亲结点或父亲结点：若一个结点含有子结点，则这个树称为该结点的父结点；如图上A是B的父节点；
根结点：一个树没有双亲的结点；如上图，A；
结点的层次：从根开始定义，根为第一层，根的子结点为第二层，一次类推；
树的高度或深度：树中结点的最大层次；如上图，树的高度为4；
以下只需了解的概念：
非终端结点或分支结点：除根结点外，度不为0的结点；如上图：B、C、D、H为分支节点；
兄弟结点：具有相同父结点的结点互称为兄弟结点；如上图：B、C是兄弟结点；
堂兄弟结点：不具有同一个父结点，但双亲在同一层的结点互为堂兄弟；如上图，G和H；
结点的祖先：从根到该结点所经分支的所有结点；如上图，A就是所有结点的祖先；
子孙：以某结点为根的子树中的任一节点，都称为该结点的子孙。如上图，所有结点都是A的子孙；
森林：有m（m>=0）课互不相交的树组成的集合称为森林；

4🍨.树的表现形式（了解）

树的表现形式有很多种，如双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。这里简单了解一下其中最常见的方法就是孩子兄弟表示法：

class Node{public int value;//数据public Node firstChild;//第一个孩子public Node nextBrother;//下一个兄弟
}

二🍝、二叉树

1🍑.什么是二叉树？

二叉树：二叉树是每个结点最多有两科子树的树的结构，其两个子树通常称为左子树和右子树。

二叉树的递归定义：

或者是一颗空树；
或者是一颗由一根结点和两课互不相交的分别称为左子树和右子树所组成的非空数，左子树和右子树又同样是二叉树；

特点：

度的限制：结点的度最大为2；
有序性：左右子树由顺序，即使某节点只有一颗子树，也要区分左右子树；

性质：

若规定的根节点层数为1，这一棵非空二叉树的第i层上最多有 $2^{i-1}$ （i>.0）个节点；
若规定只有根节点的二叉树的深度为1，则深度为k的二叉树的最大节点数是 $2^{k}-1$ （k>=0）;
对于任何一棵二叉树，如果其叶节点个数为n0，度为2的非叶节点个数为n2，则有n0=n2+1；

2🍑.二叉树的类型

1.满二叉树

满二叉树：每一层的结点树都达到最大，除最后一层外每个节点都有两个节点。

特点：

节点度数：除最后一层的叶子节点外，其他层的每一个的节点都有两个节点，即度都为2；
叶子节点：所有的叶子节点都在同一层，且叶子节点的数量为 $2^{k-1}$ ，k为数的高度；
节点总数：节点总数是 $2^{k}-1$ ；

2.完美二叉树

完美二叉树：除最后一层外，其余层节点数都达到最大，最后一层节点从左到右依次按顺序排列，可通过数组的高效和访问，完美二叉树是满二叉树的一种。

特点：

节点度数：除了底层的叶子节点外，其余所有节点都有两个子节点，即度数均为2；
叶子节点分布：所有叶子节点都在同一层，这使得树的结构呈现出完美的形态；
具有n个节点的完全二叉树的深度k为 $\log_{2}$ (n+1)上取整进1；
节点数量：对于具有n个节点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，这对于序号为i的节点有：

若i>0,双亲序号：（i-1）/2;i=0,i为根节点的编号，无双亲节点；
若2i+1<n,左孩子序号:2i+1,否则无左孩子；
若2i+1<n,右孩子序号：2i+2，否则无右孩子；

3🍪.二叉树的创建

public class BinaryTree {public 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');//连接节点A.left=B;A.right=C;B.left=D;B.right=E;C.left=F;C.right=G;return A;}
}

4.二叉树的遍历

二叉树的遍历是指按照一定的顺序访问二叉树中的每个节点，且每个节点仅被访问一次。

二叉树的遍历方式主要有前序遍历、中序遍历、后序遍历；

前序遍历

前序遍历：遍历顺序是先访问根的的节点—>左子树—>右子树，也就是根、左、右；

前序遍历代码：

// 前序遍历public void preOrder(TreeNode root){//判断是否有节点,没有返回if(root == null){return;}System.out.print(root.val+ " ");//遍历左子树preOrder(root.left);//遍历右子树preOrder(root.right);}

顺序：根节点--左子树--右子树；
根结点的打印位置：第一个；

中序遍历

中序遍历：遍历顺序是先访问左子树—>根的的节点—>右子树，也就是左、根、右；

中序遍历代码：

 // 中序遍历public void inOrder(TreeNode root){//判断是否有节点,没有返回if(root == null){return;}//遍历左子树preOrder(root.left);System.out.print(root.val+ " ");//遍历右子树preOrder(root.right);}

顺序：左子树--根节点--右子树；
根结点的打印位置：中间；

后序遍历

后序遍历：遍历顺序是先访问左子树—>右子树—>根的的节点，也就是左、根、右；

    // 后序遍历public void postOrder(TreeNode root){//判断是否有节点,没有返回if(root == null){return;}//遍历左子树preOrder(root.left);//遍历右子树preOrder(root.right);System.out.print(root.val+ " ");}
}

后序遍历的过程与前面的也是同理，就不画图过多解释了。

顺序：左子树--右子树--根节点；
根结点的打印位置：最后一个；

三者之间的区别：

	前序遍历	中序遍历	后序遍历
访问顺序	根、左、右	左、根、右	左、右、根
根节点访问位置	第一个	中间	最后一个
应用场景	二叉树结构、将表达式树转换为前缀表达式	用于输出有序序列，还能辅助将表达式树转换为中缀表达式	二叉树的高度、节点数，以及释放二叉树内存

层序遍历

层序遍历：从上至下，从左至右逐层访问就是层序遍历。

层序遍历的代码，我后期补上，或者下篇在写，这篇就到这里啦~

【Java】二叉树：数据海洋中灯塔式结构探秘（上）

个人主页 🌹：喜欢做梦二叉树中有一个树，我们可以猜到他和树有关，那我们先了解一下什么是树，在来了解一下二叉树一🍝、树型结构 1🍨.什么是树型结构？ 树是一种非线性的数据结构&…...

编程日记 2025/8/3 14:18:19

海洋通信船舶组网工业4G路由器应用

船舶是浩瀚海洋中探索与贸易的载体，更是船员们生活与工作的家园。为了在广阔的水域中搭建起稳定、高效的网络桥梁，工业4G路由器以卓越的通信组网能力，为船舶组网提供网络支持。工业4G路由器以其强大的信号发射能力，确保船舶内部…...

编程日记 2025/8/3 14:18:19

字符串-07-判断两个IP是否属于同一子网

文章目录 1. 题目描述2. 思路3. 代码 1. 题目描述 IP地址是由4个0-255之间的整数构成的，用"."符号相连。二进制的IP地址格式有32位，例如：10000011，01101011，00000011，00011000；每八…...

编程日记 2025/8/1 4:52:29

Django启用国际化支持（2）—实现界面内切换语言：activate()

文章目录 ⭐注意⭐1. 配置项目全局设置：启用国际化2. 编写视图函数3. 配置路由4. 界面演示5、扩展自动识别并切换到当前语言设置语言并保存到Session设置语言并保存到 Cookie ⭐注意⭐ 以下操作依赖于 Django 项目的国际化支持。如果你不清楚如何启用国际化功能&am…...

编程日记 2025/8/2 15:22:45

自定义协议

1. 问题引入问题：TCP是面向字节流的（TCP不关心发送的数据是消息、文件还是其他任何类型的数据。它简单地将所有数据视为一个字节序列，即字节流。这意味着TCP不会对发送的数据进行任何特定的边界划分，它只是确保数据的顺序和完整…...

编程日记 2025/7/28 4:14:10

PHP Date 函数：日期和时间处理的全指南

PHP Date 函数：日期和时间处理的全指南 PHP Date 函数是 PHP 编程语言中用于处理日期和时间的核心函数之一。它提供了强大的功能，允许开发者轻松地格式化、计算和操作日期和时间值。本文将详细介绍 PHP Date 函数的用法，包括基本格式化、时间戳处理、时区设置以及一些高级特…...

编程日记 2025/7/30 5:13:32

C++设计模式：抽象工厂模式（风格切换案例）

抽象工厂模式（Abstract Factory）是一种创建型设计模式，其核心思想是：为一组相关或相互依赖的对象提供一个创建接口，而无需指定它们具体的类。简单来说，就是一个工厂可以生产一系列相关的对象。我们接下来…...

编程日记 2025/8/2 0:40:03

社交媒体营销新趋势：如何通过海外平台提升品牌曝光度？

社交媒体不仅是简单的信息传播工具，更是连接用户与品牌之间的重要纽带。每天，有数以亿计的全球用户在不同平台上活跃，潜藏着巨大的市场潜力。对于企业来说，关键在于制定清晰的营销策略，精准把握不同社交平台的特性&…...

编程日记 2025/8/3 0:03:28

#1 kcx.c:112:89: error: format specifies type unsigned int but the argument has type u32 * (aka unsigned int *) [-Werror,-Wformat] 报错原因： int kcx(u32 *trigger) { ERR_MSG("%s:failed. attr%d, trigger%u\n", __func__, attr_enable, trig…...

编程日记 2025/7/31 15:01:18

laravel 5.5 增加宏指令 joinSub, 省去-＞toSql() 和 addBinding($bindings)；

laravel 5.5 增加宏指令 joinSub, 省去->toSql() 和 addBinding($bindings); 1. 在laravel5使用join 子查询时 $sub_query DB::table(table1)->select([table1.id, cate_id])->join(table2, table1.id, , table2.id)->where(table1.cate_id, 2)->orderBy(tabl…...

编程日记 2025/7/30 13:13:59

知识库搭建：大健康产业数字化转型的新引擎

随着数字经济的蓬勃发展，大健康产业正步入一个崭新的发展篇章。消费者对于健康的追求日益增长，促使大健康企业积极探索数字化路径，以提升供应链效率、控制成本，并在激烈的市场竞争中脱颖而出。在此过程中，一系列数字化…...

编程日记 2025/8/2 17:05:50

创建可重用React组件的实用指南

尽管React是全球最受欢迎和使用最广泛的前端框架之一，但许多开发者在重构代码以提高可复用性时仍然感到困难。如果你发现自己在React应用中不断重复相同的代码片段，那你来对地方了。在本教程中，将向你介绍三个最常见的特征，表明是…...

编程日记 2025/7/27 7:55:13

蓝桥杯每日真题 - 第18天

题目：（出差） 题目描述（13届 C&C B组E题） 解题思路： 问题分析问题实质是一个带权图的最短路径问题，但路径的权重包含两个部分： 从当前城市到下一个城市的路程时间。当前城市的…...

编程日记 2025/7/5 1:54:06

MySQL中索引全详解

第一部分：什么是索引索引在数据库中就像书的目录，能够快速定位数据位置，从而提升查询效率。没有索引时，数据库查询需要从头到尾扫描整个表（称为全表扫描），这在数据量大时非常耗时。有了索引后&…...

编程日记 2025/8/3 9:39:52

探索复合物TPP-PEG-Heparin的特性；磷酸三苯酯-聚乙二醇-肝素的线粒体靶向性

TPP-PEG-Heparin，即磷酸三苯酯（TPP）、聚乙二醇（PEG）和肝素（Heparin）的复合物，其特性融合了这三种成分的性质。一、线粒体靶向性 TPP部分：具有线粒体靶向功能&#xf…...

编程日记 2025/8/2 18:16:44

ubuntu 配置多个 git 客户端账户

Git配置两个或多个账户 https://blog.csdn.net/mainking2003/article/details/134711865 git 提交不用输入用户名、密码的方法（GIT免密提交） https://blog.csdn.net/wowocpp/article/details/125797263 git config 用法 https://blog.csdn.net/blueb…...

编程日记 2025/7/29 23:40:01

Web3与智能合约：区块链技术下的数字信任体系

随着互联网的不断发展，Web3代表着我们迈入了一个去中心化、更加安全和智能的网络时代。作为Web3的核心组成部分，区块链技术为智能合约的出现和发展提供了强有力的基础。智能合约不仅仅是自动化的代码，它们正逐步成为重塑数字世界信任体系的关…...

编程日记 2025/8/1 5:04:36

RocketMQ文件刷盘机制深度解析与Java模拟实现

引言在现代分布式系统中，消息队列（Message Queue, MQ）作为一种重要的中间件，扮演着连接不同服务、实现异步通信和消息解耦的关键角色。Apache RocketMQ作为一款高性能的分布式消息中间件，广泛应用于实时数据流处理、…...

编程日记 2025/7/30 22:11:16

高级编程之结构化代码

背景：以下没结构化代码之前，定时器同步店铺信息的代码。结构化的思想：SRP（单一职责），一个方法是做一件事，层次是相关的，逻辑和数据操作进行拆分，数据操作从业务流程上定…...

编程日记 2025/8/1 8:55:46

学习编程，学习中间件，学习源码的思路

01 看的多，内化不足最近想复习一下编程相关的知识，在复习前我翻开了之前的一些笔记，这些笔记基本都是从书本、视频、博客等摘取记录的，看着这些笔记心里总结：看的多，内化不足。 02 整理大纲为了解决这个…...

编程日记 2025/7/31 18:27:56

网络安全与加密

1.Base64简单说明描述：Base64可以成为密码学的基石，非常重要。特点：可以将任意的二进制数据进行Base64编码结果：所有的数据都能被编码为并只用65个字符就能表示的文本文件。65字符：A~Z a~z 0~9 / 对文件进行base64编码…...

编程日记 2025/8/2 13:16:32

开源协议介绍

文章目录 1. MIT License2. Apache License 2.03. GNU General Public License (GPL)4. GNU Lesser General Public License (LGPL)5. BSD License6. Mozilla Public License (MPL)7. Creative Commons Licenses (CC)8. Unlicense选择建议在开源平台上，开源项目通…...

编程日记 2025/7/30 10:08:31

Java技术复习提升 10异常

10 异常 10.1异常介绍及分类异常捕获选中后alttabt->选中try-catch 异常就是程序执行中不正常的情况注意语法和逻辑错误并不是异常异常分类有两种 error和exception error是错误虚拟机无法解决的严重问题 exception是其他因为编程错误或者外在因素导致的一般性的问…...

编程日记 2025/7/31 13:52:43

java版工程项目管理系统源码：Spring Cloud与前后端分离的完美结合

在现代化的工程项目管理中，一套功能全面、操作便捷的系统至关重要。本文将介绍一个基于Spring Cloud和Spring Boot技术的Java版工程项目管理系统，结合Vue和ElementUI实现前后端分离。该系统涵盖了项目管理、合同管理、预警管理、竣工管理、质量管理等多个…...

编程日记 2025/7/31 2:04:12

Oracle与MySQL中CONCAT()函数的使用差异

一、CONCAT函数介绍 CONCAT函数是MySQL等数据库中用于连接两个或多个字符串的内置函数。其基本语法如下： CONCAT(string1, string2, ...)参数说明： string1, string2, …：需要连接的字符串参数，可以有多个。返回值&#xff1…...

编程日记 2025/7/30 9:28:26

AI社媒引流工具：解锁智能化营销的新未来

在数字化浪潮的推动下，社交媒体成为品牌营销的主战场。然而，面对海量的用户数据和日益复杂的运营需求，传统营销方法显得力不从心。AI社媒引流王应运而生，帮助企业在多平台中精准触达目标用户，提升营销效率和效果。 1.…...

编程日记 2025/7/31 23:56:36

浏览器的事件循环机制

一、请简述浏览器的事件循环机制（Event Loop）基本原理浏览器的事件循环机制是用于协调处理 JavaScript 中的异步任务与同步任务执行顺序的一种机制，它确保了代码能够按照合理的顺序执行，避免阻塞页面渲染等情况。其基本原理如下…...

编程日记 2025/8/2 23:04:06

如何在 React 项目中应用 TypeScript？应该注意那些点？结合实际项目示例及代码进行讲解！

在 React 项目中应用 TypeScript 是提升开发效率、增强代码可维护性和可读性的好方法。TypeScript 提供了静态类型检查、自动补全和代码提示等功能，这对于 React 开发者来说，能够帮助早期发现潜在的 bug，提高开发体验。 1. 项目初始化在现…...

编程日记 2025/7/29 12:04:01

排序算法(五)--归并排序

文章目录引言归并排序概述C语言实现代码解析结论归并排序 C语言实例引言归并排序（Merge Sort）作为一种经典的排序算法，以其稳定性、分治法的巧妙应用以及相对高效的时间复杂度而著称。归并排序概述归并排序采用分治法（Di…...

编程日记 2025/8/1 1:28:56

Linux KASLR 地址偏移

kaslr开启时地址 cat /proc/cmdline BOOT_IMAGE/boot/vmlinuz-5.4.0-193-generic rootUUID0e46dee3-4557-434a-a2d2-a35c6ad3d327 ro find_preseed/preseed.cfg auto noprompt prioritycritical localeen_US quiet cat /boot/config-$(uname -r) | grep CONFIG_RANDOMIZE_B…...

编程日记 2025/8/1 18:02:33