树 - Hero · 算法 · 算法通关之路

废话

1. 递归可视化：https://recursion.vercel.app/

基本结构

树是一种非线性数据结构。树结构的基本单位是节点。节点之间的链接，称为分支（branch）。节点与分支形成树状，结构的开端，称为根（root），或根结点。根节点之外的节点，称为子节点（child）。没有链接到其他子节点的节点，称为叶节点（leaf）

节点表示

Node {
	value: any; // 当前节点的值
	children: Array<Node>; // 指向其儿子
}

重要概念

• 树的高度: 节点到叶子节点的最大值就是其高度
• 树的深度: 度和深度是相反的，高度是从下往上数，深度是从上往下。因此根节点的深度和叶子节点的高度是 0
• 树的层: 根开始定义，根为第一层，根的孩子为第二层
• 二叉树、N叉树…: 由其子节点最多可以有几个决定，最多有 N 个就是 N 叉树

二叉树

二叉树是树结构的一种，两个叉就是说每个节点最多只有两个子节点，我们习惯称之为左节点和右节点

表示

Node {
	value: any; // 当前节点的值
	left: Node | null; // 左儿子
	right: Node | null; // 右儿子
}

分类

• 完全二叉树: 顺序
• 满二叉树
• 二叉搜索树：左小右大，查找极快
• 平衡二叉树
• 红黑树

存储

• 链表存储
• 数组存储(非常适合完全二叉树)

树的核心操作

对树的核心操作始终是树的遍历

• 后序遍历(区别在在于对当前父节点的处理时机，是在回溯是处理还是在访问是就处理)
• 先序遍历
• 中序遍历是有序的

遍历方式

深度优先遍历(DFS, 细分前中后序遍历)

借助函数调用栈；深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止，属于盲目搜索。

广度优先遍历(BFS, 细分带层和不带层的)

暴力枚举，BFS不是层次遍历(即一层一层的遍历)，BFS 的核心在于求最短问题时候可以提前终止，这才是它的核心价值，层次遍历是一种不需要提前终止的 BFS 的副产物