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

初识数据结构——二叉树从基础概念到实践应用

news 来源：原创 2025/6/10 3:47:20

数据结构专栏 ⬅(click)

初识二叉树：从基础概念到实践应用🌳

一、树型结构基础

1.1 树的基本概念

在这里插入图片描述

树是一种非线性的数据结构，由n(n>0)个有限节点组成一个具有层次关系的集合。它看起来像一棵倒挂的树，根朝上而叶朝下。

关键特点：

有且仅有一个根节点，没有前驱节点
除根节点外，其余节点被分成M(M>0)个互不相交的子树
树是递归定义的

重要术语：

结点的度：一个结点含有子树的个数
树的度：树中所有结点度的最大值
叶子结点：度为0的结点
双亲结点/父结点：含有子结点的结点
孩子结点/子结点：一个结点含有的子树的根结点
根结点：没有双亲结点的结点
结点的层次：从根开始定义，根为第1层
树的高度/深度：树中结点的最大层次

1.2 树的表示方法

最常用的表示方法是孩子兄弟表示法：

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

在这里插入图片描述

二、二叉树详解

2.1 二叉树概念

二叉树是结点的一个有限集合，该集合：

或者为空
或者由一个根节点加上两棵分别称为左子树和右子树的二叉树组成

特点：

二叉树不存在度大于2的结点
二叉树的子树有左右之分，次序不能颠倒，是有序树

2.2 特殊二叉树

满二叉树：每层的结点数都达到最大值。层数为K，结点总数是2^K-1
完全二叉树：深度为K，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应

2.3 二叉树的性质

非空二叉树的第i层最多有2^(i-1)个结点
深度为K的二叉树最大结点数是2^K-1
对于任何二叉树，n0(叶子结点) = n2(度为2的结点) + 1
具有n个结点的完全二叉树深度为⌈log₂(n+1)⌉
完全二叉树的父子结点关系：
- 父结点序号：(i-1)/2
- 左孩子序号：2i+1
- 右孩子序号：2i+2

2.4 二叉树的存储

链式存储

// 孩子表示法
class Node {int val;    // 数据域Node left;  // 左孩子引用，常常代表左孩⼦为根的整棵左⼦树 Node right; // 右孩子引用，常常代表右孩⼦为根的整棵右⼦树 
}// 孩子双亲表示法
class Node {int val;Node left;  // 左孩子引用，常常代表左孩⼦为根的整棵左⼦树 Node right; // 右孩子引用，常常代表右孩⼦为根的整棵右⼦树 Node parent; // 当前节点的根节点
}

三、二叉树遍历

遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做⼀次且仅做⼀次访问。访问结点所做的操作依赖于具体的应⽤问题(比如：打印节点内容、节点内容加1)。遍历是⼆叉树上最重要的操作之一，是二叉树上进行其它运算之基础。
在这里插入图片描述

3.1 递归遍历

(NLR)前序遍历：根节点 -> 左子树 -> 右子树
(LNR)中序遍历：左子树 -> 根节点 -> 右子树
(LRN)后序遍历：左子树 -> 右子树 -> 根节点

// 前序遍历
void preOrder(Node root) {if (root == null) return;System.out.print(root.val + " ");preOrder(root.left);preOrder(root.right);
}// 中序遍历
void inOrder(Node root) {if (root == null) return;inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);
}// 后序遍历
void postOrder(Node root) {if (root == null) return;postOrder(root.left);postOrder(root.right);System.out.print(root.val + " ");
}

3.2 层序遍历

从根节点出发，按层次从上到下、从左到右访问结点。

void levelOrder(Node root) {if (root == null) return;Queue<Node> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {Node cur = queue.poll();System.out.print(cur.val + " ");if (cur.left != null) queue.offer(cur.left);if (cur.right != null) queue.offer(cur.right);}
}

四、二叉树基本操作

代码示例：

// 获取节点个数
int size(Node root) {if (root == null) return 0;return 1 + size(root.left) + size(root.right);
}// 获取叶子节点个数
int getLeafNodeCount(Node root) {if (root == null) return 0;if (root.left == null && root.right == null) return 1;return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}// 获取第k层节点个数
int getKLevelNodeCount(Node root, int k) {if (root == null || k <= 0) return 0;if (k == 1) return 1;return getKLevelNodeCount(root.left, k-1) + getKLevelNodeCount(root.right, k-1);
}// 获取二叉树高度
int getHeight(Node root) {if (root == null) return 0;return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}// 查找值为val的节点
Node find(Node root, int val) {if (root == null) return null;if (root.val == val) return root;Node left = find(root.left, val);if (left != null) return left;return find(root.right, val);
}

结语

二叉树是数据结构中的核心内容，掌握好二叉树对于理解更复杂的数据结构和算法至关重要。建议读者在学习理论的同时，多动手实现代码，解决实际问题，才能真正掌握二叉树的精髓。

在这里插入图片描述

初识数据结构——二叉树从基础概念到实践应用

数据结构专栏 ⬅(click) 初识二叉树：从基础概念到实践应用🌳 一、树型结构基础 1.1 树的基本概念树是一种非线性的数据结构，由n(n>0)个有限节点组成一个具有层次关系的集合。它看起来像一棵倒挂的树，根朝上而叶朝下。关键特…...

编程日记 2025/5/26 6:59:00

手搓传染病模型（SEIR）

先看模型在本模型中，人群有四种自然史状态：易感者(S)，暴露者(E)，感染者(I)以及康复者(R) 2.模型假设人群分布是同质均匀的，未考虑人群出生、死亡、迁入迁出对疾病传播的影响 3.康复者永久免疫：康复者永久免…...

编程日记 2025/6/2 4:57:15

企业数据赋能 | 应用模板分享：汽车销售仪表板

实时监控销售数据，比较车型、地区业绩~ 今天，小编向大家分享 Tableau 应用分析模板：由 Imran Shaikh 搭建的汽车销售仪表板。借助此仪表板，企业可以实时跟踪销售情况，了解市场趋势，并比较不同车型、地区和销…...

编程日记 2025/5/27 15:25:28

C++？动态内存管理！！！

一、引言之前我们一起讨论了类和对象的相关知识，接下来我们将继续完善我们的知识体系，为以后继续深入学习C知识添砖加瓦，在本期我们将一起学习C中关于动态内存管理的相关知识，在学习之前将要先回顾C语言中是如何进行动态内存管理…...

编程日记 2025/5/26 10:45:28

MCP协议：AI生态的统一标准

MCP（Model Context Protocol，模型上下文协议）是人工智能领域的革命性协议标准，被广泛类比为“AI世界的USB-C接口”。它通过统一模型、算力和数据的交互方式，解决了AI生态中的碎片化问题，重构了智能协作的技术范式。以下是其核心解析与技术哲学：一、MCP协议的核心定位与…...

编程日记 2025/5/29 8:56:32

在 UniApp 中实现 App 与 H5 页面的跳转及通信

在移动应用开发中，内嵌 H5 页面或与外部网页交互是常见需求。UniApp 作为跨平台框架，提供了灵活的方式实现 App 与 H5 的跳转和双向通信。本文将详细讲解实现方法，并提供可直接复用的代码示例。文章目录一、 App 内嵌 H5 页面（使…...

编程日记 2025/5/24 18:02:17

AAAI2025 TrackFormer: Multi-Object Tracking with Transformers 论文：https://arxiv.org/abs/2101.02702 代码：https://github.com/timmeinhardt/trackformer AAAI2025 SUTrack 单目标跟踪论文：https://pan.baidu.com/s/10cR4tQt3lSH5V2RNf7-3gg?pwd=pks2 代码：htt…...

编程日记 2025/5/30 10:25:07

Spark RDD行动算子与共享变量实战：从数据聚合到分布式通信

RDD行动算子： 行动算子就是会触发action的算子，触发action的含义就是真正的计算数据。 1、reduce import org.apache.spark.{SparkConf, SparkContext} object value11 { def main(args: Array[String]): Unit { // 创建 SparkConf 对象并设置应用…...

编程日记 2025/5/29 9:40:42

《2025全球机器学习技术大会：阿里云讲师张玉明深度剖析通义灵码AI程序员》

4 月 18 日 - 19 日，由 CSDN & Boolan 联合举办的 2025 全球机器学习技术大会（ML-Summit）于上海顺利举行。大会聚焦人工智能与机器学习前沿技术，汇聚了来自科技与人工智能领域的数位顶尖专家以及数千名开发者和研究者&#xf…...

编程日记 2025/5/24 0:22:48

python+adafruit_pca9685 测试舵机存储当前角度

测试代码如下： # -*- coding: UTF-8 -*- import time from board import SCL, SDA import busio from adafruit_pca9685 import PCA9685 from adafruit_motor import servo 测试控制1块驱动板或者多块 pip install Adafruit-PCA9685 --break-system-packages pip i…...

编程日记 2025/5/29 12:36:11

视觉/深度学习/机器学习相关面经总结（2）（持续更新）

目录 1、跨模态对齐的方案2、位置编码方式1. **正弦和余弦位置编码（Sinusoidal Positional Encoding）**2. **可学习的位置编码（Learnable Positional Encoding）**3. **相对位置编码（Relative Positional Encoding&…...

编程日记 2025/5/27 7:55:47

缓存并发更新的挑战

缓存并发更新的挑战 1. 引言：并发更新的挑战2. 并发场景下的常见“坑”最后写入胜出 (Last-Write-Wins)脏读 (Dirty Read)丢失更新 (Lost Update)不可重复读 (Non-repeatable Read)幻读 (Phantom Read)写偏斜 (Write Skew)缓存与数据库不一致分布式系统中的时序问题…...

编程日记 2025/5/28 17:08:55

LeetCode题解1297. 子串的最大出现次数

（好久没写题解了，忙着学ai去了） 先来看题目很显然，题目就是要我们在给定的字符串中找到一个满足要求的连续子串。首先，要求子串中不同字母的数目得小于等于maxLetters，我们可以用一个DifLettsers函数来…...

编程日记 2025/6/4 6:09:31

零基础小白如何上岸数模国奖

零基础小白如何上岸数模国奖我自己本人第一次参加数模国赛顺利上岸国奖，当然那段经历也是比较痛苦了，差不多也是从当年四月开始接触数学建模，第一次参加妈妈杯成绩并不理想，后面不断参加数模比赛进行模拟，最后顺利上岸…...

编程日记 2025/5/24 0:04:05

Redux-Saga vs Redux-Thunk

Redux-Saga与Redux-Thunk对比 #mermaid-svg-zbDYIbzoVqlMJXiE {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-zbDYIbzoVqlMJXiE .error-icon{fill:#552222;}#mermaid-svg-zbDYIbzoVqlMJXiE .error-text{fill:#55222…...

编程日记 2025/6/1 8:34:25

Win11 配置 Git 绑定 Github 账号的方法与问题汇总

目录一、创建 Github 项目库（远程仓库）二、配置安装好的 Git1. 设置用户信息2. 查看已配置的信息3. 建立本地仓库4. Git 常用命令速查表三、配置 SSH 公钥1. 生成 ssh key出现的问题 2. 启动 ssh-agent 并添加秘钥3. 在 Github 上绑定 ssh 公钥出现的问…...

编程日记 2025/5/29 13:38:13

李臻20242817_安全文件传输系统项目报告_第9周

安全文件传输系统项目报告（第 9 周） 1. 代码链接 Gitee 仓库地址：https://gitee.com/li-zhen1215/homework/tree/master/Secure-file 代码结构说明： project-root/├── src/ # 源代码目录│ ├── main.c # 主程序入口│ ├…...

编程日记 2025/5/29 10:30:02

OceanBase TPCC测试常见报错汇总

OceanBase TPCC测试常见报错汇总报错1：加载测试数据时创建tablegroup失败报错2：加载测试数据时执行超时报错3：加载测试数据时funcs.sh函数找不到报错4：加载数据时报错超过租户内存上限办法一：增加租户内存办法二：调高转储线程数办法三：调整MemStore内存占比和冻结触发阈…...

编程日记 2025/5/26 9:40:59

文心一言开发指南06——千帆大模型平台新手指南

编程日记 2025/4/28 7:28:41

解决SSLError: [SSL: DECRYPTION_FAILED_OR_BAD_RECORD_MAC] decryption faile的问题

问题描述： 在pip安装第三方库时，出现SSL的问题。传输层安全性协议（TLS）及其前身安全套接层（SSL）是现在的 HTTPS 协议中的一种安全协议，目的是为互联网通信提供安全及数据完整性保障。而较新版…...

编程日记 2025/5/26 14:44:24

Clang中ext_vector_type和address_space attribute的使用

Clang中ext_vector_type和address_space __attribute__的使用一.背景二. 关键概念详解三.示例代码与验证四. 总结一.背景在使用 Clang 编译可执行程序时，遇到类似下面的链接错误： undefined reference to atomic_add(int volatile AS4*, int) undef…...

编程日记 2025/5/29 20:31:36

echarts自定义图表

普通柱状图自定义柱状图实现思路 4个图层背景边框实体内部透明地步透明间隙红色柱形数据数据使用自定义字体倾斜柱形上方扁平矩形矩形颜色透明 label字体颜色和背景色相同实现矩形块上下靠padding实现向下 paddingBottom使用负数完整代码 <!DOCTYPE html> <…...

编程日记 2025/5/23 15:23:33

【应用密码学】实验二分组密码（2）

一、实验要求与目的 1） 学习AES密码算法原理 2） 学习AES密码算法编程实现二、实验内容与步骤记录（只记录关键步骤与结果，可截图，但注意排版与图片大小） 字符串加解密运行python程序，输入…...

编程日记 2025/5/27 4:39:02

【深度学习】多头注意力机制的实现|pytorch

博主简介：努力学习的22级计算机科学与技术本科生一枚🌸博主主页： Yaoyao2024往期回顾：【深度学习】注意力机制| 基于“上下文”进行编码,用更聪明的矩阵乘法替代笨重的全连接每日一言🌼: 路漫漫其修远兮，吾…...

编程日记 2025/6/1 11:36:04

OceanBase数据库磁盘空间管理

OceanBase数据库磁盘空间管理日志盘空间管理日志盘容量参数日志盘空间满应急处理数据盘空间管理数据盘容量参数数据文件自动扩展数据盘空间满应急处理表占用的磁盘空间日志盘空间管理日志盘容量参数 🐯 与日志盘redo_dir相关的四个重要参数： log_…...

编程日记 2025/5/29 12:08:46

自然语言处理之机器翻译：Statistical Machine Translation（SMT）的评估方法解析与创新实践

## 机器翻译与评估的重要性机器翻译（Machine Translation, MT）作为自然语言处理（NLP）的核心任务之一，旨在通过计算机实现跨语言的信息传递。随着全球化进程加速，机器翻译在商业、科研、社交等领域的应用愈发广泛。然而，翻译质量直接决定了其实际价值，因此**翻译质量…...

编程日记 2025/5/29 8:51:18

数据集下载（AER 和causaldata R包）

1.AER #install.packages("AER") library(AER)# 引用R包 citation("AER") # 参考文献：Kleiber, Christian, and Achim Zeileis. Applied econometrics with R. Springer Science & Business Media, 2008.# 查看有哪些数据集 data(package …...

编程日记 2025/5/27 6:33:10

【Linux系统】详解Linux权限

文章目录前言一、学习Linux权限的铺垫知识1.Linux的文件分类2.Linux的用户2.1 Linux下用户分类2.2 创建普通用户2.3 切换用户2.4 sudo（提升权限的指令） 二、Linux权限的概念以及修改方法1.权限的概念2.文件访问权限和访问者身份的相关修改&#xff08…...

编程日记 2025/5/29 8:59:03

Go语言--语法基础4--基本数据类型--字符串类型

在 Go 语言中，字符串也是一种基本类型。相比之下， C/C 语言中并不存在原生的字符串类型， 通常使用字符数组来表示，并以字符指针来传递。 Go 语言中字符串的声明和初始化非常简单，举例如下： var str st…...

编程日记 2025/5/28 7:43:10

分布式GPU上计算长向量模的方法

分布式GPU上计算长向量模的方法当向量分布在多个GPU卡上时，计算向量模(2-范数)需要以下步骤： 在每个GPU上计算本地数据的平方和跨GPU通信汇总所有平方和在根GPU上计算总和的平方根实现方法下面是一个完整的CUDA示例代码，使用NCCL进行多…...

编程日记 2025/5/27 8:09:38

项目班——0422——日志

...

编程日记 2025/5/26 13:37:07

【音视频】音频编码实战

FFmpeg流程从本地⽂件读取PCM数据进⾏AAC格式编码，然后将编码后的AAC数据存储到本地⽂件。示例的流程如下所示。关键函数说明： avcodec_find_encoder：根据指定的AVCodecID查找注册的编码器。avcodec_alloc_context3：为AVCod…...

编程日记 2025/6/4 16:08:14

Git Bash 下使用 SSH 连接出现 “Software caused connection abort” 问题

目录一、检查网络环境和防火墙设置（失败）二、尝试使用 GitHub 的备用 SSH 端口 443（成功）三、检查 SSH Key 是否被正确加载四、检查是否多个 SSH 进程干扰或者服务异常五、使用 HTTPS 方式临时解决（非 SSH&#xff09…...

编程日记 2025/5/29 20:39:28

K8S Pod 常见数据存储方案

假设有如下三个节点的 K8S 集群： k8s31master 是控制节点 k8s31node1、k8s31node2 是工作节点容器运行时是 containerd 一、理论介绍 1.1、Volumes 卷 Kubernetes 的卷是 pod 的⼀个组成部分，因此像容器⼀样在 pod 的规范（pod.spec&#x…...

编程日记 2025/5/31 8:15:27

JavaScript 模板字符串：更优雅的字符串处理方式

什么是模板字符串？ 模板字符串（Template Literals）是 ES6（ES2015）引入的一种新的字符串表示方式，它提供了更强大、更灵活的字符串拼接功能。与传统的字符串使用单引号（）或双引号&am…...

编程日记 2025/5/29 10:16:08

DeepSeek智能时空数据分析（五）：基于区域人口数量绘制地图散点-大模型搜集数据NL2SQL加工数据

序言：时空数据分析很有用，但是GIS/时空数据库技术门槛太高时空数据分析在优化业务运营中至关重要，然而，三大挑战仍制约其发展：技术门槛高，需融合GIS理论、SQL开发与时空数据库等多领域知识；空…...

编程日记 2025/5/22 2:15:40

PostSwigger 的 CSRF 漏洞总结

本文所提供的关于 web 安全的相关信息、技术讲解及案例分析等内容，仅用于知识分享与学术交流目的，旨在提升读者对 web 安全领域的认知与理解。以下仅仅是作者对 PostSwigger Web 安全的知识整理和分享，严禁任何非法犯罪活动。限制 CSRF 的三…...

编程日记 2025/5/29 8:46:23

vue项目页面适配

vue项目页面适配目的：结合动态设置根字体大小的脚本（如通过 JavaScript 监听屏幕尺寸变化），实现页面元素在不同设备上的自适应缩放 1、安装postcss-pxtorem ### 若项目未集成 postcss，需同步安装： npm …...

编程日记 2025/6/1 13:08:25

AI-Browser适用于 ChatGPT、Gemini、Claude、DeepSeek、Grok的客户端开源应用程序，集成了 Monaco 编辑器。

一、软件介绍文末提供程序和源码下载学习 AI-Browser适用于 ChatGPT、Gemini、Claude、DeepSeek、Grok、Felo、Cody、JENOVA、Phind、Perplexity、Genspark 和 Google AI Studio 的客户端应用程序，集成了 Monaco 编辑器。使用 Electron 构建的强大桌面应用程序&a…...

编程日记 2025/5/27 6:13:09

Flutter Dart新特性NulI safety late 关键字、空类型声明符?、非空断言!、required 关键字

目录 late 关键字 required关键词: 常用的Model对象使用required Null safety翻译成中文的意思是空安全 null safety 可以帮助开发者避免一些日常开发中很难被发现的错误，并且额外的好处是可以改善性能后的版本都要求使用nul1 safety。Flutter2.2.0(2021年5月19日…...

编程日记 2025/5/25 8:40:25

CF2096G Wonderful Guessing Game 构造

题解首先考虑没有 ? ? ? 回答的时候，答案是多少。猜猜需要多少个询问。 ⌈ log ⁡ 2 n ⌉ ? ⌈ log ⁡ 3 n ⌉ ? \lceil \log_2n\rceil ? \lceil \log_3n\rceil ? ⌈log2n⌉?⌈log3n⌉? 可以构造一个表，行表示不同的询问，…...

编程日记 2025/5/29 9:19:23

制作一款打飞机游戏26：精灵编辑器

虽然我们基本上已经重建了Axel编辑器，但我不想直接使用它。我想创建一个真正适合我们当前目的的编辑器，那就是编辑精灵（sprites）。这将是今天的一个大目标——创建一个基于模板的编辑器，用它作为我们实际编辑器的起点。…...

编程日记 2025/5/28 10:37:02

深入Java JVM常见问题及解决方案

1. 简介 Java虚拟机（JVM）是Java程序运行的核心环境，但其复杂性可能导致内存泄漏、性能下降、类加载失败等问题。本文从内存管理、垃圾回收、性能调优、异常处理四大方向，结合工具使用与实战案例，详解JVM问题的排查与解…...

编程日记 2025/5/24 16:26:53

【MySQL】Java代码操作MySQL数据库 —— JDBC编程

目录 1. Java的JDBC编程 1.1 Java的数据库编程：JDBC 1.2 JDBC工作原理 1.3 如何在项目中导入数据库驱动包如何下载数据库驱动包 jar包如何引入项目中 2. 编写JDBC代码 1. 创建并初始化一个数据源(DataSource) 2. 和数据库服务器建立连接 3. 构造 SQL 语句…...

编程日记 2025/5/29 9:59:51

Marmoset Toolbag 5.0 中文汉化版八猴软件中文汉化版免费下载

八猴安装包下载链接 https://pan.baidu.com/s/1Mgy3Mrlrb3Tvtc8w7Zn1nA?pwd6666 提取码：6666 Marmoset Toolbag是由Monkey公司推出一款专业动画渲染软件，也叫做八猴渲染器。该软件主要特征功能是可以进行实时模型观察、材质编辑和动画预览，…...

编程日记 2025/4/28 7:19:50