1. 从“家谱”到“文件系统”为什么我们需要树干了这么多年开发无论是写业务逻辑还是啃底层源码总有一个数据结构像空气一样无处不在却又常常被我们忽略其精妙之处——那就是树。你可能没专门研究过它但你肯定用过文件管理器里的文件夹嵌套也肯定在刷算法题时被“二叉树遍历”折磨过。树本质上就是一种分层组织数据的模型它完美地模拟了现实世界中大量存在的“一对多”关系。想想你的电脑文件系统C盘下面有“Program Files”、“Users”等文件夹“Users”里又有你的用户名文件夹里面再装着“Documents”、“Downloads”……这不是一个典型的树形结构吗再想想公司的组织架构CEO下面管着几个副总裁每个副总裁分管几个部门部门下又有若干小组。这种清晰的层级关系用线性结构比如数组或链表来表示会非常别扭而树结构则天生契合。我最初学数据结构时总觉得“树”的概念一大堆术语——父亲、儿子、深度、叶子——枯燥又抽象。直到后来自己设计一个商品分类模块需要支持无限级分类时才恍然大悟这些术语不是学者们造出来为难我们的而是精确描述这种层级关系的必备工具。没有这些清晰的定义我们连讨论和实现一个树形结构都做不到。今天我就把这些年关于树和森林最核心、最基础的概念用最直白的方式捋一遍这就像是学武功前扎的马步基础打牢了后面学二叉树、平衡树、B树才能事半功倍。2. 核心概念拆解像认识一个新家族一样理解树要理解一棵“树”我们得先把它想象成一个家族或者一个公司的管理体系这样那些抽象的概念立刻就会鲜活起来。2.1 结点与关系谁是谁的谁首先树里的每一个元素我们称之为结点。每个结点就像家族里的一个人。根结点这是树的起点是唯一一个没有“上级”的结点。就像家族的始祖或者公司的创始人。任何一棵非空的树有且仅有一个根结点。在文件系统里它就是那个盘符比如C:\。父亲与儿子这是一种直接的上下级关系。如果结点A直接连接到结点B且A在上层B在下层那么A就是B的父亲B就是A的儿子。一个父亲可以有多个儿子但一个儿子只能有一个直接父亲根结点除外。在文件夹里“Users”文件夹是“John”文件夹的父亲。兄弟拥有同一个父亲的多个结点彼此互称为兄弟。比如“Documents”和“Downloads”文件夹它们都是“John”的儿子所以它们是兄弟关系。祖先与后裔这是关系的延伸。从结点A出发沿着父子关系一直向上走能到达的所有结点包括父亲、父亲的父亲……直到根结点都是A的祖先。反过来从结点A出发沿着父子关系一直向下走能到达的所有结点都是A的后裔。注意父亲是最近的祖先儿子是最近的后裔。注意在严谨的定义中一个结点不是自己的祖先或后裔。谈论祖先/后裔时通常指的是除了自己以外的直系上级或下级。2.2 结点的属性度量一个结点的“影响力”知道了谁是谁我们再来看看怎么量化描述一个结点。度一个结点的儿子个数就称为该结点的度。度衡量了一个结点的“直接下属”有多少。例如一个文件夹里有3个子文件夹它的度就是3。叶子结点度为0的结点。顾名思义它就像树梢的叶子没有下级了。在文件系统里一个纯文本文件.txt通常就是叶子结点。分支结点度大于0的结点。它就像树的枝干还会分出更小的枝桠。所有非叶子的结点都是分支结点注意根结点如果没有儿子也可以是叶子结点但这种情况很少见。层数与深度这两个概念容易混淆关键看起点。结点的层数从根结点开始定义根结点在第1层它的儿子在第2层以此类推。它描述的是结点在整棵树中的“绝对高度”。结点的深度从该结点出发向上回溯到根结点所经过的边数。根结点的深度为0。它描述的是结点到树根的“距离”。举个例子对于根结点的儿子它的层数是2深度是1。对于同一个结点其深度 层数 - 1。路径与路径长度从一个结点走到另一个结点所经过的结点序列称为路径。由于树中任意两结点间的路径是唯一的这是树的一个重要性质这个序列是明确的。路径中经过的边数称为路径长度。从根结点到某个结点的路径长度就等于该结点的深度。2.3 树的整体属性这棵树有多大、多高树的深度也称为树的高度。它是树中所有结点的最大层数或者说根结点的最大后裔深度1。它衡量了这棵树“最深”能到多少层。一个只有根结点的树深度为1。2.4 从树到森林当不止一棵树时森林就是mm≥0棵互不相交的树的集合。这是一个非常自然的概念。把一棵树的根结点去掉它的每棵子树就各自独立这些子树的集合就构成了一个森林。反过来给一个森林加上一个统一的根结点森林就变成了一棵树。在计算机中森林的典型例子就是多棵树状任务队列或者操作系统内核中多个独立的进程树每个进程及其子进程构成一棵树所有进程树组成森林。3. 概念的应用与辨析在代码和思考中落地理解了静态概念我们来看看它们在动态操作和算法思考中如何体现。3.1 如何计算树的深度这是一个经典的递归问题完美体现了树的结构特性。树的深度等于其根结点所有子树中深度最大者再加1。用伪代码表示这个递归思想非常清晰def tree_depth(node): if node is None: # 空结点深度为0 return 0 if node.children is empty: # 叶子结点深度为1 return 1 max_child_depth 0 for child in node.children: child_depth tree_depth(child) if child_depth max_child_depth: max_child_depth child_depth return max_child_depth 1 # 当前结点深度 最大子树深度 1实操心得在面试或实际编码中对于二叉树这个递归函数会简化为max(depth(left_child), depth(right_child)) 1。务必注意递归的基准情况空结点返回0还是返回-1这取决于你对深度/高度的定义根节点为第1层还是第0层。我个人的习惯是深度从0开始计数根深度0这样空树的深度为-1单结点树深度为0与边数的概念更吻合。但在很多教材中深度从1开始计数。关键是在一个项目或一次讨论中保持定义一致。3.2 叶子结点 vs. 分支结点遍历时的分水岭在遍历树如前序、中序、后序遍历时区分叶子结点和分支结点至关重要因为对它们的处理逻辑往往不同。遍历叶子结点你可能需要收集所有叶子结点的值例如计算所有文件的总大小。遍历分支结点你可能需要执行某些管理操作例如统计所有非空文件夹的数量或对每个文件夹应用一个权限设置。在递归遍历中判断一个结点是否为叶子结点通常是递归的终止条件或特殊处理点def traverse(node): if node is None: return # 如果是叶子结点执行特定操作 if node.children is empty: # 或对于二叉树if node.left is None and node.right is None: process_leaf(node) return # 如果是分支结点先处理当前结点再递归处理子树 process_branch(node) for child in node.children: traverse(child)3.3 路径的唯一性树的核心优势与约束树结构有一个核心性质树中任意两个结点之间有且仅有一条路径。这个性质带来了双重影响优势查找关系变得非常高效。要判断A是否是B的祖先或者计算它们的“距离”只需要分别从A和B向上回溯到根比较路径即可。这比在复杂的网络图中寻找路径简单得多。约束它无法直接表示“多父”关系。在现实中一个员工可能同时向两个项目经理汇报矩阵式管理一个文件可能属于多个分类。这种“多对多”关系单纯的树结构无法直接表示需要引入更复杂的图结构如有向无环图或通过其他方式如软链接、标签系统来模拟。踩坑记录我曾设计过一个商品分类表最初直接用parent_id字段构建树。后来业务要求一个商品可以属于多个未级分类。这时单纯的树结构就捉襟见肘了。最终的解决方案是引入了“关系表”将商品与分类的多对多关系单独存储而分类自身的层级关系依然用树来维护。这就是清晰理解数据结构边界带来的好处。4. 从概念到实现树的存储与基础操作理解了是什么我们来看看在计算机里怎么表示它。树的存储方式直接影响了其操作的效率。4.1 树的存储结构选型主要有两种思想基于链式存储和基于顺序存储。4.1.1 链式存储直观的“父亲-儿子”链接这是最自然的方式。每个结点包含数据域和若干个指针域指向其儿子结点。不定长子结点表示法孩子表示法每个结点维护一个链表存放其所有儿子结点的指针。这种方式灵活能准确表示任意度的树是通用树最常用的存储方式。struct TreeNode { DataType data; struct TreeNode *firstChild; // 指向第一个儿子 struct TreeNode *nextSibling; // 指向下一个兄弟 };这种“左孩子右兄弟”表示法非常巧妙它可以将任何一棵普通的树转化为二叉树来存储和处理极大地统一了算法。定长子结点表示法假设树的度为k每个结点都包含k个指针域。这种方式浪费空间很多指针是空的且不灵活除非能确定树的度固定且较小否则不推荐。4.1.2 顺序存储利用数组和下标用一个连续的数组来存储所有结点。每个结点需要记录其父结点在数组中的索引父结点表示法。双亲表示法每个结点只存储其父结点的索引根结点的父索引可设为-1。这种方式寻找父结点和祖先非常快O(1)或O(depth)但寻找儿子或兄弟则需要遍历整个数组效率低下。适用于频繁“向上查找”的场景。#define MAX_SIZE 100 struct PTNode { DataType data; int parent; // 父结点下标 }; struct PTree { struct PTNode nodes[MAX_SIZE]; int root_idx; // 根结点位置 int node_count; // 结点数 };选型心得没有绝对的好坏。孩子表示法链式更通用操作子树方便双亲表示法顺序在需要快速定位祖先如并查集算法时优势明显。在工程中根据主要操作类型来选择甚至混合使用比如结点内既存子节点链表也存父节点指针也是常见的。4.2 基础操作的时间复杂度分析基于不同的存储结构基础操作的效率天差地别操作描述孩子表示法 (链式)双亲表示法 (顺序)备注查找结点N的父亲O(1)O(1)双亲表示法直接存储孩子表示法通常也需要存储父指针以便回溯。查找结点N的所有儿子O(degree(N))O(n)孩子表示法通过链表直接访问双亲表示法需扫描整个数组。在结点N下插入新儿子MO(1)O(1)链式插入链表头部顺序存储需在数组末尾添加并设置M.parentN。删除结点N及其子树O(size_of_subtree)O(n) 或 O(size_of_subtree)都需要遍历子树所有结点进行释放或标记。顺序存储中标记删除更常见。计算树的深度O(n)O(n)都需要遍历所有结点。递归或层次遍历实现。提示degree(N)指结点N的度n指树中总结点数。可以看到如果需要频繁地向下遍历找儿子、兄弟链式存储优势巨大如果只关心向上关系顺序存储更简洁高效。4.3 树的遍历四种经典策略遍历是树操作的基础。根据访问根结点的时机分为四种方式它们适用于不同的场景先序遍历根 - 子树1 - 子树2 - ...操作访问根结点然后依次先序遍历每棵子树。应用复制整棵树的结构、计算目录树的大小在访问文件夹时即累加其本身大小。递归代码框架def pre_order(node): if node is None: return visit(node) # 处理当前结点 for child in node.children: pre_order(child)后序遍历子树1 - 子树2 - ... - 根操作依次后序遍历每棵子树最后访问根结点。应用释放整棵树的内存必须先释放子结点、计算文件夹总大小必须先累加完所有子项的大小。递归代码框架def post_order(node): if node is None: return for child in node.children: post_order(child) visit(node) # 处理当前结点层次遍历第1层 - 第2层 - 第3层 - ...操作借助队列从根结点开始将其入队。然后循环出队一个结点并访问将其所有儿子结点入队。应用按层级打印组织架构图、寻找从根到某结点的最短路径广度优先搜索BFS。代码框架使用队列from collections import deque def level_order(root): if root is None: return queue deque([root]) while queue: node queue.popleft() visit(node) for child in node.children: queue.append(child)中序遍历主要针对二叉树左子树 - 根 - 右子树。对于多叉树中序遍历的定义不唯一通常不讨论。遍历实战技巧递归实现简洁易懂是理解概念的首选。但在生产环境中对于深度可能很大的树如超深的目录嵌套递归有栈溢出的风险。此时用显式的栈来模拟递归迭代法进行先序/后序遍历或用队列进行层次遍历是更稳健的做法。例如迭代先序遍历def pre_order_iterative(root): if root is None: return stack [root] while stack: node stack.pop() visit(node) # 注意为了让左儿子先被访问需要将儿子逆序入栈 for child in reversed(node.children): stack.append(child)5. 常见问题与深度思考在实际使用中总会遇到一些似是而非或需要权衡的问题。5.1 为什么树的定义中通常排除“空树”很多严谨的定义会说“树是n(n0)个结点的有限集。当n0时称为空树”。但在讨论具体性质如根结点、深度时我们通常默认树是非空的。这是因为空树是一个边界情况很多操作和性质对它没有意义比如问空树的根结点是什么深度是多少。在算法实现中首先要判断传入的根结点指针是否为空这是一个良好的防御性编程习惯。5.2 结点的度与树的度结点的度单个结点的儿子数。树的度树中所有结点的度的最大值。 区分这两个概念很重要。树的度决定了你设计数据结构时每个结点需要预留多少个儿子指针如果采用定长表示法。例如一棵二叉树其树的度最大为2。5.3 路径长度的两种语境结点到结点的路径长度指两结点间唯一路径上的边数。树的路径长度通常指树的带权路径长度是树中所有叶子结点的深度 × 权值之和。这个概念是哈夫曼树压缩算法的核心。不要混淆。5.4 森林、树与二叉树的相互转换这是一个重要的知识点因为它允许我们用研究得更透彻的二叉树算法来处理一般的树和森林。树 - 二叉树使用“左孩子右兄弟”法。每个结点的左指针指向其第一个儿子右指针指向其下一个兄弟。转换后原树的根结点在二叉树中其右子树一定为空因为根没有兄弟。森林 - 二叉树先将森林中的每棵树转换为二叉树然后将后一棵二叉树的根作为前一棵二叉树根结点的右兄弟即右指针连接起来。二叉树 - 树/森林上述过程的逆过程。转换的意义许多针对二叉树的高效算法如各种遍历、线索化可以间接应用于一般的树和森林扩大了算法的适用范围。5.5 如何高效判断结点间关系这是一个常见的面试题和实际问题。给定两个结点A和B如何判断A是否是B的祖先方法一向上回溯法从B开始不断访问其父结点如果某次访问到了A则A是B的祖先。时间复杂度为O(depth(B))。这是最常用的方法前提是结点结构中有指向父结点的指针。方法二预处理法如果查询极其频繁可以预处理出每个结点的“进入时间”和“离开时间”通过一次DFS遍历。如果结点A的区间完全包含结点B的区间则A是B的祖先。查询时间复杂度为O(1)但需要额外的存储空间和预处理时间。这在处理大型静态树如DOM树时非常有效。理解树的基本概念就像拿到了进入数据结构森林的地图和指南针。这些术语定义是同行间无歧义沟通的基础其背后蕴含的“分层”、“一对多”、“唯一路径”思想是设计无数高效算法如查找、排序、索引、决策的基石。下次当你看到文件夹嵌套、组织架构图或者算法题里的TreeNode时希望你能会心一笑清楚地知道每一个指针、每一个层级所代表的精确含义。 数据结构树与森林：核心概念、存储实现与遍历算法全解析
1. 从“家谱”到“文件系统”为什么我们需要树干了这么多年开发无论是写业务逻辑还是啃底层源码总有一个数据结构像空气一样无处不在却又常常被我们忽略其精妙之处——那就是树。你可能没专门研究过它但你肯定用过文件管理器里的文件夹嵌套也肯定在刷算法题时被“二叉树遍历”折磨过。树本质上就是一种分层组织数据的模型它完美地模拟了现实世界中大量存在的“一对多”关系。想想你的电脑文件系统C盘下面有“Program Files”、“Users”等文件夹“Users”里又有你的用户名文件夹里面再装着“Documents”、“Downloads”……这不是一个典型的树形结构吗再想想公司的组织架构CEO下面管着几个副总裁每个副总裁分管几个部门部门下又有若干小组。这种清晰的层级关系用线性结构比如数组或链表来表示会非常别扭而树结构则天生契合。我最初学数据结构时总觉得“树”的概念一大堆术语——父亲、儿子、深度、叶子——枯燥又抽象。直到后来自己设计一个商品分类模块需要支持无限级分类时才恍然大悟这些术语不是学者们造出来为难我们的而是精确描述这种层级关系的必备工具。没有这些清晰的定义我们连讨论和实现一个树形结构都做不到。今天我就把这些年关于树和森林最核心、最基础的概念用最直白的方式捋一遍这就像是学武功前扎的马步基础打牢了后面学二叉树、平衡树、B树才能事半功倍。2. 核心概念拆解像认识一个新家族一样理解树要理解一棵“树”我们得先把它想象成一个家族或者一个公司的管理体系这样那些抽象的概念立刻就会鲜活起来。2.1 结点与关系谁是谁的谁首先树里的每一个元素我们称之为结点。每个结点就像家族里的一个人。根结点这是树的起点是唯一一个没有“上级”的结点。就像家族的始祖或者公司的创始人。任何一棵非空的树有且仅有一个根结点。在文件系统里它就是那个盘符比如C:\。父亲与儿子这是一种直接的上下级关系。如果结点A直接连接到结点B且A在上层B在下层那么A就是B的父亲B就是A的儿子。一个父亲可以有多个儿子但一个儿子只能有一个直接父亲根结点除外。在文件夹里“Users”文件夹是“John”文件夹的父亲。兄弟拥有同一个父亲的多个结点彼此互称为兄弟。比如“Documents”和“Downloads”文件夹它们都是“John”的儿子所以它们是兄弟关系。祖先与后裔这是关系的延伸。从结点A出发沿着父子关系一直向上走能到达的所有结点包括父亲、父亲的父亲……直到根结点都是A的祖先。反过来从结点A出发沿着父子关系一直向下走能到达的所有结点都是A的后裔。注意父亲是最近的祖先儿子是最近的后裔。注意在严谨的定义中一个结点不是自己的祖先或后裔。谈论祖先/后裔时通常指的是除了自己以外的直系上级或下级。2.2 结点的属性度量一个结点的“影响力”知道了谁是谁我们再来看看怎么量化描述一个结点。度一个结点的儿子个数就称为该结点的度。度衡量了一个结点的“直接下属”有多少。例如一个文件夹里有3个子文件夹它的度就是3。叶子结点度为0的结点。顾名思义它就像树梢的叶子没有下级了。在文件系统里一个纯文本文件.txt通常就是叶子结点。分支结点度大于0的结点。它就像树的枝干还会分出更小的枝桠。所有非叶子的结点都是分支结点注意根结点如果没有儿子也可以是叶子结点但这种情况很少见。层数与深度这两个概念容易混淆关键看起点。结点的层数从根结点开始定义根结点在第1层它的儿子在第2层以此类推。它描述的是结点在整棵树中的“绝对高度”。结点的深度从该结点出发向上回溯到根结点所经过的边数。根结点的深度为0。它描述的是结点到树根的“距离”。举个例子对于根结点的儿子它的层数是2深度是1。对于同一个结点其深度 层数 - 1。路径与路径长度从一个结点走到另一个结点所经过的结点序列称为路径。由于树中任意两结点间的路径是唯一的这是树的一个重要性质这个序列是明确的。路径中经过的边数称为路径长度。从根结点到某个结点的路径长度就等于该结点的深度。2.3 树的整体属性这棵树有多大、多高树的深度也称为树的高度。它是树中所有结点的最大层数或者说根结点的最大后裔深度1。它衡量了这棵树“最深”能到多少层。一个只有根结点的树深度为1。2.4 从树到森林当不止一棵树时森林就是mm≥0棵互不相交的树的集合。这是一个非常自然的概念。把一棵树的根结点去掉它的每棵子树就各自独立这些子树的集合就构成了一个森林。反过来给一个森林加上一个统一的根结点森林就变成了一棵树。在计算机中森林的典型例子就是多棵树状任务队列或者操作系统内核中多个独立的进程树每个进程及其子进程构成一棵树所有进程树组成森林。3. 概念的应用与辨析在代码和思考中落地理解了静态概念我们来看看它们在动态操作和算法思考中如何体现。3.1 如何计算树的深度这是一个经典的递归问题完美体现了树的结构特性。树的深度等于其根结点所有子树中深度最大者再加1。用伪代码表示这个递归思想非常清晰def tree_depth(node): if node is None: # 空结点深度为0 return 0 if node.children is empty: # 叶子结点深度为1 return 1 max_child_depth 0 for child in node.children: child_depth tree_depth(child) if child_depth max_child_depth: max_child_depth child_depth return max_child_depth 1 # 当前结点深度 最大子树深度 1实操心得在面试或实际编码中对于二叉树这个递归函数会简化为max(depth(left_child), depth(right_child)) 1。务必注意递归的基准情况空结点返回0还是返回-1这取决于你对深度/高度的定义根节点为第1层还是第0层。我个人的习惯是深度从0开始计数根深度0这样空树的深度为-1单结点树深度为0与边数的概念更吻合。但在很多教材中深度从1开始计数。关键是在一个项目或一次讨论中保持定义一致。3.2 叶子结点 vs. 分支结点遍历时的分水岭在遍历树如前序、中序、后序遍历时区分叶子结点和分支结点至关重要因为对它们的处理逻辑往往不同。遍历叶子结点你可能需要收集所有叶子结点的值例如计算所有文件的总大小。遍历分支结点你可能需要执行某些管理操作例如统计所有非空文件夹的数量或对每个文件夹应用一个权限设置。在递归遍历中判断一个结点是否为叶子结点通常是递归的终止条件或特殊处理点def traverse(node): if node is None: return # 如果是叶子结点执行特定操作 if node.children is empty: # 或对于二叉树if node.left is None and node.right is None: process_leaf(node) return # 如果是分支结点先处理当前结点再递归处理子树 process_branch(node) for child in node.children: traverse(child)3.3 路径的唯一性树的核心优势与约束树结构有一个核心性质树中任意两个结点之间有且仅有一条路径。这个性质带来了双重影响优势查找关系变得非常高效。要判断A是否是B的祖先或者计算它们的“距离”只需要分别从A和B向上回溯到根比较路径即可。这比在复杂的网络图中寻找路径简单得多。约束它无法直接表示“多父”关系。在现实中一个员工可能同时向两个项目经理汇报矩阵式管理一个文件可能属于多个分类。这种“多对多”关系单纯的树结构无法直接表示需要引入更复杂的图结构如有向无环图或通过其他方式如软链接、标签系统来模拟。踩坑记录我曾设计过一个商品分类表最初直接用parent_id字段构建树。后来业务要求一个商品可以属于多个未级分类。这时单纯的树结构就捉襟见肘了。最终的解决方案是引入了“关系表”将商品与分类的多对多关系单独存储而分类自身的层级关系依然用树来维护。这就是清晰理解数据结构边界带来的好处。4. 从概念到实现树的存储与基础操作理解了是什么我们来看看在计算机里怎么表示它。树的存储方式直接影响了其操作的效率。4.1 树的存储结构选型主要有两种思想基于链式存储和基于顺序存储。4.1.1 链式存储直观的“父亲-儿子”链接这是最自然的方式。每个结点包含数据域和若干个指针域指向其儿子结点。不定长子结点表示法孩子表示法每个结点维护一个链表存放其所有儿子结点的指针。这种方式灵活能准确表示任意度的树是通用树最常用的存储方式。struct TreeNode { DataType data; struct TreeNode *firstChild; // 指向第一个儿子 struct TreeNode *nextSibling; // 指向下一个兄弟 };这种“左孩子右兄弟”表示法非常巧妙它可以将任何一棵普通的树转化为二叉树来存储和处理极大地统一了算法。定长子结点表示法假设树的度为k每个结点都包含k个指针域。这种方式浪费空间很多指针是空的且不灵活除非能确定树的度固定且较小否则不推荐。4.1.2 顺序存储利用数组和下标用一个连续的数组来存储所有结点。每个结点需要记录其父结点在数组中的索引父结点表示法。双亲表示法每个结点只存储其父结点的索引根结点的父索引可设为-1。这种方式寻找父结点和祖先非常快O(1)或O(depth)但寻找儿子或兄弟则需要遍历整个数组效率低下。适用于频繁“向上查找”的场景。#define MAX_SIZE 100 struct PTNode { DataType data; int parent; // 父结点下标 }; struct PTree { struct PTNode nodes[MAX_SIZE]; int root_idx; // 根结点位置 int node_count; // 结点数 };选型心得没有绝对的好坏。孩子表示法链式更通用操作子树方便双亲表示法顺序在需要快速定位祖先如并查集算法时优势明显。在工程中根据主要操作类型来选择甚至混合使用比如结点内既存子节点链表也存父节点指针也是常见的。4.2 基础操作的时间复杂度分析基于不同的存储结构基础操作的效率天差地别操作描述孩子表示法 (链式)双亲表示法 (顺序)备注查找结点N的父亲O(1)O(1)双亲表示法直接存储孩子表示法通常也需要存储父指针以便回溯。查找结点N的所有儿子O(degree(N))O(n)孩子表示法通过链表直接访问双亲表示法需扫描整个数组。在结点N下插入新儿子MO(1)O(1)链式插入链表头部顺序存储需在数组末尾添加并设置M.parentN。删除结点N及其子树O(size_of_subtree)O(n) 或 O(size_of_subtree)都需要遍历子树所有结点进行释放或标记。顺序存储中标记删除更常见。计算树的深度O(n)O(n)都需要遍历所有结点。递归或层次遍历实现。提示degree(N)指结点N的度n指树中总结点数。可以看到如果需要频繁地向下遍历找儿子、兄弟链式存储优势巨大如果只关心向上关系顺序存储更简洁高效。4.3 树的遍历四种经典策略遍历是树操作的基础。根据访问根结点的时机分为四种方式它们适用于不同的场景先序遍历根 - 子树1 - 子树2 - ...操作访问根结点然后依次先序遍历每棵子树。应用复制整棵树的结构、计算目录树的大小在访问文件夹时即累加其本身大小。递归代码框架def pre_order(node): if node is None: return visit(node) # 处理当前结点 for child in node.children: pre_order(child)后序遍历子树1 - 子树2 - ... - 根操作依次后序遍历每棵子树最后访问根结点。应用释放整棵树的内存必须先释放子结点、计算文件夹总大小必须先累加完所有子项的大小。递归代码框架def post_order(node): if node is None: return for child in node.children: post_order(child) visit(node) # 处理当前结点层次遍历第1层 - 第2层 - 第3层 - ...操作借助队列从根结点开始将其入队。然后循环出队一个结点并访问将其所有儿子结点入队。应用按层级打印组织架构图、寻找从根到某结点的最短路径广度优先搜索BFS。代码框架使用队列from collections import deque def level_order(root): if root is None: return queue deque([root]) while queue: node queue.popleft() visit(node) for child in node.children: queue.append(child)中序遍历主要针对二叉树左子树 - 根 - 右子树。对于多叉树中序遍历的定义不唯一通常不讨论。遍历实战技巧递归实现简洁易懂是理解概念的首选。但在生产环境中对于深度可能很大的树如超深的目录嵌套递归有栈溢出的风险。此时用显式的栈来模拟递归迭代法进行先序/后序遍历或用队列进行层次遍历是更稳健的做法。例如迭代先序遍历def pre_order_iterative(root): if root is None: return stack [root] while stack: node stack.pop() visit(node) # 注意为了让左儿子先被访问需要将儿子逆序入栈 for child in reversed(node.children): stack.append(child)5. 常见问题与深度思考在实际使用中总会遇到一些似是而非或需要权衡的问题。5.1 为什么树的定义中通常排除“空树”很多严谨的定义会说“树是n(n0)个结点的有限集。当n0时称为空树”。但在讨论具体性质如根结点、深度时我们通常默认树是非空的。这是因为空树是一个边界情况很多操作和性质对它没有意义比如问空树的根结点是什么深度是多少。在算法实现中首先要判断传入的根结点指针是否为空这是一个良好的防御性编程习惯。5.2 结点的度与树的度结点的度单个结点的儿子数。树的度树中所有结点的度的最大值。 区分这两个概念很重要。树的度决定了你设计数据结构时每个结点需要预留多少个儿子指针如果采用定长表示法。例如一棵二叉树其树的度最大为2。5.3 路径长度的两种语境结点到结点的路径长度指两结点间唯一路径上的边数。树的路径长度通常指树的带权路径长度是树中所有叶子结点的深度 × 权值之和。这个概念是哈夫曼树压缩算法的核心。不要混淆。5.4 森林、树与二叉树的相互转换这是一个重要的知识点因为它允许我们用研究得更透彻的二叉树算法来处理一般的树和森林。树 - 二叉树使用“左孩子右兄弟”法。每个结点的左指针指向其第一个儿子右指针指向其下一个兄弟。转换后原树的根结点在二叉树中其右子树一定为空因为根没有兄弟。森林 - 二叉树先将森林中的每棵树转换为二叉树然后将后一棵二叉树的根作为前一棵二叉树根结点的右兄弟即右指针连接起来。二叉树 - 树/森林上述过程的逆过程。转换的意义许多针对二叉树的高效算法如各种遍历、线索化可以间接应用于一般的树和森林扩大了算法的适用范围。5.5 如何高效判断结点间关系这是一个常见的面试题和实际问题。给定两个结点A和B如何判断A是否是B的祖先方法一向上回溯法从B开始不断访问其父结点如果某次访问到了A则A是B的祖先。时间复杂度为O(depth(B))。这是最常用的方法前提是结点结构中有指向父结点的指针。方法二预处理法如果查询极其频繁可以预处理出每个结点的“进入时间”和“离开时间”通过一次DFS遍历。如果结点A的区间完全包含结点B的区间则A是B的祖先。查询时间复杂度为O(1)但需要额外的存储空间和预处理时间。这在处理大型静态树如DOM树时非常有效。理解树的基本概念就像拿到了进入数据结构森林的地图和指南针。这些术语定义是同行间无歧义沟通的基础其背后蕴含的“分层”、“一对多”、“唯一路径”思想是设计无数高效算法如查找、排序、索引、决策的基石。下次当你看到文件夹嵌套、组织架构图或者算法题里的TreeNode时希望你能会心一笑清楚地知道每一个指针、每一个层级所代表的精确含义。