大学离散数学《树》复习课件

期末复习离散数学《树》期末复习精讲定义·性质·生成树·遍历·题型日期2026年复习导览01基本概念无向树、森林、叶与分支点的定义02性质判定等价刻画与边点计数公式03生成树破圈法与避圈法求最小生成树04二叉树遍历先序、中序、后序与层次遍历05典型题型考点套路归纳与易错点规避SECTION01树的基本概念无回路且连通，是树的两大支柱从定义出发，理清树与森林的边界什么是树连通且无回路，是树的两大必备特征树的定义一个

无回路的连通无向图

称为树定义核心两大特征树中任意两顶点连通，且不存在任何回路。条件辨析缺一不可两个条件缺一不可：只连通有回路不是树；只无回路不连通是森林。结构地位图论基石树是最简单的连通图，也是结构最丰富的图之一。森林与平凡树森林的每个连通分支都是树林森林与树的关系森林一个无回路的无向图，其每个连通分支都是树树与森林树是恰有一个连通分支的森林，森林则可以有多个分支界平凡树与判定边界平凡树仅含一个顶点的树，也称为平凡图判定边界当顶点数大于等于2时，孤立点图因不连通，不是树叶、分支点与顶点的度度数决定了顶点在树中的角色关键结论：顶点数大于等于2的树中，至少有两片叶顶点数大于等于2的树中，至少有两片叶叶（树叶）树中

度数为1

的顶点分支点树中

度数大于等于2

的顶点树的度树中所有顶点度数的

最大值树的直观模型树结构在生活中无处不在家谱树·组织结构图体现层层分明的层级关系文件目录树从根目录出发逐级展开决策树·语法树用分支表示不同选择或结构共同特征这些模型均具备

连通且无回路

的结构特征SECTION02树的性质与判定边数等于点数减一，是树的身份证掌握等价刻画，判定题迎刃而解边数与点数的关系树的边数恰好比顶点数少一m=n−1设树有

n

个顶点、m

条边，则核心公式：直观理解每增加一个顶点，只增加一条边反向判定无回路图满足

m=n−1，必是树应用场景已知点数直接求边数，或据此判断图是否为树树的等价刻画多个条件彼此等价，判定树有多条路径1T连通且无回路2任意两顶点间有唯一路径3连通且边数

m=n−14无回路且边数

m=n−15无回路，任意添加一条新边恰产生一个回路设

T

是n阶

无向简单图以下命题互相等价树中路径为何唯一路径唯一，是树无回路的直接推论路径唯一，是树无回路的直接推论树中任意两顶点之间存在且仅有唯一一条路径反证逻辑若存在两条不同路径，合起来必构成回路，与树无回路矛盾等价表述该结论是"无回路"特征的另一种等价刻画理论支撑为后续生成树、最优化等问题奠定基础树至少有两片叶树的两个端点至少是叶顶点数

n≥2

的树中，至少有两片叶定理与直观理解直观理解树的"端点"必然度为1，否则会延伸出回路可推结论树中分支点数不超过

n−2应用场景常用于构造法证明与树的计数树的判定方法总结先数点边，再查连通与回路第1步数点边先数顶点数n与边数m检查是否满足

m=n−1第2步判据一判据一连通且无回路第3步判据二判据二无回路且

m=n−1第4步判据三判据三连通且

m=n−1三个判据任意一个成立，即可判定该图为树SECTION03生成树与最小生成树破圈去边，避圈添边，殊途同归两种算法，一个目标：权值最小什么是生成树生成树是包含全部顶点的极小连通子图核心定义连通图G的生成子图若是一棵树，则称为G的生成树生成树的三要素4项生成子图连通图G的生成子图若是一棵树，则称为G的生成树顶点覆盖包含G的所有顶点，但只保留

n−1

条边边数关系生成树的边数=顶点数−1极小特性母图中边最少但仍连通的子图生成树一定存在吗连通图必有生成树定理：任何

连通图

都至少存在一棵生成树01求法一破圈法找到回路就删去其中一条边，直到无回路每次删边后仍保持图连通，最终得到生成树02求法二避圈法逐条添加不成回路的边，直到连通推论：n个顶点、m条边的连通图，需删去

m−(n−1)

条边才能得到生成树什么是最小生成树权值之和最小的生成树MST是在连通带权图中，权之和最小的生成树，用于求解铺设线路最短、建设成本最低等最优化问题。核心概念最小生成树基础带权图每条边都赋有一个权重的连通图生成树的权生成树中所有边的权之和最小生成树权之和最小的生成树，简称MST应用场景最优化问题铺设线路最短可用于求解线路铺设的最优化问题建设成本最低可用于求解工程建设的最优化问题避圈法求最小生成树由小到大选边，不构成回路就保留克鲁斯卡尔算法以“从小到大选边、不成环即保留”的贪心策略，得到总权值最小的生成树。—避圈法核心思想1第一步排序将图中所有边按权从小到大排列。2第二步选边依次考察每条边，若加入后不构成回路，则加入生成树。3第三步舍弃若构成回路，则舍弃该边，继续考察下一条。4第四步收束重复直到选够

n−1

条边，即得最小生成树。普里姆算法求生成树从一点生长，每次选最短的外接边每次只选

最短外接边，让生成树从一点逐步生长1步骤01任选顶点选一个顶点作为初始点，加入已选集合2步骤02选最小边在连接已选与未选顶点的边中，选权

最小

的一条加入3步骤03并入顶点把该边另一端的顶点并入已选集合4步骤04重复至全重复直到所有顶点都被选入，得到最小生成树最小生成树求解示例两种算法结果一致，权值相同对比两种经典算法的求解过程，核心都围绕逐步选边与避免回路展开。避圈法避免回路策略逐步选边，避开回路步骤先排序，再判断回路普里姆算法扩展策略逐步扩展，每次取最小外接边步骤先建集合，再逐步扩展两种算法最终得到的最小生成树权值相同，最后核对边数为

n−1VSSECTION04二叉树的遍历根的位置决定次序，左右顺序不变先中后序加层次，四种遍历全掌握二叉树的基础概念每个结点至多两棵子树，且分左右一棵有序树中，每个结点至多分出两棵子树，且左右有严格次序——这是二叉树最根本的结构约束。二叉树每个结点至多有两棵子树的有序树。左右子树两棵子树分别称为左子树和右子树，次序不能颠倒。空与单根二叉树可以为空，也可以只有根结点。特殊形态满二叉树、完全二叉树、斜树。先序遍历先访问根，再左再右二叉树的基础遍历方式，也是其它遍历方法的基石。根

左

右01遍历次序根结点→左子树→右子树02简称简记为

根左右03递归执行访问根→先序遍历左子树→先序遍历右子树04核心特点序列的第一个结点一定是根中序遍历先左，再访问根，最后右中序遍历按

左根右

的次序访问二叉树全部结点遍历规则详解3项遍历次序左子树→根结点→右子树，简称

左根右递归执行中序遍历左子树，访问根，再中序遍历右子树核心特点在二叉排序树中，中序序列是

有序序列后序遍历先左再右，最后访问根后序遍历的序列中，最后一个结点一定是根——子树皆在其前完成访问遍历次序步骤左子树先完成左子树的遍历右子树再遍历右子树的全部结点根结点最后才访问根结点简称记忆左右根按左、右、根的顺序记忆递归执行方式后序遍历左子树递归进入左子树，重复后序逻辑后序遍历右子树左子树完成后，再递归右子树访问根两棵子树处理完后最后访问根结点核心特点规律根在末尾序列的最后一个结点一定是根层次遍历逐层从上到下，从左到右“从根所在层出发，逐层深入，层次遍历展现了二叉树结构性的访问秩序。”次序规则从根所在层开始，逐层向下访问。同层规则同一层内从左到右依次访问。队列实现出队时访问，并把左右孩子入队。结构意义层次遍历体现树的层次结构。四种遍历的对比根的位置不同，是区分四种遍历的关键遍历方式访问顺序先序遍历根→左→右中序遍历左→根→右后序遍历左→右→根层次遍历逐层，从左到右记忆口诀：先中后对应

根在左、中、右

的位置由遍历序列还原二叉树先序加中序，或后序加中序，可唯一确定1还原步骤找根先序遍历：首元素定根后序遍历：末元素定根2还原步骤划分用中序序列划分左右根左侧为左子树3还原步骤递归对左右子树递归还原可唯一确定先序+中序先序首元素定根，中序划分左右后序+中序后序末元素定根，中序划分左右不能唯一确定先序+后序不能唯一确定一棵二叉树对比SECTION05典型题型与易错点题型有套路，陷阱需警惕归纳考点，规避失分点题型一

树的性质计算抓住点边关系，计算题迎刃而解树的性质计算，核心在点与边的数量关系边数直求已知树有

n

个顶点，直接由

m=n−1

求边数。握手定理已知各顶点度数之和，结合握手定理求边数。快速筛选判断某图是否为树，优先用

m=n−1

快速筛选。常见变式求叶的个数、分支点数、树的高度等常见变式。题型二

生成树求解选边避圈，权值和最小求解生成树问题，关键在四个步骤：构造、优化、计算、验证，环环相扣。求生成树破圈法删边或避圈法加边求最小生成树优先用克鲁斯卡尔或普里姆算法计算权值把所选边的权逐条相加验证边数生成树边数必须等于n−1题型三

遍历序列问题定根、划分、递归，三步还原先定根，再借中序划分左右子树，递归处理写出遍历序列给定二叉树，写出先序、中序、后序三种深度优先遍历序列。还原二叉树由两种遍历序列还原二叉树，必须搭配中序。求结点位置求某结点在先序、中序、后序序列中的位置。关键步骤先定根，再借中序划分，递归处理常见易错点梳理概念相近处，往往就是失分点树与森林混淆森林可以不连通，树必须连通条件遗漏忘记树的两个条件，把有回路的连通图误判为树边数记错生成树边数写成n条，应为

n−1

条子树颠倒二叉树左右子树颠倒，导致遍历序列出错还原误区用先序加后序去还原二叉树，二者不能唯一确定本章复习总结概念打底，性质铺路，算法与应用收口本章围绕树结构从概念、性质到算法与技能，形成完整复习闭环复习要点：概念→性质→算法→技能，层层递进；边数=点数−1

是解题关键。核心概念概念打底