树的应用 —— 二叉树的存储结构_完全二叉树的存储结构

树的应用 —— 二叉树的存储结构

二叉树的存储结构分为两种：顺序存储结构和链式存储结构

① 顺序存储结构

二叉树可以采用顺序存储结构，按完全二叉树的节点层次编号，依次存放二叉树中的数据元素。

完全二叉树很适合顺序存储结构，下面左图中的完全二叉树的顺序存储结构如右图所示。

普通二叉树进行顺序存储时需要被补充为完全二叉树，在对应的完全二叉树没有孩子的位置补0，其顺序存储结构如下图所示

显然，普通二叉树不适合采用顺序存储结构，因为有可能在补充为完全二叉树的过程中，补充了太多的0，而浪费了大量的空间。

因此普通二叉树可以使用链式存储结构。

② 链式存储结构

二叉树最多有两个“叉”，即最多有两棵子树。

二叉树采用链式存储结构时，每个节点都包含一个数据域，存储节点信息；还包含两个指针域，指向左右两个孩子。

这种存储方式被称为二叉链表，结构如下图所示。

二叉链表节点的结构体定义如下图所示

那么下面左图中的二叉树可被存储为二叉链表形式，如下面右图所示。

一般情况下，二叉树采用二叉链表存储即可，但是在实际问题中，如果经常需要访问双亲节点，二叉链表存储则必须从根节点出发查找其双亲节点，这样做非常麻烦。

例如在上图中，如果想找F的双亲，就必须从根节点A出发，访问C，再访问F，此时才能返回F的双亲为C。

为了解决该问题，可以增加一个指向双亲节点的指针域，这样每个节点就包含三个指针域，分别指向两个孩子节点和双亲节点，还包含一个数据域，存储节点信息。

这种存储方式被称为三叉链表，结构如下图所示。

三叉链表节点的结构体定义如下图所示。

那么下面左图中的二叉树也可以被存储为三叉链表形式，如下面右图所示。