Day07 树和图
2026-08-08 21:44:19
发布于：广东
一、树（Tree）完整知识点+全部公式
（一）树基础定义与通用性质
1. 数学定义
树是连通、无回路（无环）的无向图，是图的特殊子集。
满足三个等价判定条件（满足任意两条即可判定为树）：
① n 个顶点，n-1 条边；② 连通；③ 无环。
2. 树基础核心特性
- 任意两个顶点之间有且仅有唯一一条简单路径；
- 在树上任意添加一条边，会产生且仅产生一个环；任意删除一条边，整棵树断开为两棵不连通子树；
- 递归结构：一棵树由根节点和若干互不相交的子树构成。
3. 树基础术语（有根树）
- 根节点：唯一没有父节点的起始节点；
- 父节点、子节点：直接相连的上下级节点；
- 叶子结点（叶节点）：度为0、没有子节点的节点；
- 深度：节点到根节点经过的边数；高度：节点到最远叶子的最长路径边数；
- 子树：某个节点及其所有后代节点组成的独立树形结构。
（二）树通用全套计算公式（所有树适用）
设：n = 总节点数，m = 总边数，k = 森林中树的棵数
1. 边数公式
单棵树：m = n - 1
森林（多棵不相交的树）：m = n - k
2. 树的握手定理（度数和公式）
所有节点度数之和 = 2×边数
边数=n-1
即可得到节点度数之和=2x(n-1)
（三）二叉树专属概念、性质与核心公式
约定符号：
n₀：度为0的叶子结点；n₁：度为1的结点；n₂：度为2的结点
1. 总节点拆分公式
n = n₀ + n₁ + n₂
2. 二叉树最重要推导公式
联立总度数公式与总节点公式可推出：
n₀ = n₂ + 1
结论：任意一棵非空二叉树，叶子结点数量永远比度为2的结点多1。
（四）特殊二叉树：满二叉树 & 完全二叉树
1. 满二叉树（每层节点全部填满）
性质：不存在度为1的节点，n₁=0
层数规则（根为第1层）：
① 第 i 层最多节点数：2^(i-1)
② 高度为 h 的满二叉树总节点数：n = 2^h - 1
③ 叶子全部集中在最后一层，叶子总数：2^(h-1)
- 完全二叉树（高频考点）
核心特性：
1. 前 h-1 层是标准满二叉树，仅最后一层节点靠左连续排列，右侧空缺；
2. 度为1的节点最多只有1个，即 n₁=0 或 n₁=1；
3. 层数计算公式：已知总节点 n，树的高度
h = ⌊log₂n⌋ + 1
4. 叶子节点快速计算
- n 为偶数：n₁=1，n₀=n/2
- n 为奇数：n₁=0，n₀=(n+1)/2
5. 顺序存储下标规则（数组下标从1开始）
节点 i 的左孩子：2i，右孩子：2i+1；任意节点 j 的父节点：⌊j/2⌋
（五）二叉树遍历与常见分类
1. 四种遍历方式
- 前序遍历：根 → 左子树 → 右子树
- 中序遍历：左子树 → 根 → 右子树
- 后序遍历：左子树 → 右子树 → 根
- 层序遍历（BFS）：从上到下、从左到右逐层访问
2. 常见二叉树类型
二叉搜索树BST、平衡二叉树AVL、红黑树、堆（底层为完全二叉树）
二、图（Graph）完整知识点+配套全套公式
（一）图基础定义与分类
1. 定义
图记作 G=(V,E)，V 是非空顶点集合，E 是边的集合。图是最通用的非线性结构，树、环、森林都是图的特例。
2. 三大分类
① 按边方向：无向图、有向图；
② 按边权重：无权图、带权图（也称网）；
③ 按重边/自环：简单图（无自环、无重复边）、多重图。
（二）图基础术语
- 度：无向图中依附于顶点的边条数；有向图分为入度（指向该顶点的边）、出度（从该顶点出发的边）；
- 路径：顶点首尾相连的边序列；回路/环：起点和终点为同一个顶点的路径；
- 连通图（无向）：任意两顶点互相可达；有向图强连通图：任意两点双向可达；
- DAG有向无环图：不存在环路，可进行拓扑排序；
- 生成子图：包含原图全部顶点的子图，树就是连通无向图的极小连通生成子图。
（三）图全套核心公式
设：n=|V| 顶点总数，m=|E| 边总数
- 通用握手定理（图最重要公式）
（1）无向图
所有顶点度数之和等于边数的2倍
度数之和= 2m
对标树：树是特殊无向图，代入 m=n-1 直接得到 度数之和=2(n-1)，完美统一。
（2）有向图
所有顶点总入度之和 = 总出度之和 = 总边数
总入度 = 总出度 = m
- 简单图最大边数公式
① n 个顶点的无向简单图最多边数（完全无向图）
m_max = n(n-1)/2
② n 个顶点的有向简单图最多边数（完全有向图）
m_max = n(n-1)
（四）图存储结构
1. 邻接矩阵：二维数组存储，空间复杂度 O(n²)，适合小规模稠密图，查询两点邻接关系 O(1)；
2. 邻接表：每个顶点挂载链表存储邻接点，空间复杂度 O(n+m)，适合稀疏图，算法竞赛主流写法。
====================================================
树 一页纸必背清单
1. 树核心性质（必背）
- 本质：连通、无环、n个点n-1条边，满足任意两条即可判定为树
- 两点路径唯一；加边成环、删边断裂
- 森林：多棵互不连通的树
2. 通用树全部公式
- 单树边数：m = n - 1
- 森林边数：m = n - k（k为树的棵数）
- 树度数总和：∑deg = 2(n-1)
3. 二叉树核心公式
- 总节点：n = n₀ + n₁ + n₂
- 万能结论：n₀ = n₂ + 1（叶子比二度节点多1）
4. 满二叉树（高度h）
- 第i层最大节点：2^(i-1)
- 总节点数：n = 2^h - 1
- 无度1节点：n₁=0
5. 完全二叉树（考点最多）
- 结构：前h-1层满，最后一层靠左排列
- 度1节点：n₁=0 或 1
- 树高公式：h = ⌊log₂n⌋ + 1
- 叶子计算：偶数n→n₀=n/2；奇数n→n₀=(n+1)/2
- 存储下标（从1开始）：左孩子2i、右孩子2i+1、父节点⌊j/2⌋
6. 二叉树遍历口诀
- 前序：根左右 中序：左根右 后序：左右根 层序：逐层遍历
====================================================
图 一页纸必背清单
1. 图基础定义与分类
- 结构：G=(V,E)，通用非线性结构，树是特殊图
- 分类：有向/无向、带权/无权、简单图/多重图
- 核心概念：度、路径、回路、连通分量、强连通、DAG有向无环图
2. 图核心万能公式
- 无向图握手定理：∑deg = 2m
- 有向图度数定理：总入度 = 总出度 = m
- 无向完全图最大边数：m_max = n(n-1)/2
- 有向完全图最大边数：m_max = n(n-1)
- 森林（p个连通分量）：m = n - p
3. 存储结构
- 邻接矩阵：O(n²)，适合稠密图、查询快
- 邻接表：O(n+m)，适合稀疏图、代码常用
4. 核心遍历与算法
- 遍历：DFS深度优先、BFS广度优先（无权最短路）
- 最短路：Dijkstra、Floyd、Bellman-Ford
- 生成树：Kruskal、Prim
- DAG专属：拓扑排序、判环
全部评论 2
泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶 泰山压顶
1周前 来自 广东
1
有帮助，赞一个