【数据结构】二叉树小题

一、真题 1前序 后序遍历反推中序2011 年核心原理二叉树的遍历规则前序遍历根节点 → 左子树 → 右子树中序遍历左子树 → 根节点 → 右子树后序遍历左子树 → 右子树 → 根节点关键结论仅通过前序 后序遍历无法唯一确定一棵二叉树但可以确定根节点、父子关系以及每个节点的子树方向左 / 右。若前序序列与后序序列完全逆序说明这棵二叉树是单支树每个节点最多只有一个子节点要么全是左孩子要么全是右孩子。解题分析已知前序[1,2,3,4]、后序[4,3,2,1]可直接确定根节点是1前序第一个后序最后一个2是1的子节点3是2的子节点4是3的子节点整棵树为单支链结构我们逐一验证选项A 选项1,2,3,4对应右单支树每个节点只有右孩子结构1→右孩子2→右孩子3→右孩子4前序1,2,3,4后序4,3,2,1符合条件 ✅B 选项2,3,4,1对应左单支树 右单支混合结构1的左孩子2→右孩子3→右孩子4前序1,2,3,4后序4,3,2,1符合条件 ✅C 选项3,2,4,1若中序为3,2,4,1则根1的左子树为[3,2,4]前序中1之后的子序列为[2,3,4]后序中1之前的子序列为[4,3,2]此时2作为左子树的根中序中2的左子树为[3]、右子树为[4]则2有两个孩子不再是单支树前序会变为1,2,3,4但后序会变为3,4,2,1与题目后序4,3,2,1矛盾 ❌D 选项4,3,2,1对应左单支树每个节点只有左孩子结构1→左孩子2→左孩子3→左孩子4前序1,2,3,4后序4,3,2,1符合条件 ✅答案C二、真题 2先序与中序序列相同的条件2017 年核心原理先序遍历根 → 左 → 右中序遍历左 → 根 → 右若两者序列完全相同说明遍历顺序完全一致即左子树必须为空否则先序会先访问根中序会先访问左子树序列必然不同。解题分析若每个非叶节点只有右子树左子树为空先序遍历根 → 空 → 右子树根 → 空 → ...中序遍历空 → 根 → 右子树根 → 空 → ...两者序列完全一致 ✅若只有左子树先序为根→左→右中序为左→根→右序列必然不同 ❌度为 1 的节点可能是左孩子或右孩子若为左孩子则序列不同 ❌度为 2 的节点有左右子树序列必然不同 ❌答案B补充验证我们用 3 个节点的树举例右单支树1→右2→右3先序1,2,3中序1,2,3完全一致左单支树1→左2→左3先序1,2,3中序3,2,1完全相反三、真题 3二叉树顺序存储的最小单元数2020 年解析1. 二叉树顺序存储的核心规则二叉树的顺序存储是按照完全二叉树的层序遍历顺序将结点依次存入数组中。对于完全二叉树数组大小刚好等于结点数无浪费对于非完全二叉树必须为缺失的结点预留空的存储单元以保证父子结点的下标关系左孩子下标 2× 父结点下标右孩子下标 2× 父结点下标 1成立。2. 高度为 h 的二叉树的顺序存储最大单元数高度为h的二叉树顺序存储需要的最大存储单元数等于高度为 h 的满二叉树的结点总数公式为2h−1本题中树的高度为 5因此满二叉树的结点总数为25−132−1313. 为什么不能选更小的数题目要求的是存放该二叉树需要的存储单元至少是多少这里的 “至少” 是指无论这棵高度为 5、10 个结点的二叉树是什么形态都能存下的最小通用空间。高度为 5 的二叉树最深层的结点在第 5 层其在顺序存储中的下标最大为25−131因此数组必须至少开到 31 个单元才能覆盖所有可能的结点位置。选项 B (16)、C (15)、D (10) 都无法覆盖高度为 5 的二叉树的最大下标因此不可能满足要求。答案A. 31补充说明顺序存储的本质是按完全二叉树的结构映射因此树的高度直接决定了数组的最小长度与实际结点数无关只要高度确定数组长度至少为2h−1。本题中 10 个结点是干扰项核心约束是高度为 5因此直接用满二叉树公式计算即可。四、考点总结与解题技巧核心考点梳理考点核心结论解题技巧遍历反推前序 后序无法唯一确定树中序是唯一能确定树的关键先找根再分左右子树递归验证遍历序列相同先序 中序 → 无左子树只有右子树中序 后序 → 无右子树只有左子树直接用遍历规则推导排除法验证顺序存储按完全二叉树层序编号存储高度 h 的树需2^h -1个单元区分实际节点数和预留单元数不要混淆避坑指南单支树的遍历特性全右单支树的先序 中序全左单支树的后序 中序前序与后序逆序顺序存储的本质是为完全二叉树设计的非完全二叉树必须补空节点因此单元数远大于实际节点数遍历反推的边界前序 后序只能确定根和父子关系无法确定子树方向因此会有多种可能的中序序列