阅读:0       作者:严长生

二叉树的顺序存储原理及实现过程

二叉树的顺序存储,实际上就是使用数组存储二叉树。

使用数组存储二叉树的实现思想是将二叉树从根节点按照层次顺序依次存储在数组中,但需要注意的是,此方式只适用于完全二叉树,如果要使用数组存储普通二叉树,需要提前将该二叉树转化为完全二叉树。

完全二叉树,即二叉树除了最后一层节点外,其余各节点都既有左节点和右节点,最后一层的节点满足从左到右依次分布,则此二叉树为完全二叉树。普通二叉树转化为完全二叉树的方法是将不满足条件的节点添加左孩子或右孩子(节点存储的数据为一个特殊值,例如 0),令其整体结构上表现为一个完全二叉树。


图 1 完全二叉树

例如,图 1(A) 和 (B) 都是二叉树,但图 1(A) 是完全二叉树,(B) 由于最后一层不符合从左往右依次分布的要求,所以不是完全二叉树,只是一个普通的二叉树。

因此,存储图 1(A) 时,数组中存储为:


如果图 1(B) 也采取顺序存储的方式,就需要将其转化成完全二叉树,其转化过程如下:


图 2 普通二叉树转完全二叉树

图 2 中,转化后的二叉树中,数据元素 0 表示此位置没有数据。将转化后的完全二叉树按照层次并从左到右的次序存储到数组中: