为了避免大家对树不了解，或者时间久了遗忘了很多内容，下面我们先把树相关的概念做一下简单回顾；
可能内容稍微有点基础了，但是主要是想对算法和数据结构做一次整体的梳理；
后续基础部分整理完后也会开始比较难的算法部分；
一、回顾
树（Tree）是计算机科学中一种非线性层次化数据结构，它通过“节点”（Node）和“边”（Edge）模拟现实中树的分支结构，相比数组、链表等线性结构，能更高效地组织具有层级关系的数据（如文件系统、组织结构）。其核心特点是无环且连通，即任意两个节点间有且仅有一条路径，且不存在闭环。
（一）树的基本概念与术语
理解树结构需先掌握以下核心术语，以“普通树”和“二叉树”的通用概念为例：
术语定义与说明节点（Node）树的基本组成单元，存储数据（如值、指针），分为不同类型： - 根节点：树的顶层节点，无父节点（唯一）； - 叶子节点：无子节点的终端节点； - 内部节点：既有父节点也有子节点的中间节点。边（Edge）连接两个节点的线段，代表节点间的父子关系（如根节点到子节点的边）。父/子节点若边连接节点A和B，且A在B的上层，则A是B的父节点，B是A的子节点；同一父节点的子节点互称兄弟节点。层次（Level）根节点所在层为第1层（或第0层，视定义而定），其子节点为第2层，以此类推（描述节点的“深度”位置）。深度（Depth）从根节点到当前节点的边的数量（如根节点深度为0，其子节点深度为1）。高度（Height）从当前节点到最远叶子节点的边的数量（如叶子节点高度为0，根节点高度为树的最大层次）。子树（Subtree）以某节点为根，其所有后代节点（子节点、孙节点等）构成的树（原树的“子集”）。
（二）树的分类（按结构特征划分）
树的结构灵活，根据“子节点数量限制”“平衡性”等特征可分为多种类型，不同类型适用于不同场景：
1. 普通树（自由树）
特点：无限制子节点数量，父节点可拥有任意个孩子（如现实中的“家族树”“公司组织架构树”）。示例： 一个部门经理（根节点）下有3个小组组长（子节点），每个组长下又有不同数量的员工（叶子节点）。局限：结构不规则，难以用统一算法高效操作（如遍历、查找），因此实际工程中更常用“限制子节点数量”的树。
2. 二叉树（最常用的树结构）
核心定义：每个节点最多有两个子节点，分别称为“左子节点”和“右子节点”（即使只有一个子节点，也需明确左/右属性）。特殊类型（二叉树的衍生结构，优化性能）：
满二叉树：除叶子节点外，所有内部节点都有“左+右”两个子节点；且叶子节点全部在同一层（如3层满二叉树共7个节点：1根+2父+4叶）。完全二叉树：按“层序遍历顺序”（从左到右、从上到下）填充节点，若最后一层叶子节点未填满，仅允许“右侧缺漏”（如3层完全二叉树可有5/6/7个节点，不允许“左侧缺漏”）。 → 优势：可用数组存储（无需指针，通过索引计算父子关系：若父节点索引为i，左子节点为2i+1，右子节点为2i+2），节省内存。平衡二叉树（如AVL树、红黑树）：左右子树的高度差（平衡因子）不超过1，避免树结构“倾斜”为链表（保证查找、插入效率为O(log n)）。
3. 多叉树（K叉树）
特点：每个节点最多有K个子节点（K≥3），是普通树的“规则化”版本。典型应用：
B树/B+树（数据库索引）：多叉平衡树，每个节点可存储多个关键字，减少磁盘I/O次数（适合大规模数据存储）。Trie树（前缀树）：用于字符串前缀匹配（如搜索引擎自动补全、拼写检查），每个节点存储一个字符，路径代表完整字符串。
（三）树的核心操作
树的操作围绕“遍历”“插入”“删除”“查找”展开，其中遍历是基础（需访问树中所有节点，为后续操作提供支持）。
1. 遍历操作（以二叉树为例，通用思路可扩展到多叉树）
遍历即按特定顺序访问所有节点，常见方式分为“深度优先”和“广度优先”两类：
遍历类型具体方式访问顺序规则应用场景深度优先（DFS）前序遍历（根→左→右）先访问根节点，再递归遍历左子树，最后递归遍历右子树。复制树、获取树的前缀表达式中序遍历（左→根→右）先递归遍历左子树，再访问根节点，最后递归遍历右子树。二叉搜索树（BST）的升序输出后序遍历（左→右→根）先递归遍历左子树，再递归遍历右子树，最后访问根节点。计算树的高度、删除树节点广度优先（BFS）层序遍历（按层访问）从根节点开始，按“层次”依次访问每一层的所有节点（左到右），需用队列实现。树的层次统计、最短路径查找
2. 插入与删除
插入：需根据树的类型遵循规则（如二叉搜索树需保证“左子树值<根<右子树值”，平衡树需调整平衡因子），避免破坏树的结构特性。删除：较复杂，需考虑节点类型（叶子/内部节点），删除后可能需修复树的平衡性（如红黑树的“旋转”操作）。
3. 查找
普通查找：通过遍历（如DFS/BFS）逐个匹配节点值，效率为O(n)（n为节点总数）。高效查找：利用特殊树的特性（如二叉搜索树、B树），通过“比较-分支”减少访问节点数，效率可达O(log n)（平衡树）。
（四）树的核心应用场景
树的层次化结构使其在“需表达层级关系”“需高效查找/插入”的场景中不可替代，常见应用包括：
应用领域具体场景依赖的树类型数据存储与索引数据库索引（MySQL的InnoDB用B+树）、文件系统（如Linux的Ext4用多叉树）B树/B+树、多叉树字符串处理搜索引擎自动补全、拼写检查、IP路由匹配Trie树（前缀树）、后缀树算法与计算优先队列（任务调度）、Huffman数据压缩、决策树（机器学习分类）堆（完全二叉树）、Huffman树、决策树系统与架构组织架构图、XML/HTML文档解析（DOM树）、编译原理中的抽象语法树（AST）普通树、二叉树游戏与AI博弈树（如围棋AI的落子决策）、路径规划博弈树、状态树
（五）树与其他数据结构的对比
理解树的定位，需对比线性结构（数组、链表）和其他非线性结构（图）：
数据结构结构特性优势劣势典型操作效率数组线性、连续存储随机访问快（O(1)）插入/删除慢（需移动元素）查找：O(n)（未排序）链表线性、分散存储插入/删除快（O(1)，已知位置）随机访问慢（O(n)）查找：O(n)树非线性、层次存储兼顾插入/删除/查找效率（O(log n)）实现复杂（需维护结构特性）查找：O(log n)（平衡树）图非线性、任意节点连接表达复杂关系（如社交网络）操作效率低（如最短路径O(n²)）遍历：O(n+m)（n节点m边）
（六）总结
树是一种“平衡了线性结构效率与非线性结构表达能力”的数据结构，其核心价值在于：
层级化表达：天然适合描述具有父子/从属关系的数据（如文件系统、组织架构）；高效操作：通过平衡化（如红黑树）、规则化（如B树）优化，使插入、删除、查找效率达到O(log n)，远超线性结构；广泛适配：衍生出的堆、Trie树、Huffman树等结构，可满足任务调度、字符串处理、数据压缩等多样化需求，是计算机科学的基础数据结构之一。
二、树的遍历
树这种数据结构经常被用在查找频繁的场景下，因为时间复杂度随着数据量的暴增，他会变得逐渐平缓；
如你所见，红色的部分是O(n)也就是逐个查找的时间复杂度，而蓝色部分是O(log n)也就是树查找的时间复杂度；这个图证明了在大数据量的情况下，树的查找效率要更高；
在下面部分的遍历部分我们主要介绍四种遍历方式：
前序遍历(深度优先)中序遍历后序遍历层序遍历(广度优先)
对于前序遍历在深度优先搜索一文中涉及到了(不过就是换了个名称)：深度优先搜索(DFS)-CSDN博客
对于层序遍历在广度优先搜索一文中涉及到了(不过就是换了个名称)：广度优先搜索(BFS)-CSDN博客
这里以使用相对多的二叉树作为案例展开叙述：
1.前序遍历(深度优先)
示意图如下(先访问根节点，再递归遍历左子树，最后递归遍历右子树)：
Java代码实现：
public void preorder(TreeNode node) {
if (node == null) return;
System.out.print(node.val + " ");
preorder(node.left);
preorder(node.right);
}
栈执行过程：
步骤：
1. 栈: []
调用preorder(1) → 栈: [preorder(1)]
打印1 → 输出: 1
2. 调用preorder(2) → 栈: [preorder(1), preorder(2)]
打印2 → 输出: 1 2
3. 调用preorder(4) → 栈: [preorder(1), preorder(2), preorder(4)]
打印4 → 输出: 1 2 4
4. 4的左右为空 → 出栈 → 栈: [preorder(1), preorder(2)]
调用preorder(5) → 栈: [preorder(1), preorder(2), preorder(5)]
打印5 → 输出: 1 2 4 5
5. 5的左右为空 → 出栈 → 栈: [preorder(1), preorder(2)]
2出栈 → 栈: [preorder(1)]
调用preorder(3) → 栈: [preorder(1), preorder(3)]
打印3 → 输出: 1 2 4 5 3
6. 调用preorder(6) → 栈: [preorder(1), preorder(3), preorder(6)]
打印6 → 输出: 1 2 4 5 3 6
7. 6的左右为空 → 出栈 → 栈: [preorder(1), preorder(3)]
调用preorder(7) → 栈: [preorder(1), preorder(3), preorder(7)]
打印7 → 输出: 1 2 4 5 3 6 7
8. 7的左右为空 → 出栈 → 栈: [preorder(1), preorder(3)]
3出栈 → 栈: [preorder(1)]
1出栈 → 栈: []
2.中序遍历
示意图如下(先递归遍历左子树，再访问根节点，最后递归遍历右子树)：
Java代码实现：
public void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
System.out.print(node.val + " ");
inorder(node.right);
}
栈执行过程：
步骤：
1. 栈: []
调用inorder(1) → 栈: [inorder(1)]
调用inorder(2) → 栈: [inorder(1), inorder(2)]
调用inorder(4) → 栈: [inorder(1), inorder(2), inorder(4)]
2. 4的左为空 → 出栈 → 栈: [inorder(1), inorder(2)]
打印4 → 输出: 4
调用4的右(空) → 返回
3. 2的左处理完 → 打印2 → 输出: 4 2
调用inorder(5) → 栈: [inorder(1), inorder(2), inorder(5)]
4. 5的左为空 → 出栈 → 栈: [inorder(1), inorder(2)]
打印5 → 输出: 4 2 5
调用5的右(空) → 返回
2出栈 → 栈: [inorder(1)]
5. 1的左处理完 → 打印1 → 输出: 4 2 5 1
调用inorder(3) → 栈: [inorder(1), inorder(3)]
调用inorder(6) → 栈: [inorder(1), inorder(3), inorder(6)]
6. 6的左为空 → 出栈 → 栈: [inorder(1), inorder(3)]
打印6 → 输出: 4 2 5 1 6
调用6的右(空) → 返回
7. 3的左处理完 → 打印3 → 输出: 4 2 5 1 6 3
调用inorder(7) → 栈: [inorder(1), inorder(3), inorder(7)]
8. 7的左为空 → 出栈 → 栈: [inorder(1), inorder(3)]
打印7 → 输出: 4 2 5 1 6 3 7
调用7的右(空) → 返回
3出栈 → 栈: [inorder(1)]
1出栈 → 栈: []
3.后序遍历
示意图如下(先递归遍历左子树，再递归遍历右子树，最后访问根节点)：
Java代码实现：
public void postorder(TreeNode node) {
if (node == null) return;
postorder(node.left);
postorder(node.right);
System.out.print(node.val + " ");
}
栈执行过程：
步骤：
1. 栈: []
调用postorder(1) → 栈: [postorder(1)]
调用postorder(2) → 栈: [postorder(1), postorder(2)]
调用postorder(4) → 栈: [postorder(1), postorder(2), postorder(4)]
2. 4的左右为空 → 出栈 → 栈: [postorder(1), postorder(2)]
打印4 → 输出: 4
3. 调用postorder(5) → 栈: [postorder(1), postorder(2), postorder(5)]
5的左右为空 → 出栈 → 栈: [postorder(1), postorder(2)]
打印5 → 输出: 4 5
2出栈 → 栈: [postorder(1)]
打印2 → 输出: 4 5 2
4. 调用postorder(3) → 栈: [postorder(1), postorder(3)]
调用postorder(6) → 栈: [postorder(1), postorder(3), postorder(6)]
6的左右为空 → 出栈 → 栈: [postorder(1), postorder(3)]
打印6 → 输出: 4 5 2 6
5. 调用postorder(7) → 栈: [postorder(1), postorder(3), postorder(7)]
7的左右为空 → 出栈 → 栈: [postorder(1), postorder(3)]
打印7 → 输出: 4 5 2 6 7
3出栈 → 栈: [postorder(1)]
打印3 → 输出: 4 5 2 6 7 3
6. 1出栈 → 栈: []
打印1 → 输出: 4 5 2 6 7 3 1
4.层序遍历(广度优先)
示例图如下(从根节点开始，按“层次”从左到右访问每一层的所有节点，需用队列实现)：
Java代码实现：
public static void levelorderTraversal(TreeNode root) {
if (root == null) return;
Queue
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
总结
前序、中序、后序遍历的核心差异体现在 “访问节点值（取 val）的时机” 上，而这种差异本质上与函数调用栈的执行顺序直接相关。
为什么改变取 val 位置就能实现不同遍历？
递归实现的前、中、后序遍历，本质上是通过函数调用栈的压栈 / 出栈顺序控制节点访问时机：
当调用traversal(node)时，函数会先压入栈中，然后执行内部逻辑访问节点值（print(node.val)）的位置不同，对应它在栈中的执行阶段不同：
前序遍历：刚入栈就访问（先处理根节点，再压入左右子树的调用）中序遍历：左子树调用出栈后才访问（左子树处理完，再处理根节点）后序遍历：左右子树调用都出栈后才访问（左右子树都处理完，最后处理根节点）
那要是后面面试的时候，让你写个算法；
那直接提笔就来：
前序、中序、后续，分别对应取val的不同位置；层序加个队列记录；
那我算法思想都学明白了，规律也发现了，直接用规律不香么？
看完了这部分文章，可以去看看另外两篇，看看实际的算法该怎么写：
前序遍历-算法案例：深度优先搜索(DFS)-CSDN博客层序遍历-算法案例：广度优先搜索(BFS)-CSDN博客