一.顺序存储二叉树

将二叉树存储在一个数组中，通过存储元素的下标反映元素之间的父子关系。

按照二叉树结点自上向下、自左向右的顺序存储。使用此存储方式，结点的前驱和后继不一定是它们在逻辑上的邻接关系，非常适用于满二又树和完全二又树。

顺序存储到数组中父节点与左右节点索引关系：

推导：
等比数列求和公式：s(n) = a(1-q^(n+1))/(1-q)
第k层节点个数：2^(k-1),k>=1
第1层到k-1层节点个数：2^(k-1)-1,k>=1
k层第一个节点索引：2^(k-1)-1,k>=1，偏移j个节点对应的节点索引：2 ^(k-1)-1+j，k+1层第j个节点对应的子节点索引:2 ^k - 1+2j

2^k - 1+2j = 2(2 ^(k-1) -1 + j) + 1

故完全二叉树子节点索引为2 * 父节点索引+1，2 * 父节点索引+2

子节点索引为k，则父节点索引为(k-1)/2

二.线索二叉树

对于二叉链表，不管二叉树的形态如何，n个结点的二叉链表共有2n个链域，非空链域为n-1个(从根节点开始一个指针链接一个节点)，故其中的空链域有n+1个。

为提高空指针利用率提出了一种方法，利用原来的空链域存放指针，指向树中其他结点，这种指针称为线索。

对每个结点增加 ltag、rtag 分别表示该节点的左右节点是左/右子树还是前驱/后继

若结点的左子树为空，则该结点的左孩子指针指向其前驱结点。

若结点的右子树为空，则该结点的右孩子指针指向其后继结点。