数据结构重学日记（十七）二叉树的存储结构

二叉树的存储结构也包括顺序存储和链式存储

顺序存储

就是用一组地址连续的存储单元依次自上而下，自左至右存储完全二叉树上的结点元素。

完全二叉树

对于非完全二叉树，也要把它看做是完全二叉树，然后把对应的结点置空。

斜树的存储

也因为如此，当树为斜树时就会造成大量的空间浪费，所以就又有了链式存储。

链式存储

二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。

通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。其结点结构为：

其中，data域存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。利用这样的结点结构表示的二叉树的链式存储结构被称为二叉链表，如图所示。

链式存储结构

为了方便访问某结点的双亲，还可以给链表结点增加一个双亲字段 parent，用来指向其双亲结点。每个结点由四个域组成，其结点结构为：

这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。利用这样的结点结构表示的二叉树的链式存储结构被称为三叉链表。

三叉链表