概述
二叉树的存储结构主要分为顺序存储结构和链式存储结构。
1. 顺序存储结构
它是用一组连续的存储单元存储二叉树的数据元素，因此，必须把二叉树的所有结点安排成为一个恰当的序列。
为了在这个序列中的能反映出结点相互位置之间的逻辑关系，可用编号的方法，即对二叉树按完全二叉树进行编号，然后用一维数组存储，其中编号 为i的结点存储在数组中下标为i的分量中，该方法称为“以编号为地址”策略，该策略会从树根起，自上层至下层，每层自左至右的给所有结点编号。
该策略的缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树却需要2^h -1个结点存储空间，而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好。
对于完全二叉树来说，采用以编号作为数组的下标的方法将结点存入一位数组中，也就是将编号为i的结点存入一维数组的以i为下标的数组元素中，这种情况下，不仅节省内存，结点的位置确定也很方便。
对于非完全二叉树，则用某种方法将其转化为完全二叉树，为此可增设若干个虚拟结点，这种情况下对存储空间浪费极大。
2. 链式存储结构
二叉链表中结点不仅包含数据域，还包含两个指针域，一个是左孩指针，指向其左孩结点，另一个是右孩指针，指向其右孩结点。
在含n个结点的二叉链表中有2n个指针域，其中 n-1个用来指向结点的左右孩子，其余n+1个空链域。
三叉链表的结点中会多一个指向父结点的指针。
以下是三叉链表的结构表现形式。
最后
以上就是聪慧斑马为你收集整理的数据结构与算法 －二叉树的存储结构的全部内容，希望文章能够帮你解决数据结构与算法 －二叉树的存储结构所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复