1866 字
9 分钟
树的知识总结
一、树的基本定义与术语
1. 什么是树？
树 是一种非线性的数据结构，它是由 n (n≥0) 个有限节点组成的一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，根在上，叶在下。
- 空树：当 n=0 时，称为空树。
- 非空树：在任意一棵非空树中，有且仅有一个特定的节点称为根。
2. 关键术语（结合下图理解）
让我们通过一个例子来理解这些术语：
A (根节点) /|\ B C D / \ \ E F G / \ H I- 节点：树中的每个元素，如图中的 A, B, C, …, I。
- 根节点：没有父节点的节点，即树最顶层的节点。（A）
- 父节点：一个节点的直接上层节点。如 B 是 E 和 F 的父节点。
- 子节点：一个节点的直接下层节点。如 E 和 F 是 B 的子节点。
- 兄弟节点：具有相同父节点的节点。如 B, C, D 互为兄弟节点；E 和 F 互为兄弟节点。
- 叶节点/终端节点：没有子节点的节点。如图中的 C, F, H, I, G。
- 分支节点/非终端节点：不是叶节点的节点（即至少有一个子节点）。如图中的 A, B, D, E。
- 节点的度：一个节点拥有的子节点个数。例如：
- 节点 A 的度 = 3 (有B, C, D三个子节点)
- 节点 B 的度 = 2 (有E, F两个子节点)
- 节点 C 的度 = 0 (是叶节点)
- 树的度：树内各节点的度的最大值。在上面的树中，节点的度最大为 3 (节点A)，所以这棵树的度是 3。
- 路径：从节点
n1到nk的路径是一个节点序列n1, n2, ..., nk，其中对于 1 ≤ i < k，ni是n(i+1)的父节点。路径的长度是所经过的边的数量。- 例如，从 A 到 H 的路径是 A -> B -> E -> H，路径长度为 3。
- 祖先与子孙：如果从根节点到节点
q存在一条路径，且节点p在这条路径上，那么p是q的祖先，q是p的子孙。- 例如，A, B, E 都是 H 的祖先；H, I 是 E 的子孙。
二、深度与高度（重点与易混点）
这是两个非常容易混淆的概念，但它们有本质的区别。核心记忆点：深度是自上而下累加，高度是自下而上累加。
1. 节点的深度
- 定义：从根节点到该节点所经过的边的数量。
- 计算方法：从根节点开始（深度为0），每向下一层，深度加1。
- 特点：根节点的深度为0（或某些教材定义为1，但计算机科学中普遍使用0，面试时需确认）。一个节点的深度由其祖先节点决定。
在上面的例子中：
- 节点 A 的深度 = 0 (根节点)
- 节点 B 的深度 = 1
- 节点 E 的深度 = 2
- 节点 H 的深度 = 3
2. 节点的高度
- 定义：从该节点到其最远叶节点所经过的边的数量。
- 计算方法：从该节点开始，向下遍历到最远的叶节点，计算路径上的边数。
- 特点：所有叶节点的高度为0。一个节点的高度由其子孙节点决定。
在上面的例子中：
- 节点 H 的高度 = 0 (叶节点)
- 节点 E 的高度 = 1 (到 H 或 I)
- 节点 B 的高度 = 2 (路径 B -> E -> H/I)
- 节点 A 的高度 = 3 (路径 A -> B -> E -> H/I 或 A -> D -> G)
3. 树的深度/高度
- 定义：树中所有节点的深度的最大值，也就是根节点的高度。
- 在上例中，树的深度/高度 = 3。
三、深度与高度的计算方法（递归与迭代）
我们通常使用递归来定义和计算它们，因为树本身就是递归定义的。
递归定义
- **节点的高度 **
height(node):- 如果
node是null(空树或空子树)，返回 -1。 - 如果
node是叶节点 (即node.left和node.right都为null)，返回 0。 - 否则，返回
1 + max(height(node.left), height(node.right))。 - 解释：节点的高度是其左右子树中较高的那个的高度再加1（加的1是连接自己和子节点的这条边）。
- 如果
- 节点的深度:
- 在树的结构中，我们通常不会为每个节点单独计算深度，因为深度是从根节点开始传递的。通常是在遍历（如前序遍历）时，将当前深度作为参数传递下去。
代码示例（以计算节点高度为例）
以下是一个简单的二叉树节点类和计算高度的方法：
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right
def get_height(node): """ 计算二叉树中某个节点的高度 (递归方法) """ # 1. 基准情况：如果节点为空，返回-1 if node is None: return -1
# 2. 递归计算左子树和右子树的高度 left_height = get_height(node.left) right_height = get_height(node.right)
# 3. 当前节点的高度是左右子树中较大的那个高度 + 1 return 1 + max(left_height, right_height)
# 构建示例树： A(B(E(H,I),F),C,D(G))# 注意：这是一个多叉树，为了代码演示，我们构建一个类似的二叉树结构。# A# / \# B C# / \ \# E F D# / \ \# H I G
root = TreeNode('A')root.left = TreeNode('B')root.right = TreeNode('C')root.left.left = TreeNode('E')root.left.right = TreeNode('F')root.left.left.left = TreeNode('H')root.left.left.right = TreeNode('I')root.right.right = TreeNode('D')root.right.right.right = TreeNode('G')
print(f"The height of the tree is: {get_height(root)}") # 输出： 3 (从A到H)print(f"The height of node 'B' is: {get_height(root.left)}") # 输出： 2 (从B到H)print(f"The height of node 'E' is: {get_height(root.left.left)}") # 输出： 1 (从E到H)迭代方法（使用层次遍历计算树的高度）
我们也可以使用队列进行广度优先搜索（BFS）来计算树的高度。
from collections import deque
def get_height_iterative(root): """ 使用层次遍历（BFS）计算树的高度 (迭代方法) """ if root is None: return -1
height = -1 # 初始化为-1，因为根节点所在层是第0层 queue = deque([root])
while queue: level_size = len(queue) # 处理当前层的所有节点 for _ in range(level_size): node = queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) # 每处理完一层，高度加1 height += 1 return height
print(f"The height of the tree (iterative) is: {get_height_iterative(root)}") # 输出： 3总结与对比
| 概念 | 定义 | 计算视角 | 基准情况 |
|---|---|---|---|
| 节点的深度 | 从根节点到该节点的路径长度 | 自上而下 | 根节点的深度为0 |
| 节点的高度 | 从该节点到最远叶节点的路径长度 | 自下而上 | 叶节点的高度为0，空节点高度为-1 |
| 树的高度/深度 | 根节点的高度 或 所有节点深度的最大值 | - | - |
学习建议：
- 画图：对于任何树的问题，先在纸上画出来，手动标出每个节点的深度和高度。
- 理解递归：递归是解决树问题最自然、最强大的工具，务必掌握其思想。
- 分清视角：时刻记住深度是“我从根那里下来了多少步”，高度是“我的子孙中最远的那个离我多远”。
希望这份总结对你有帮助！树是数据结构中的一个宝库，打好基础后，学习二叉树、二叉搜索树、AVL树等都会轻松很多。如果你有任何疑问，随时可以再问我。