二叉树的顺序存储结构瞧了无师自通

发布时间：2022-07-07 10:08 所属栏目：51 来源：互联网

导读：二叉树的存储结构有两种，分别为顺序存储和链式存储。本节先介绍二叉树的顺序存储结构。二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。需要注意的是，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以使用顺序表存储。因此，如果我们

　　二叉树的存储结构有两种，分别为顺序存储和链式存储。本节先介绍二叉树的顺序存储结构。

　　二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。需要注意的是，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以使用顺序表存储。因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。
　　有读者会说，满二叉树也可以使用顺序存储。要知道，满二叉树也是完全二叉树，因为它满足完全二叉树的所有特征。

　　解决了二叉树的转化问题，接下来学习如何顺序存储完全（满）二叉树。

　　完全二叉树的顺序存储，仅需从根节点开始，按照层次依次将树中节点存储到数组即可。

　　由此，我们就实现了完全二叉树的顺序存储。

　　不仅如此，从顺序表中还原完全二叉树也很简单。我们知道，完全二叉树具有这样的性质，将树中节点按照层次并从左到右依次标号（1,2,3,...），若节点 i 有左右孩子，则其左孩子节点为 2*i，右孩子节点为 2*i+1。此性质可用于还原数组中存储的完全二叉树，也就是实现由图 3 到图 2、由图 4 到图 1 的转变。
　　编写本节实现代码，需要对二叉树进行层次遍历，这个知识点本章有单独一节做详细介绍，这里不再给出具体的代码实现。

（编辑：ASP站长网）

二叉树的顺序存储结构 瞧了无师自通

二叉树的顺序存储结构瞧了无师自通