Knowledge
树知识点
用于复习树的性质、生成树、二叉树、哈夫曼树、深度和高度计算。
树的基本性质
树是连通且无回路的无向图，n 个顶点的树有 n-1 条边。
重要公式
- 树：连通 + 无回路
- |E|=|V|-1
常见考法
在连通、无回路、n-1 条边之间相互推出。
复习提示
- 树题常用反证法处理回路或连通性。
易错提醒
只有 n-1 条边不一定是树，还要看连通性或无回路。
生成树
生成树是包含原图全部顶点的树形支撑子图。
重要公式
- n 个顶点的生成树有 n-1 条边
常见考法
判断支撑子图、生成树和最小生成树。
复习提示
- 连通图一定存在生成树。
易错提醒
生成树保留全部顶点，但不保留全部边。