二叉树顺序存储结构

二叉树由于其特殊性，使用顺序存储结构也能实现。

1.一颗完全二叉树的顺序存储结构

如图

将其存入数组中是这样的

2.一般二叉树的顺序存储结构

我们把不存在的节点实则之为^;

如图

将其存入数组中是这样的

3.极端情况，右斜树

如图

将其存入数组中的情况是这样的

上面的例子我们可以非常清楚，非完全二叉树，需要分配多余的存储空间，这样是浪费的，所以一般来说顺序存储结构仅适用于完全二叉树

二叉链表

二叉树每个结点最多有两个孩子，所以可以为它设计一个数据域和两个数据指针分别指向左孩子和右孩子，我们称这样链表叫做二叉链表。

二叉链表结点的实现

/**
 * 二叉树的存储结构
 */
class BitNode{
    public $data; //数据域
    public $lchild; //左孩子指针
    public $rchile; //右孩子指针
    //public $parent //双亲指针
}

如图所示

如果需要，可以设计多一个指针指向其双亲，这样的链表称为3叉链表