三、二叉树的存储结构

image.png

一、顺序存储结构

我们顺序的存储这个二叉树的数据：

image.png

image.png

我们针对图中的树可以得出这样的关系，但是这仅针对于完全二叉树，不针对所有的树，例如下面的这个树就不行：

image.png

链式存储结构

image.png

如图我们使用链表的形式来存储二叉树的数据，其中我们有三个域，一个数据域，左边的指向左孩子，右边的指向右孩子。

下面就是C语言中的二叉链表存储结构：

image.png

image.png

但是有这样一个问题，这个存储结构是可以存储左孩子和右孩子，但是如果一个节点有多余两个孩子的节点怎么办？ 这样的话就得换一种思路了：

我们想其实链式结构最主要的就是我们需要由父节点可以找到他的孩子节点。
如图所示：

image.png

可以轻易的看到啊原本的结构，A1与A2，A3，A4都有直接的关系，右图则是按照层级的，A1仅与A2关联，然后A2与A3，A4关联即可，他们属于第二级然后以此类推，我们要达到的目的就是由父节点可以找到所有的孩子节点即可。

然后就推导出这样的数据结构：

image.png

我们使用一个指针指向一个孩子节点，然后另一个指针指向他的兄弟节点即可

这个就是树的孩子兄弟存储结构

image.png