（数据结构）二叉树的顺序存储结构
二叉树的存储结构有两种，分别为顺序存储和链式存储
·
二叉树的存储结构
二叉树的存储结构有两种，分别为顺序存储和链式存储，此篇文章介绍顺序存储
二叉树的顺序存储
二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树
重点！！！
顺序存储只适用于完全二叉树（包括满二叉树），因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树
满二叉树的限制条件比完全二叉树更严苛，也就是说如果此树是满二叉树，那么它一定也是完全二叉树
普通二叉树转完全二叉树的方法
给二叉树额外添加一些节点，将其拼凑成完全二叉树
图 1 普通二叉树的转化
如上图 1，左侧是普通二叉树，右侧是转化后的完全（满）二叉树
解决转换问题后得解决存储问题
完全二叉树的顺序存储，仅需从根节点开始，按照层次依次将树中节点存储到数组
图 2 完全二叉树示意图
如上图 2 的完全二叉树，其存储状态如下图 3：
图 3 完全二叉树存储状态示意图
同样，存储由普通二叉树转化来的完全二叉树，其存储状态如下图 4：
图 4 普通二叉树存储状态示意图
实现存储过程后需要考虑还原问题
完全二叉树具有此性质，将树中节点按照层次并从左到右依次标号，若节点 有左右孩子，则其左孩子节点为
，右孩子节点为
，此性质可用于还原数组中存储的完全二叉树
但是实现此部分代码，需要对二叉树进行层次遍历！！！
我将在后面的文章中补充！！！
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
5
0- 0
已为社区贡献9条内容
所有评论(0)