【数据结构】二叉树入门全解：从定义、性质到经典真题

一、先搞懂什么是二叉树二叉树Binary Tree是一种特殊的树形结构定义非常清晰它是由nn≥0个结点构成的有限集合满足空树当n0时二叉树为空非空树有且仅有一个根结点除根结点外其余结点分为两个互不相交的子集T₁和T₂分别称为根的左子树和右子树且T₁、T₂本身也是二叉树。核心特点每个结点最多只有 2 棵子树即度最大为 2子树有严格的左右之分顺序不能颠倒左子树和右子树是完全不同的两棵树。二叉树的 5 种基本形态二叉树的结构非常灵活基础形态只有 5 种空二叉树仅有根结点右子树为空只有左子树左子树为空只有右子树左右子树均非空二、二叉树的核心性质解题的 “万能公式”掌握这些性质是解决所有二叉树问题的基础也是考试的核心考点性质 1第 i 层的最大结点数二叉树的第i层根为第 1 层最多有2^(i-1)个结点。验证第 1 层根2^01第 2 层最多 2 个第 3 层最多 4 个完全符合满二叉树的结构。性质 2深度为 k 的二叉树最大结点数深度为k的二叉树最多有2^k - 1个结点。本质等比数列求和124...2^(k-1) 2^k - 1对应满二叉树的结点总数。性质 3叶子结点与度为 2 的结点的关系对于任意非空二叉树若叶子结点数为n₀度为 2 的结点数为n₂则恒有n₀ n₂ 1推导设总结点数为n度为 1 的结点数为n₁则n n₀ n₁ n₂又因为二叉树的边数 总结点数 - 1 n-1同时边数也等于n₁ 2n₂度为 1 的结点贡献 1 条边度为 2 的贡献 2 条联立得n₀ n₁ n₂ - 1 n₁ 2n₂化简后n₀ n₂ 1完美成立。三、特殊二叉树满二叉树 完全二叉树这两种是考试中最常考的二叉树类型必须彻底分清1. 满二叉树定义深度为k且结点总数为2^k - 1的二叉树。特点所有叶子结点都在最后一层除叶子结点外每个结点都有 2 个子结点同深度下满二叉树的结点数、叶子数都是最多的按层序编号根为 1从上到下、从左到右编号为i的结点左孩子为2i右孩子为2i1父结点为⌊i/2⌋。2. 完全二叉树定义深度为k、有n个结点的二叉树当且仅当它的每个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时称为完全二叉树。核心特点判断依据叶子结点只可能出现在最后两层若某结点没有左子树则一定没有右子树上一层没有铺满绝对不能有下一层结点对任意结点若其右分支子孙的最大层次为l则左分支子孙的最大层次必为l或l1。完全二叉树的专属性质解题神器性质 4完全二叉树的深度有n个结点的完全二叉树深度为⌊log₂n⌋ 1向下取整后 1。性质 5层序编号的父子关系对n个结点的完全二叉树按层序编号根为 1每层从左到右对任意结点i1≤i≤n若i1结点i是根无父结点若i1父结点编号为⌊i/2⌋若2i n结点i无左孩子是叶子结点否则左孩子为2i若2i1 n结点i无右孩子否则右孩子为2i1。四、经典真题实战把性质用起来我们结合 3 道历年考研真题手把手教你用性质解题彻底吃透考点。真题 12009完全二叉树结点数最大值题目已知一棵完全二叉树的第 6 层根为第 1 层有 8 个叶结点则该完全二叉树的结点个数最多是 A. 39 B. 52 C. 111 D. 119解题步骤分析结构完全二叉树的叶子结点只能在最后两层因此第 6 层有 8 个叶子说明树的深度有两种可能深度为 6或深度为 7要结点数最多必然取深度 7。计算前 5 层满二叉树的结点数深度为 5 的满二叉树结点总数为2^5 - 1 31个。计算第 6 层的结点数第 6 层最多有2^(6-1) 32个结点。其中 8 个是叶子结点说明剩下32 - 8 24个结点是非叶子结点有子结点。计算第 7 层的最大结点数第 6 层的 24 个非叶子结点每个最多有 2 个子结点因此第 7 层最多有24 × 2 48个结点。总结点数前 5 层 31 第 6 层 32 第 7 层 48 111对应选项 C。真题 22011完全二叉树的叶子结点数题目若一棵完全二叉树有 768 个结点则该二叉树中叶结点的个数是 A. 257 B. 258 C. 384 D. 385解题步骤方法 1利用性质 3 完全二叉树的特点完全二叉树中度为 1 的结点数n₁只能是 0 或 1这是完全二叉树的核心特点。设叶子结点数为n₀度为 2 的结点数为n₂则总结点数n n₀ n₁ n₂ 768由性质 3n₀ n₂ 1→n₂ n₀ - 1代入得n₀ n₁ (n₀ - 1) 768→2n₀ n₁ 769因为2n₀是偶数769 是奇数所以n₁必须为 1奇数才能让等式成立。因此2n₀ 1 769→n₀ 384对应选项 C。方法 2利用完全二叉树层序编号性质完全二叉树的叶子结点是编号大于⌊n/2⌋的所有结点。n768⌊768/2⌋ 384因此叶子结点是编号 385~768共768 - 384 384个直接得出答案。真题 32018满二叉树的结点总数题目设一棵非空完全二叉树 T 的所有叶结点均位于同一层且每个非叶结点都有 2 个子结点。若 T 有 k 个叶结点则 T 的结点总数是 A. 2k-1 B. 2k C. k² D. 2^k-1解题步骤分析树的类型所有叶结点在同一层且每个非叶结点都有 2 个子结点 → 这是一棵满二叉树。满二叉树中叶子结点数n₀ k由性质 3n₀ n₂ 1得度为 2 的结点数n₂ k - 1。满二叉树中没有度为 1 的结点n₁0因此总结点数n n₀ n₁ n₂ k 0 (k-1) 2k - 1对应选项 A。补充验证深度为 h 的满二叉树叶子数k2^(h-1)总结点数2^h - 1 2×2^(h-1) - 1 2k - 1完全一致。五、总结二叉树核心考点速记表格知识点核心公式 / 结论二叉树性质 3n₀ n₂ 1所有二叉树通用满二叉树深度 k结点数2^k - 1叶子数2^(k-1)总结点数2×叶子数 - 1完全二叉树度为 1 的结点数只能是 0 或 1叶子结点为编号 ⌊n/2⌋的结点深度⌊log₂n⌋1完全二叉树父子关系父结点⌊i/2⌋左孩子2i右孩子2i1二