从零开始学习数据结构|学习数据结构--第四章（树与二叉树（二叉树的顺序存储和链式存储））数据结构|顺序存储|链式存储

第四章：树与二叉树（二叉树的存储结构） 1.二叉树的顺序存储二叉树的顺序存储
用一组连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。
思考为啥是存储完全二叉树？

文章图片

这里正常情况存储的时数据，我们这里理解就存储编号了。但是如果使用上图存储，我们如何表示二叉树的逻辑关系呢？
二叉树的逻辑关系：1 是 2 和 3的双亲结点，2 3 是 1 的孩子结点。
这样的逻辑关机该如何维护呢？
我们在学习线性表的时候，我们知道线性表的地址是连续的，也就是线性表的下一个结点就是它下一个存储单元存放的元素，但是如果按照上图存储，一个节点的孩子结点一定是它接下来存放的元素吗？
二叉树逻辑关系的表示方法：
我们知道：在完全二叉树中依次编号,对于结点 i :若存在左孩子,则编号为 2i; 若存在右孩子,则编号为 2i+1 。
所以我们使用这样的性质来实现二叉树逻辑关系。

文章图片

在这里数组下标和结点的标号是一致的，这样我们就能使用下标来找到孩子结点下标了。这里为了更方便的对应完全二叉树性质，所以数组的第一个位置我们没有存储结点，当然其实也是可以存储的只不过找孩子结点的方式需要改变：左孩子 2i+1,右孩子2i+2 。其实我们在进行实际应用的是偶，0这个位置是会存储节点的个数的。

文章图片

注意上面都是说的是完全二叉树

从零开始学习数据结构|学习数据结构--第四章（树与二叉树（二叉树的顺序存储和链式存储））

文章图片

例如上图，是非完全二叉树，我们按照数组第一个位置空出来然后从上到下，从左到右，将结点依次填入数组，如上图。此时我们按如果按照上面的性质找3结点的左孩子为 2x3=6，按理说应该是存储在下标为6的地方，可以是实际上存储到下标为5的地方，这样就无法通过之前的方法来表示逻辑关系了。
那么该采用什么方法呢？
其实只需要对方法改进一下就行了。我们将这颗非完全二叉树 补成 完全二叉树 ，即将 2 号结点补一个右孩子即可，然后进行存放。因为添加了一个不存在的空结点，所以在数组中用 0 表示

文章图片

此时就表示了逻辑关系。虽然我们这样完成了二叉树的顺序存储的而且表示了逻辑关系，但是这样的存储方法是有一个弊端的。

文章图片

如上图，我们如果将上面的二叉树使用顺序存储，则需要将其补成完全二叉树，这样我们就浪费了很多的存储空间来进行存放。所以：
顺序存储最坏情况会非常浪费存储空间，比较适合完全二叉树。
因此我们在存储二叉树的时候往往使用链式存储。

文章图片

2.二叉树的链式存储二叉树的链式存储：用链表来存放一棵二叉树,二叉树中每个结点用链表的一个链结点来存储。
因为是二叉树，所以每个结点都可能有一个左孩子和右孩子，我们使用链表存放，所以可以每个结点可以定义一个数据域和两个指针域，两个指针域用来分别存储左结点和右结点。

文章图片

我们举一个例子来看看具体是如何存放的。

文章图片

因为某些结点没有左孩子或者右孩子，所以会出现空的指针域的情况，关于空指针域的个数我们有如下规律：
含有n个结点的二叉链表中，有 n+1 个空链域。
上面的结论是通过：2n-(n-1) 这个式子得到。式子的解释：
2n 表示每一个结点都有两个指针域，那么共n个结点，则总共 2n个指针域。我们要想的到空链域，则需要减去指针非空指针域。而非空指针域的个数其实就是孩子结点，有一个孩子结点，则需要一个指针域指向，而总共多少个孩子结点呢？总共为 n-1 个，因为 n 个结点中除了第一个结点是二叉树根节点外，其余都是孩子结点。故得到：2n-(n-1)=n+1
3.总结本次学习了二叉树的顺序存储和链式存储，在实际应用中，对于顺序存储我们可能直接在数组的下标为1的位置开始存储二叉树，下标为0的位置存储二叉树的信息。
链式存储中，我们也可能需要三个指针域，除了指向左右孩子结点的指针域，还需要一个指向双亲结点的指针域。
关于数据结构的知识持续更新中，下次将会讲解：二叉树的遍历和线索二叉树，欢迎大家的关注，也可以关注同名公众号理木客
【从零开始学习数据结构|学习数据结构--第四章（树与二叉树（二叉树的顺序存储和链式存储））】