深入学习二叉树：二叉树基础3

问题导读


1.顺序存储一般适用于什么类型二叉树？
2.顺序存储二叉树，可能存在什么问题？
3.顺序存储不能满足二叉树的存储需求，用什么存储更合适？


上一篇：
深入学习二叉树：二叉树基础2
https://www.aboutyun.com/forum.php?mod=viewthread&tid=30539


3.7 二叉树的存储结构
3.7.1 顺序存储
二叉树的顺序存储结构就是使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。




图3.6所示的一棵完全二叉树采用顺序存储方式，如图3.7表示：




由图3.7可以看出，当二叉树为完全二叉树时，结点数刚好填满数组。
那么当二叉树不为完全二叉树时，采用顺序存储形式如何呢？例如：对于图3.8描述的二叉树：





其中浅色结点表示结点不存在。那么图3.8所示的二叉树的顺序存储结构如图3.9所示：





其中，∧表示数组中此位置没有存储结点。此时可以发现，顺序存储结构中已经出现了空间浪费的情况。
那么对于图3.3所示的右斜树极端情况对应的顺序存储结构如图3.10所示：




由图3.10可以看出，对于这种右斜树极端情况，采用顺序存储的方式是十分浪费空间的。因此，顺序存储一般适用于完全二叉树。


3.7.2 二叉链表
既然顺序存储不能满足二叉树的存储需求，那么考虑采用链式存储。由二叉树定义可知，二叉树的每个结点最多有两个孩子。因此，可以将结点数据结构定义为一个数据和两个指针域。表示方式如图3.11所示：




定义结点代码：

typedef struct BiTNode{
    TElemType data;//数据
    struct BiTNode *lchild, *rchild;//左右孩子指针
} BiTNode, *BiTree;
复制代码

则图3.6所示的二叉树可以采用图3.12表示。





图3.12中采用一种链表结构存储二叉树，这种链表称为二叉链表。



大数据爱好者可加微信w3aboutyun



作者：MrHorse1992
链接：https://www.jianshu.com/p/bf73c8d50dc2