【Python 数据结构 9.树】

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

                                                                                                        —— 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

---

五、树的应用

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