考点频率★★★★☆选择题常考是理解二叉树遍历和操作的基础难度⭐⭐建议重点掌握顺序存储的适用范围完全二叉树和链式存储的节点结构1️⃣ 存储结构概述在上一篇文章中我们学习了二叉树的五大性质。但光有性质还不够——数据最终要存到计算机里才能用。二叉树的存储方式主要有两种顺序存储用数组存储适合完全二叉树链式存储用链表存储适合所有二叉树打个比方顺序存储就像固定座位的电影院——每个座位数组下标对应一个固定位置适合人员固定完全二叉树的场景。链式存储就像自由入座的教室——每个人节点记住自己左边和右边是谁灵活性高适合任意形状的群体任意二叉树。2️⃣ 顺序存储Sequential Storage2.1 核心思想将二叉树的节点按照从上到下、从左到右的顺序依次存储到一维数组中。节点在数组中的下标位置直接反映了它在树中的逻辑位置。基于的性质完全二叉树的编号规律性质5——对于编号为i ii的节点左子节点位置2 i 2i2i右子节点位置2 i 1 2i 12i1父节点位置⌊ i / 2 ⌋ \lfloor i/2 \rfloor⌊i/2⌋2.2 存储规则规则说明数组下标从1开始或从 0 开始考试常考从1开始下标1存储根节点节点i ii的左子节点存储在2 i 2i2i如果2 i ≤ n 2i \le n2i≤n节点i ii的右子节点存储在2 i 1 2i12i1如果2 i 1 ≤ n 2i1 \le n2i1≤n空节点用特殊值如#或0占位保持数组位置的对应关系示例完全二叉树1 / \ 2 3 / \ \ 4 5 6顺序存储为[1, 2, 3, 4, 5, 6]下标从1开始2.3 顺序存储的适用场景适用场景原因完全二叉树节点位置紧凑数组空间利用率高满二叉树所有位置都被填满空间利用率100%2.4 顺序存储的痛点考点对于一般二叉树非完全二叉树顺序存储会浪费大量空间。1 / \ 2 3 / \ 4 5顺序存储[1, 2, 3, 4, #, #, 5]中间两个空位用#占位关键点一般二叉树如果用顺序存储必须把空缺的位置也用特殊值占位导致数组中有大量空闲空间。最坏情况下一棵深度为k kk的二叉树即使只有k kk个节点也需要2 k − 1 2^k - 12k−1长度的数组。这就是为什么一般二叉树不用顺序存储。3️⃣ 链式存储Linked Storage3.1 核心思想用链表来存储二叉树每个节点包含数据域和两个指针域分别指向左子节点和右子节点。节点之间通过指针连接物理上可以分散存储。3.2 节点结构typedefstructBiTNode{intdata;// 数据域structBiTNode*lchild;// 左子节点指针structBiTNode*rchild;// 右子节点指针}BiTNode,*BiTree;3.3 三种遍历方式在链式存储中的实现遍历方式访问顺序代码逻辑伪代码先序遍历Preorder根 → 左 → 右访问根; 先序(左子树); 先序(右子树)中序遍历Inorder左 → 根 → 右中序(左子树); 访问根; 中序(右子树)后序遍历Postorder左 → 右 → 根后序(左子树); 后序(右子树); 访问根示例对上面的树进行遍历1 / \ 2 3 / \ \ 4 5 6先序1 2 4 5 3 6中序4 2 5 1 3 6后序4 5 2 6 3 14️⃣ 顺序存储 vs 链式存储对比表对比项顺序存储链式存储二叉链表底层结构数组链表指针适用范围完全二叉树/满二叉树所有二叉树存储密度完全二叉树高一般二叉树低大量空位低每个节点两个指针约50%查找父节点直接计算⌊ i / 2 ⌋ \lfloor i/2 \rfloor⌊i/2⌋O ( 1 ) O(1)O(1)需要遍历O ( n ) O(n)O(n)查找子节点直接计算2 i 2i2i或2 i 1 2i12i1O ( 1 ) O(1)O(1)通过指针访问O ( 1 ) O(1)O(1)插入/删除困难需要移动大量元素简单修改指针空间浪费一般二叉树浪费严重每个节点固定指针开销5️⃣ 经典例题例题1顺序存储的适用性以下哪种二叉树最适合采用顺序存储A. 满二叉树B. 只有右子树的二叉树C. 深度为10的任意二叉树D. 每个节点只有一个子节点的二叉树解析满二叉树和完全二叉树最适合顺序存储因为数组中没有空位浪费。满二叉树的节点编号是连续的可以100%利用数组空间。选A。例题2三叉链表的改进如果需要在二叉树中频繁查找某个节点的父节点应该选择什么存储结构A. 顺序存储B. 普通二叉链表无父指针C. 三叉链表增加父指针D. 循环链表解析三叉链表在普通二叉链表的基础上增加了父指针查找父节点时不需要遍历直接访问即可。软考中考到这个概念时知道它的作用是快速查找父节点即可。选C。例题3判断顺序存储结构适用于所有类型的二叉树。 解析错误。顺序存储只适用于完全二叉树和满二叉树对于一般二叉树会造成大量空间浪费。6️⃣ 记忆口诀完全二叉用数组下标计算找父母。一般二叉用链表左右指针指向清楚。先序根左右中序左根右后序左右根。7️⃣ 小测验评论区对答案对于一棵深度为h hh的完全二叉树采用顺序存储时数组的长度至少为 。A.h hhB.2 h − 1 2^{h-1}2h−1C.2 h − 1 2^h - 12h−1D.2 h − 2 2^{h} - 22h−2本专栏日更点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #二叉树 #顺序存储 #链式存储 #数据结构 #软考备考