大学数据结构《树与二叉树》案例教学课件

大学数据结构《树与二叉树》案例教学课件树·二叉树·遍历·哈夫曼授课时间：2026年案例教学课程导览01树与二叉树基础从生活案例到术语体系02二叉树性质与存储核心性质与两种存储结构03遍历算法与线索化四种遍历方式与线索二叉树04树与森林的转换树、森林与二叉树的相互转换05经典应用与综合案例哈夫曼树与知识迁移树与二叉树基础从生活案例认识树形结构树形结构无处不在，从目录到家族谱系01树形结构无处不在从熟悉场景理解树形结构一个前驱、多个后继，形成

层次关系文件系统目录层层嵌套，子目录从属于父目录。家族谱系祖辈向下分支出子孙，代际关系清晰。组织机构校长到院长到教师到学生，一对多隶属。与线性表的一对一不同，树描述的是数据之间的一对多层次关系，是典型的非线性结构。树的基本术语体系掌握术语是理解树结构的第一步术语含义节点树中的一个数据元素根节点没有前驱的唯一节点度节点拥有的子树个数叶子度为0的节点层次根为第1层，向下递增深度树中节点的最大层次森林若干棵互不相交的树记忆要点：节点的

度

决定分支多少，树的

深度

反映纵向高度。二叉树的定义与形态每个节点最多两棵子树，且左右有序左子树与右子树不能颠倒，这是二叉树与普通度为2的树的关键区别；理解这一有序性，是后续讨论遍历顺序的基础。二叉树是度为

2

的有序树，每个节点至多有两个孩子空树形态一没有任何节点的空形态仅有根节点形态二只存在一个根节点根只有左子树形态三根节点只有左子树根只有右子树形态四根节点只有右子树根左右子树都有形态五根节点左右子树都有特殊二叉树辨析满与完全，一字之差含义不同满与完全，一字之差，含义却截然不同满二叉树每一层都达到最大节点数叶子全在最底层完全二叉树仅最后一层可不满节点靠左连续排列判别口诀满二叉树一定是完全二叉树，反之不成立。从上到下、从左到右依次编号，编号连续无空缺即为完全二叉树。完全二叉树的这一特性，使其顺序存储效率最高。VS二叉树的性质与存储掌握性质，理解存储本质性质是理解二叉树结构的钥匙02二叉树的核心性质三条性质是推导与计算的基石性质内容性质1第i层最多有

2^(i-1)

个节点性质2深度为h的二叉树最多有

2^h-1

个节点性质3叶子数

n0=n2+1（度为2的节点数加1）三条性质环环相扣，共同刻画了二叉树的规模边界性质3常在考试中反向使用：已知叶子数即可推出度为2的节点数由性质2可知，同样节点数下，树越矮查找路径越短节点数随高度指数增长高度每增加1，满二叉树节点数近乎翻倍，呈指数增长。高度与最大节点数高度11高度23高度37高度415高度531指数增长意味着，用较小的树高就能容纳大量数据，这正是二叉树高效的组织能力。顺序存储的适用与局限数组存储简洁，但空间代价明显顺序存储适合

完全二叉树，对一般二叉树则不够经济。下标关系节点i的左孩子为

2i节点i的右孩子为

2i+1节点i的双亲为

i除以2取整优缺点对比优点：定位便捷，无需指针，父子关系可计算缺点：普通二叉树需补空节点占位，极端单支树浪费大量空间链式存储的灵活表达指针描述结构，灵活且不浪费二叉链表组成：左指针、数据、右指针特点：结构紧凑，常用三叉链表组成：左指针、数据、右指针、双亲指针特点：便于找双亲链式存储既灵活又不浪费，是二叉树的主流表示方式含

n

个节点的二叉链表共有

2n

个指针域，实际使用

n-1

个，因此存在

n+1

个空指针这一闲置资源启发后续线索二叉树VS遍历算法与线索化遍历是操作二叉树的核心四种遍历方式，递归与迭代并重03先序中序与后序遍历根节点访问时机的不同，决定了三种顺序记牢访问根节点的时机，就能准确写出任意二叉树的遍历序列。先序遍历访问顺序根→左子树→右子树根节点最先访问根左右中序遍历访问顺序左子树→根→右子树根节点居中访问表达式a+b恰好还原中缀表达式左根右后序遍历访问顺序左子树→右子树→根根节点最后访问左右根层序遍历与队列应用逐层访问，队列是不可或缺的帮手层序遍历流程1根节点入队2队头节点出队并访问3左右孩子依次入队4重复至队列为空广度优先层序遍历属于广度优先，与三种深度优先形成对照。先入先出队列的先入先出特性，保证同层节点按从左到右顺序处理。借助队列，层序遍历得以简洁实现，是队列的经典应用场景。遍历序列的互推技巧会写序列，也要会由序列还原树掌握这一方法，就能在序列与树结构之间自由转换先序+中序→可唯一确定一棵二叉树先序首节点定位根中序中根的位置划分左右子树区间递归即可还原唯一结构可唯一确定后序+中序→可唯一确定一棵二叉树后序末节点定位根中序中根的位置划分左右子树区间递归即可还原唯一结构可唯一确定先序+后序→无法唯一确定先序与后序均可定位根缺少中序无法划分左右子树区间左右子树边界存在多种可能无法唯一确定遍历算法的应用举例遍历不止于输出，更是求解的基础树的众多操作，本质上都是遍历的变体——以五种常见应用为例。许多树的应用本质上都是遍历的变体，掌握遍历即掌握了操作的通用骨架。统计节点数任一遍历中计数加一即可。求树的深度递归取左右子树深度较大者加一。复制二叉树先序递归生成新节点。判断相似递归比较两树结构。输出表达式中序输出中缀，后序输出后缀。线索二叉树的提出让闲置空指针指向前驱与后继线索化把浪费的空域变成有用的导航指针，使遍历无需借助栈二叉链表存在

n+1

个空指针，白白闲置n+1个空指针二叉链表中白白闲置的空域这些空域正是线索化的用武之地01利用规则左空指针指向前驱，右空指针指向后继02标志位增设标志位

ltag

与

rtag：为0表示指向孩子，为1表示指向线索03线索分类按遍历顺序不同，可分为先序、中序、后序线索二叉树04线索化价值把浪费的空域变成有用的导航指针，遍历无需借助栈中序线索化的实现中序线索化，遍历不再用栈1按中序遍历访问各节点遍历顺序为线索化提供前驱依据2左指针为空，置ltag为1并指向前驱标记空左指针3前驱右指针为空，置rtag为1并指向当前节点标记空右指针4用指针始终记录前一个访问节点始终保存前驱线索化后，找前驱和后继都可在

常数时间

内完成遍历时无需递归栈，节省空间，适合频繁遍历的场合把空指针利用到极致，正是线索二叉树的设计智慧树与森林的转换转换规则打通树与二叉树掌握转换，灵活应对不同结构04树转换为二叉树掌握三步法，树变二叉树加线在所有相邻兄弟节点之间连一条线抹线对每个节点，只保留其与第一个孩子的连线旋转以根为轴，将树顺时针旋转，调整层次左孩子右兄弟森林转换为二叉树森林转二叉树，根与根相连森林转二叉树后，根的

右子树

反映原森林中的树间关系若二叉树根结点有右子树，说明它来自一个森林掌握这一规则，就能在森林与二叉树间自由转换。1步骤01每棵树分别转换逐棵处理先将森林中每一棵树分别转换为二叉树2步骤02根与根相连依次相连从第一棵树的根出发依次把后一棵树的根作为前一棵根的

右孩子

相连3步骤03得到完整二叉树完成转换连接后即得到一棵完整的二叉树二叉树还原树与森林逆用口诀，二叉树还原为树还原与转换互为逆过程，反复练习即可熟练切换。还原规则：左孩子连双亲右链，去掉双亲到右孩子连线还原规则01某节点是其双亲的左孩子，则把该节点的右孩子、右孩子的右孩子等都与双亲相连02最后去掉原双亲到右孩子的连线判定方法01若二叉树根无右子树，还原为一棵树02若二叉树根有右子树，沿右链断开，还原为森林树与森林的遍历树与森林的遍历，映射到二叉树树遍历→二叉树遍历

对应关系先根遍历

二叉树先序遍历后根遍历

二叉树中序遍历森林先序遍历

二叉树先序森林中序遍历

二叉树中序树无中根遍历，需与二叉树中序区分理清对应关系，就能借助二叉树的遍历算法处理一切树结构。经典应用与综合案例从理论走向实际应用哈夫曼编码，让树结构发挥价值05哈夫曼树的构造每次选两个最小权值合并1组成森林把每个带权节点看作一棵单节点树，组成森林2合并最小从森林中选出权值最小的两棵树合并，新根权值为二者之和3放回森林将新树放回森林，重复步骤24构造完成直到森林中只剩一棵树，即为哈夫曼树哈夫曼树的构造体现了贪心思想，是树结构最经典的应用之一。带权路径长度

WPL

越小，编码效率越高权值越大的节点往往离根越近哈夫曼编码的实现左0右1，编码无歧义哈夫曼编码广泛应用于文件压缩与通信传输，是树结构服务现实的典范4项分支记法从根到每个叶子的路径上，左分支记

0，右分支记

1路径即编码每个字符对应一条从根到叶的路径，即为它的哈夫曼编码前缀编码由于字符都在叶子节点，任一编码都不是其他编码的前缀，称为

前缀编码长短分配高频字符编码短，低频字符编码长，整体平均码长最短二叉排序树的应用左小右大，中序即有序若插入序列本身有序，树会退化为单支链表，查找降为线性级。这一缺陷催生了平衡二叉树。二叉排序树以有序性换查找效率，中序遍历即得有序序列，但退化为单支链表时查找降为线性级定义与关键性质2项定义左子树上所有节点小于根，右子树上所有节点大于根关键性质中序遍历结果为递增有序序列操作要点2项查找逐层比较，平均时间复杂度为对数级插入、删除均需维持有序性平衡二叉树的引入用平衡因子守住院子树的势均力敌平衡机制使树高维持在对数级，保证查找始终高效平衡查找树的核心价值任意节点左右子树高度差不超过1高度差即平衡因子，取值-1、0、1插入导致失衡时，通过旋转恢复平衡常见旋转：左左型、右右型、