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

【Python 数据结构 9.树】

news 来源：原创 2025/8/27 21:46:07

我装作漠视一切，其实我在乎的太多，但我知道抓得越紧越容易失去

—— 25.3.6

一、树的基本概念

1.树的定义

树是n个结点的有限集合，n=0时为空树。当n大于0的时候，满足如下两个条件：

① 有且仅有一个特定的结点，称为根结点 Root；

② 当 n > 1 时，其余结点分为 m 个互不相交的有限集合，T1、T2、T3、….Tm，其中每个 Ti 又是一棵树，并且为 Root 的子树；

2.子树的定义

树的定义用到了递归的思想。即树的定义中，还用到了树的概念。

T1 和 T2 就是 a 的子树，结点 d、9、h、i 组成的树又是结点 b 的子树

子树的个数没有限制，但是它们一定是互不相交的

3.结点的定义

树的结点包含一个数据域和 m 个指针域，指针域用来指向它的子树。结点的分类为：根结点、叶子结点、内部结点。结点拥有子树的个数，被称为结点的度，树中各个结点度的最大值，被称为树的度。

1) 根结点

一棵树的根结点只有一个

2) 叶子结点

度为 0 的结点被称为叶子结点，叶子结点不能指向任何子树

3) 内部结点

除了根结点和叶子结点以外的结点，都被称为内部结点

4.结点的关系

1) 孩子结点

对于某个结点，它的子树的根结点被称为该结点的孩子结点

2) 父节点

该结点被称为孩子结点的父结点

3) 兄弟结点

同一父结点下的孩子结点互相称为兄弟结点

5.树的深度

结点的层次，从根结点开始记为第 1 层，如果某个结点在第 i 层，则它的子树的根结点在第 i+1 层。树中结点的最大层次称为树的深度，如图所示，是一棵深度为 4 的树。

6.森林的定义

森林是 m 棵互不相交的树的集合。对于树的每个结点而言，其子树集合就是森林，如图所示，b 和 c 两棵子树组成的集合就是一个森林。

二、树的数据结构表示

1.结点 id

为了方便树数据的读取和修改，我们一般用一个数字来代表树的结点，这个数字就是树的结点 id，它是一个唯一 id，每个树结点的结点 id 都是不同的。如图所示，每个结点都有一个 id 作为标识。

2.结点池

在处理树相关的问题时，结点一定是有限的，有时候也一定是确定的，比如一个问题给出的时候，给出一个 n 个结点的树，这个 n 必然是有上限的，所以我们可以事先将所有的结点存储在一个顺序表中，然后通过结点id 索引的方式，快速获取到对应的结点。而这个顺序表就是结点池。所以，根据结点 id 获取结点的这步操作，时间复杂度是 O(1)的。

3.结点数据

树的结点数据可以是任意的，这样就可以处理任何情况下的问题，如图所示，树结点的数据的类型是字符类型(a、b、c、d、e、f、g、h、i)。

4.孩子结点列表

每个结点都要保存一个孩子结点列表(叶子结点的孩子结点列表是空的)，注意这里所说的是列表，不是顺序表也不是链表，当然也不是特指 Python 中的 list，而指的就是自然语义上的列表，我们可以用顺序表来实现对孩子结点的存储，也可以用链表来实现对孩子结点的存储。

5.添加树边

如图所示，两个绿色的箭头，分别代表的就是添加两条边的过程。添加树边（a -> b、a -> c )的过程，可以通过树的结点 id 先获取到实际的树结点，然后将孩子结点添加到父结点的孩子结点列表来完成。

6.树的遍历

树的遍历的引入，让我们开始了解递归的概念，而树本身也是一种递归的数据结构

三、Python中的树

用Python实现下图的树，并用深度遍历的方式将其打印出来

代码实现

Ⅰ、树的结点类定义

树节点的基本结构：树是一种分层数据结构，每个节点可以有零个或多个子节点。TreeNode 类通过 val 属性存储节点的值，并通过 childrenList 属性维护子节点的列表。

动态添加子节点：addChild 方法允许在树结构中动态添加子节点，使得树可以根据需要扩展。

通用性：val 属性初始为 None，使得节点可以存储任意类型的值（如整数、字符串、对象等），增加了代码的通用性。

append()：Python 中列表（list）对象的一个内置方法，用于在列表的末尾添加一个元素。该方法会直接修改原列表，而不是返回一个新的列表。

参数	类型	作用
`object`	任意类型	要添加到列表末尾的元素。可以是数字、字符串、列表、字典等任何 Python 对象。

class TreeNode:def __init__(self):self.val = Noneself.childrenList = []def addChild(self, node):self.childrenList.append(node)

Ⅱ、树结构初始化

列表推导式：用于从一个可迭代对象（如列表、元组、字符串等）中快速生成一个新的列表。它可以将复杂的循环和条件判断合并为一行代码，使代码更加简洁和高效。

参数	作用
`expression`	对`item`执行的操作或表达式，生成新列表中的元素。
`item`	从`iterable`中遍历的每一个元素。
`iterable`	可迭代对象（如列表、元组、字符串等）。
`condition`	可选的条件语句，用于筛选要包含在新列表中的元素。

range()：用于生成一个不可变的数字序列，通常用于循环控制或生成数字列表。它可以根据指定的起始值、结束值和步长生成一系列数字。

参数	作用
`start`	序列的起始值（包含），默认为0。
`stop`	序列的结束值（不包含）。
`step`	步长，默认为1。如果为负数，则生成递减的序列。

class Tree:def __init__(self, maxNodes):self.root = Noneself.nodes = [TreeNode() for i in range(maxNodes)]

Ⅲ、根据索引获取树节点

根据给定的索引 index，从 self.nodes 列表中获取对应的树节点

    def getTreeNode(self, index):return self.nodes[index]

Ⅳ、设置根结点

调用 getTreeNode(rootIndex) 获取索引为 rootIndex 的节点，并将其赋值给 self.root，从而将该节点设置为树的根节点。

    def setRoot(self, rootIndex):self.root = self.getTreeNode(rootIndex)

Ⅴ、添加孩子结点

首先通过 getTreeNode(parentIndex) 获取父节点，然后通过 getTreeNode(childIndex) 获取子节点，最后调用父节点的 addChild 方法将子节点添加到父节点的子节点列表中

    def addChild(self, parentIndex, childIndex):parent = self.getTreeNode(parentIndex)child = self.getTreeNode(childIndex)parent.addChild(child)

Ⅵ、给指定索引结点赋值

通过 getTreeNode(index) 获取索引为 index 的节点，并将其 val 属性设置为 val

    def AssignData(self, index, val):self.getTreeNode(index).val = val

Ⅶ、打印树结构

如果 node 为 None，则从根节点 self.root 开始打印。首先打印当前节点的值 node.val，然后递归地遍历并打印每个子节点的值。node.childrenList 是当前节点的子节点列表

    def PrintTree(self,node = None):if node is None:node = self.rootprint(node.val,end=" ")for child in node.childrenList:self.PrintTree(child)

Ⅷ、 Python中树的实现

class TreeNode:def __init__(self):self.val = Noneself.childrenList = []def addChild(self, node):self.childrenList.append(node)class Tree:def __init__(self, maxNodes):self.root = Noneself.nodes = [TreeNode() for i in range(maxNodes)]def getTreeNode(self, index):return self.nodes[index]def setRoot(self, rootIndex):self.root = self.getTreeNode(rootIndex)def addChild(self, parentIndex, childIndex):parent = self.getTreeNode(parentIndex)child = self.getTreeNode(childIndex)parent.addChild(child)def AssignData(self, index, val):self.getTreeNode(index).val = valdef PrintTree(self,node = None):if node is None:node = self.rootprint(node.val,end=" ")for child in node.childrenList:self.PrintTree(child)def test():T = Tree(9)T.setRoot(0)T.AssignData(0,'a')T.AssignData(1,'b')T.AssignData(2,'c')T.AssignData(3,'d')T.AssignData(4,'e')T.AssignData(5,'f')T.AssignData(6,'g')T.AssignData(7,'h')T.AssignData(8,'i')T.addChild(0,1)T.addChild(0,2)T.addChild(1,3)T.addChild(2,4)T.addChild(2,5)T.addChild(3,6)T.addChild(3,7)T.addChild(3,8)T.PrintTree()test()

四、实战

1.2236. 判断根结点是否等于子结点之和

给你一个 二叉树 的根结点 root，该二叉树由恰好 3 个结点组成：根结点、左子结点和右子结点。

如果根结点值等于两个子结点值之和，返回 true ，否则返回 false 。

示例 1：
输入：root = [10,4,6]
输出：true
解释：根结点、左子结点和右子结点的值分别是 10 、4 和 6 。
由于 10 等于 4 + 6 ，因此返回 true 。
示例 2：
输入：root = [5,3,1]
输出：false
解释：根结点、左子结点和右子结点的值分别是 5 、3 和 1 。
由于 5 不等于 3 + 1 ，因此返回 false 。
提示：

树只包含根结点、左子结点和右子结点
-100 <= Node.val <= 100

方法一、直接判断是否相等

思路与算法

核心逻辑：直接比较根节点的值 root.val 与其左右子节点值之和 root.left.val + root.right.val，若相等则返回 True，否则返回 False。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def checkTree(self, root: Optional[TreeNode]) -> bool:if root == None:return Falsereturn root.val == root.left.val + root.right.val

2.104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：
输入：root = [1,null,2]
输出：2
提示：

树中节点的数量在 [0, 104] 区间内。
-100 <= Node.val <= 100

方法一递归

思路与算法

递归终止条件：如果当前节点 root 为 None，表示已经遍历到了叶子节点的下一层，返回深度 0。

递归计算左右子树的深度：分别递归计算左子树和右子树的最大深度，分别存储在 left 和 right 中。

返回当前树的最大深度：当前树的最大深度为左右子树深度的较大值加 1（加 1 表示当前层）。

max()： 返回一组数值中的最大值。它可以用于多种编程语言和工具中，如Python、Excel、MATLAB等。

参数	作用
`number1`, `number2`, ...	必需，表示要比较的数值或数值范围。在Excel中，最多可包含255个参数 4 。
`iterable`	在Python中，表示可迭代对象（如列表、元组等），函数将返回该对象中的最大值 5 。
`key`	在Python中，可选参数，用于指定一个函数作为比较的标准。例如，可以使用`key=lambda x: abs(x)`来比较绝对值 5 。
`default`	在Python中，可选参数，当可迭代对象为空时，返回此默认值 5 。
`dim`	在MATLAB中，可选参数，用于指定在矩阵的哪一维上查找最大值 1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if root == None:return 0left = self.maxDepth(root.left)right = self.maxDepth(root.right)return max(left, right) + 1

方法二、先序遍历 + 递归

思路与算法

dfs 方法：这是一个递归方法，用于遍历二叉树的每个节点。

参数 root 是当前节点，depth 是当前节点的深度。

如果当前深度 depth 大于 self.max，则更新 self.max 为当前深度。

如果当前节点 root 不为空，则递归调用 dfs 方法遍历其左子树和右子树，并将深度 depth 加 1。

calculateDepth 方法：这是主方法，用于计算二叉树的最大深度。

首先初始化 self.max 为 0，表示当前最大深度。然后调用 dfs 方法，从根节点开始遍历，初始深度为 0。最后返回 self.max，即二叉树的最大深度。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def dfs(self, root:Optional[TreeNode], depth:int) -> None:if depth > self.max:self.max = depthif root:self.dfs(root.left, depth + 1)self.dfs(root.right, depth + 1)def calculateDepth(self, root: Optional[TreeNode]) -> int:self.max = 0self.dfs(root, 0)return self.max

五、树的应用

在信息量非常大的情况下，需要快速将信息分类，就可以用到树这种数据结构

【Python 数据结构 9.树】

我装作漠视一切，其实我在乎的太多，但我知道抓得越紧越容易失去 —— 25.3.6 一、树的基本概念 1.树的定义树是n个结点的有限集合，n0时为空树。当n大于0的时候，满足如下两个条件： ① 有且仅有一个特定的结点&#xff…...

编程日记 2025/8/27 21:46:07

美团校招实习笔试历年真题与内推

美团第一场笔试时间在本周六晚19:00开启想知道笔试考什么？来刷刷历年真题 👉点击https://my5353.com/Bo1c1历年真题开刷！ −−−−−−−−−−−−−−−−−−−−−− 1⃣【26届转正实习】70%转正留用，提前锁定正式offer&…...

编程日记 2025/8/27 21:38:52

redis的淘汰策略

Redis 的淘汰策略（Eviction Policy）是指当 Redis 内存不足时，如何选择删除哪些数据来腾出空间。以下是 Redis 支持的几种淘汰策略，用通俗的话解释它们的特点： 1. noeviction（不淘汰） 特点&#…...

编程日记 2025/8/27 21:45:09

Linux中的TCP编程接口基本使用

TCP编程接口基本使用本篇介绍在UDP编程接口基本使用已经介绍过UDP编程相关的接口，本篇开始介绍TCP编程相关的接口。有了UDP编程的基础，理解TCP相关的接口会更加容易，下面将按照两个方向使用TCP编程接口： 基本使用TCP编程接口…...

编程日记 2025/8/27 16:39:24

javaweb：Maven、SpringBoot快速入门、HTTP协议

Maven Maven作用介绍 Maven的坐标依赖配置依赖传递排除依赖依赖范围生命周期 clean：清除编译文件 compile：生成编译文件 test：执行所有的单元测试方法（在pom.xml引入Junit单元测试依赖） package：…...

编程日记 2025/8/26 8:00:59

macOS常用网络管理配置命令

目录 **1. ifconfig：查看和配置网络接口****2. networksetup：管理系统网络配置****3. ping：测试网络连通性****4. traceroute：跟踪数据包路径****5. nslookup/dig：DNS 查询****6. netstat：查看网络连接和统…...

编程日记 2025/8/27 21:39:50

IntelliJ IDEA 中配置 Groovy

在 IntelliJ IDEA 中配置 Groovy 环境可以分为以下几个步骤 1. 安装 Groovy 插件步骤： 打开 IntelliJ IDEA，进入菜单栏：File → Settings（Windows/Linux）或 IntelliJ IDEA → Preferences（Mac&#xff0…...

编程日记 2025/8/27 21:38:53

如何实现区域灰质体积、皮层厚度、低频振幅等影像学特征的病例-对照分析差异分析

在神经影像学研究中，病例-对照分析（case-control analysis）是一种常见的方法，用于比较患者组（cases）与健康对照组（controls）在脑结构和功能上的差异。本文介绍如何利用病例-对照分析…...

编程日记 2025/8/27 12:34:50

WordPress报502错误问题解决-php-fpm-84.service loaded failed failed LSB: starts php-fpm

文章目录问题描述问题排查问题解决问题描述服务器环境： php：8.4MySQL：8.0Nginx：1.26.2 在访问站点时，一直报502，而两天前还能正常访问。问题排查导致502的问题很多，比如站点访问量太大…...

编程日记 2025/8/27 21:39:50

2025上软考下周开启报名！附报考流程和常见问题解答

报名时间 ：3月10日开始报名（以当地报名时间为准） 考试时间 ：2025年5月24日~27日（具体时间以准考证为准） 报名网址 ：中国计算机技术职业资格网(https://bm.ruankao.org.cn/sign/welcome) 目前已…...

编程日记 2025/8/27 21:42:01

Process-based Self-Rewarding Language Models 论文简介

基于过程的自奖励语言模型：LLM优化的新范式引言大型语言模型（LLM）在多种任务中展现出了强大的能力，尤其是在使用人工标注的偏好数据进行训练时。然而，传统的自奖励范式在数学推理任务中存在局限性，甚至…...

编程日记 2025/8/24 1:24:42

Kotlin字符串操作在Android开发中的应用示例

Kotlin字符串操作在Android开发中的应用示例引言在Android开发中，Kotlin已经成为主流的编程语言，它提供了许多便捷的字符串操作功能。本文将结合一个具体的Kotlin示例程序，详细介绍Kotlin中字符串的创建、格式化和使用方法。示例代码以…...

编程日记 2025/8/27 21:42:01

自律 linux 第 36 天

昨天学习IO多路复用的时候使用的是select函数接口， select需要在应用层建立一个放套接字的表，然后传入内核中，再又内核将响应的套接字表传回应用层，这样耗费时间和资源，而且这个表只能存放最多1024个套接字&#xff0c…...

编程日记 2025/8/27 21:44:20

《从零开始构建视频同步字幕播放软件》

《从零开始构建视频同步字幕播放软件》字幕软件：数字时代的 “语言桥梁” 在全球化进程不断加速的今天，我们正处于一个信息爆炸且多元文化交融的时代。电影、剧集、公开课、短视频等各类视频内容，跨越了地域与国界的限制，在互联…...

编程日记 2025/8/27 21:37:57

VirtualBox虚拟机安装Mac OS启动后的系统设置

VirtualBox虚拟机安装Mac OS一直没装成功，本来想要放弃的，后来想着再试一次，于是在关机的情况，执行那几句设置： cd "E:\Program Files\Oracle\VirtualBox\" VBoxManage.exe modifyvm "MacOS" --c…...

编程日记 2025/8/27 21:37:53

JDK17下载安装 mkdir -p /usr/local/develop cd /usr/local/develop 将下载的包上传服务器指定路径解压文件 tar -zxvf jdk-17.0.14_linux-x64_bin.tar.gz -C /usr/local/develop/ 修改文件夹名 mv /usr/local/develop/jdk-17.0.14 /usr/local/develop/java17 配置环境变量…...

编程日记 2025/8/27 13:24:19

测试用例详解

一、通用测试用例八要素　 1、用例编号； 　　 2、测试项目； 　 3、测试标题； 4、重要级别； 　　 5、预置条件； 　　 6、测试输入； 　　 7、操作步骤； 　　 8、预期输出二、具体分析通…...

编程日记 2025/8/27 21:42:02

深入解析 dig 命令：DNS 查询与故障排除利器

文章目录深入解析 dig 命令：DNS 查询与故障排除利器简介dig 命令简介适用范围基本语法常用参数说明实例解析输出各部分解析其他相关信息总结下面是一篇完善优化后的博文示例，涵盖了dig命令的介绍、语法、参数说明、实例解析及其他相关信息&#xff0c…...

编程日记 2025/8/27 21:41:00

第18周：YOLOv5-C3模块实现

目录前言一、前期准备 1. 设置GPU 2. 导入数据 3. 划分数据集二、搭建包含C3模块的模型 1. 搭建模型 2. 查看模型详情三、训练模型 1. 编写训练函数 2. 编写测试函数 3. 正式训练四、结果可视化 1. Loss与Accuracy图 2. 模型评估五、总结前言 🍨 本文为…...

编程日记 2025/8/27 21:40:59

Note 12 R pro (MIUI 14.0.10) magisk方式获取root教程

Note 12 R pro (MIUI 14.0.10) magisk方式获取root教程解锁BL 可以参考： https://blog.csdn.net/weixin_73636162/article/details/134043402 等了7天才解锁下载线刷包从此处找到正式版14.0.10版本的线刷包： https://web.vip.miui.com/page/i…...

编程日记 2025/8/27 21:38:54

Python 高级编程与实战：构建数据可视化应用

在前几篇文章中，我们探讨了 Python 的基础语法、面向对象编程、函数式编程、元编程、性能优化、调试技巧、数据科学、机器学习、Web 开发、API 设计、网络编程、异步IO、并发编程、设计模式与软件架构、性能优化与调试技巧、分布式系统、微服务架构、自动化测试框架以及 RESTf…...

编程日记 2025/8/27 21:37:56

Memory should not be managed manually(Code Smell)

If you manage memory manually, it’s your responsibility to delete all memory created with new, and to make sure it’s delete d once and only once. Ensuring this is done is error-prone, especially when your function can have early exit points. Fortunately…...

编程日记 2025/8/27 21:36:10

一、树的基本概念

1.树的定义

2.子树的定义

3.结点的定义

1) 根结点

2) 叶子结点

3) 内部结点

4.结点的关系

1) 孩子结点

2) 父节点

3) 兄弟结点

5.树的深度

6.森林的定义

二、树的数据结构表示

1.结点 id

2.结点池

3.结点数据

4.孩子结点列表

5.添加树边

6.树的遍历

三、Python中的树

代码实现

Ⅰ、树的结点类定义

Ⅱ、树结构初始化

Ⅲ、根据索引获取树节点

Ⅳ、设置根结点

Ⅴ、添加孩子结点

Ⅵ、 给指定索引结点赋值

Ⅶ、打印树结构

Ⅷ、 Python中树的实现

四、实战

1.2236. 判断根结点是否等于子结点之和

方法一、直接判断是否相等

思路与算法

2.104. 二叉树的最大深度

方法一 递归

思路与算法

方法二、先序遍历 + 递归

思路与算法

五、树的应用

相关文章：

Ⅵ、给指定索引结点赋值

方法一递归