序言

树是一种很常用的数据结构，此文汇总了树的一些相关概念。

基本概念

树（tree）可以用几种方式定义。定义树的一种自然的方式是递归的方式。一棵树是一些节点的集合。这个集合可以是空集；若不是空集，则树由称做根（root）的节点 r 以及 0 个或多个非空的（子）树 T1，T2，…，Tk，组成，这些子树中每一棵的根都被来自根 r 的一条有向的边（edge）所连结。

每一棵子树的根叫做根 r 的儿子（child），而 r 是每一棵子树的根的父亲（parent）。

从递归定义中我们发现，一棵树是 N 个节点和 N-1 条边的集合，其中的一个节点叫做根。存在 N-1 条边的结论是由下面的事实得出的：每条边都将某个节点连接到它的父亲，而除去根节点外每一个节点都有一个父亲。每一个节点可以有任意多个儿子，也可能是零个儿子。没有儿子的节点称为树叶（leaf）；具有相同父亲的节点为兄弟（siblings）；用类似的方法可以定义祖父（grandparent）和孙子（grandchild）关系。

从节点 n1 到 nk 的路径（path）定义为节点 n1，n2，..·，nk 的一个序列，使得对于 1≤i<k 节点 n；是 n(i+1) 的父亲。这条路径的长（length）是为该路径上的边的条数，即 k-1。注意，在一棵树中从根到每个节点恰好存在一条路径。
对任意节点 n(i)，n(i) 的深度（depth）为从根到 n(i) 的唯一的路径的长。因此，根的深度为 0。n(i) 的高（height）是从 n(i) 到一片树叶的最长路径的长。因此所有的树叶的高都是 0。一棵树的高等于它的根的高。一棵树的深度等于它的最深的树叶的深度；该深度总是等于这棵树的高。

如果存在从 n1 到 n2 的一条路径，那么 n1 是 n2 的一位祖先（ancestor），而 n2 是 n1 的一个后裔（descendant）。如果 n1≠n2，那么 n1 是 n2 的真祖先（proper ancestor）而 n2 是 n1 的真后裔 (proper descendant)。

树的类别

和日常生活中所见到的树一样，为了适应不同的环境，不同的树存在一些差异性结构，为了适应不同的业务需要，数据结构中的树同样如此，存在了不同种类的树。
数据结构的树大概存在以下种类：

二叉树
- 满二叉树
- 完全二叉树
- 线索二叉树
- 平衡二叉树
哈夫曼树
AVL 树
红黑树
B 树
B+ 树
堆

树的遍历

树的遍历是指按照一定规则，逐个访问树中的节点，以便获取或处理节点的值或相关信息。

树的遍历可以分为两种：

深度优先遍历
广度优先遍历

具体选择哪种遍历操作，取决于具体业务。

深度优先遍历

深度优先遍历（Depth-First Traversal）是一种递归或使用栈的方式进行树遍历的方法。它从根节点开始，先访问当前节点，然后依次访问当前节点的子节点（左子节点或右子节点），直到遍历完整个子树，然后返回上一级节点继续遍历其未访问的子节点。

根据访问节点的顺序，深度优先遍历可以进一步分为三种方式：

前序遍历（DLR）：首先访问根结点，之后遍历左子树，最后遍历右子树
中序遍历（LDR）：首先遍历左子树，之后访问根结点，最后遍历右子树
后序遍历（LRD）：首先遍历左子树，之后遍历右子树，最后访问根结点

从定义可以发现，深度优先遍历是叫前，还是中，还是后，取决于根结点的位置，根结点在哪个位置，就叫什么遍历。

应用场景

前序遍历

前序遍历在许多业务场景中都有应用，其中一些典型的场景包括：

表达式求值：在数学表达式求值时，可以使用前序遍历来遍历表达式树，从根节点开始按照操作符的优先级进行计算
代码生成：在编译器或解释器中，可以使用前序遍历来遍历语法树或抽象语法树（AST），根据树的结构生成相应的代码
表单数据处理：在处理表单数据或配置文件时，可以使用前序遍历来遍历数据结构，执行相应的操作，如数据验证、数据转换等
目录结构遍历：在文件系统中，可以使用前序遍历来遍历目录结构，获取文件和文件夹的层级关系以及相应的信息
网络爬虫：在网络爬虫中，可以使用前序遍历来遍历网页链接，从根链接开始递归地访问子链接，实现网页抓取和数据提取
视图渲染：在图形界面或Web开发中，可以使用前序遍历来遍历 UI 组件树或 DOM 树，实现视图的渲染和事件处理
树结构分析：在各种树结构的分析中，可以使用前序遍历来遍历树节点，进行深度优先的分析和处理

中序遍历

中序遍历结果刚好是按顺序排列的，在一些排序算法中，可以使用中序遍历来对二叉搜索树进行中序遍历，从而得到有序的元素序列。

后序遍历

后序遍历（Post-order Traversal）是一种树的遍历方式，具体顺序为左子树 -> 右子树 -> 根节点。

后序遍历在一些特定的应用场景中是非常有用的，其中一些常见的业务场景如下：

表达式树解析：后序遍历是解析前缀（Polish）和后缀（Reverse Polish）表示法的算术表达式的一种有效方式。在这种情况下，运算符位于操作数之后（后缀）或之前（前缀）。例如，后序遍历可以用于计算后缀表达式（也称为逆波兰表示法）
文件系统操作：后序遍历可以用于执行涉及文件系统的操作，特别是那些需要先处理子目录或文件，然后才能处理父目录的操作。例如，如果你想删除一个目录及其所有子目录和文件，你可能需要先删除子目录和文件（后序遍历的”左”和”右”），然后再删除父目录（后序遍历的”根”）
内存管理：在某些内存管理任务中，如垃圾回收，后序遍历可以用来确保只有在所有的子节点都被处理之后，才会处理父节点。这对于正确地释放内存非常重要
语言处理和编译器设计：在编译器设计和其他语言处理任务中，后序遍历可以用来处理抽象语法树（AST）。例如，如果你想计算一个表达式的值，你可能需要先计算子表达式（后序遍历的”左”和”右”），然后再根据这些子表达式的值和父节点的操作符来计算父表达式的值（后序遍历的”根”）。
树的剪枝：在一些树结构的算法中，可以使用后序遍历来遍历树节点并进行剪枝操作，删除不符合条件的节点
决策树和回归树：在决策树和回归树算法中，后序遍历可以用于遍历决策树或回归树的节点，并进行预测或决策
系统资源释放：在一些系统编程中，后序遍历可以用于释放系统资源，如内存释放、文件关闭等

广度优先遍历

广度优先遍历（Breadth-First Traversal），又称为层次遍历，是一种逐层访问树节点的方法。它从根节点开始，首先访问根节点，然后逐层访问当前层的所有节点，直到遍历完整个树。

在广度优先遍历中，一般使用队列来存储待访问的节点，因为队列先进先出的特点可以保证按层遍历。

应用场景

广度优先遍历常用于层级遍历、最短路径等问题。

文章信息

时间	说明
2022-08-19	初稿