【数据结构】二叉树的存储结构(顺序/链式)
考点频率★★★★☆选择题常考是理解二叉树遍历和操作的基础难度⭐⭐建议重点掌握顺序存储的适用范围完全二叉树和链式存储的节点结构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本专栏日更点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #二叉树 #顺序存储 #链式存储 #数据结构 #软考备考

相关新闻

第6章 时域递归滤波:IIR滤波器在视频降噪中的应用

第6章 时域递归滤波:IIR滤波器在视频降噪中的应用

作者:一位在ISP领域摸爬滚打十余年的算法工程师 “纸上得来终觉浅,绝知此事要躬行。”——这门课的每一行代码,都希望你亲自跑一遍。 从原理到代码,从理论到工程落地 本课程共30章,系统讲解ISP核心算法——多帧降噪、HDR合成、夜景算法的原理、实现与调优。 每章包含:原理…

2026/11/20 15:40:28 阅读更多 →
线程中断-interrupted方法

线程中断-interrupted方法

一、没有中断机制,代码会出什么问题?假设 Java 没有 interrupt(),你要怎么让一个正在运行的线程停下来?方案 1:用一个 volatile boolean 标志位class Worker implements Runnable {private volatile boolean running …

2026/11/20 15:40:28 阅读更多 →
PD Sink芯片怎么选?从耐压、外围和协议三方面看懂ECP5702的优势

PD Sink芯片怎么选?从耐压、外围和协议三方面看懂ECP5702的优势

分析:以常见的20V/3A快充场景为例,我们需要特别关注三个致命参数:工作耐压值外围电路复杂度协议支持灵活性(一)首先是工作耐压,决定了芯片在高压快充场景下的可靠性。假设你的设备只用了耐压12V的芯片&…

2026/11/16 23:13:14 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/19 21:38:27 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/19 21:38:49 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/19 21:39:09 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/19 21:36:50 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/19 21:37:45 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/19 21:36:20 阅读更多 →

日新闻

周新闻

月新闻