注意理解二叉树的顺序存储结构和链式存储结构的特点及适用范围。对给定顺序存储的完全二叉树某个结点下标，能说出该结点的双亲和孩子结点的下标。能画出二叉链表的逻辑示意图。

1.二叉树的顺序存储结构

二叉树的顺序存储是指利用数组存储二叉树。顺序存储一棵二叉树时，首先对该树中每个结点进行顺序编号，然后以各结点的编号为下标，把各结点的值对应存储到一个一维数组中。在图6-6(a)和(b)的二叉树中，各结点上方的数字就是该结点的编号。

图6-6 带结点编号的二叉树

假定分别采用一维数组data1和data2来顺序存储图6-6(a)和(b)中的二叉树，则两数组中各元素的值如图6-7所示。

图6-7 二叉树的顺序存储结构

在二叉树的顺序存贮结构中，各结点之间的关系是通过下标计算出来的，因此访问每一个结点的双亲和左、右孩子都非常方便。

二叉树的顺序存储结构对于存储完全二叉树是合适的，它能够充分利用存贮空间；但对于一般二叉树，特别是对于那些单分支结点较多的二叉树来说是很不合适的，因为可能只有少数存储位置被利用，而多数或绝大多数的存贮位置空闲着。因此，对于一般二叉树通常采用下面介绍的链接存贮结构。

2.二叉树的链式存储结构

（1）结点类型定义

在二叉树的链接存储中，通常采用的方法是在每个结点中设置三个域：值域、左指针域和右指针域，其结点结构为：

其中data表示值域，用于存储对应的数据元素，left和right分别表示左指针域和右指针域，用以存储左孩子和右孩子结点的存贮位置（即指针）。

二叉树链式存储的结点类型可定义为：