二叉树的存储表示
1二叉树的顺序存储表示 2二叉树的链式存储表示 3三叉链表
1二叉树的顺序存储表示
二叉树的顺序存储结构的定义如下：
#define MAXSIZE = 100； //暂定二叉树中节点数的最大值为100 Typedef struct {
ElemType *data ； //存储空间基址（初始化时分配空间） Int nodeNum ； //二叉树中节点数 }SqBiTree ； //二叉树的顺序存储结构
为了能在存储结构中反映出节点之间的逻辑关系，必须将二叉树中节点依照一定规律安排在这组存储单元中。

对于完全二叉树，只要从根起按层序存储即可。

显然，这种顺序存储结构仅适用于完全二叉树。

因为，在最坏的情况下，一个深度为 k 且只有 k 个结点的单支树（树中不存在度为 2 的结点）却需要长度为2k -1的一维数组。

二叉树的顺序存储图如图1所示：
2
6
320
116
5402
106
543216
（a ）满二叉树（b ）一般二叉树
图1 顺序存储
2二叉树的链式存储表示
二叉树有不同的链式结构，其中最常用的是二叉链表与三叉链表。

二叉链表的结点形式如表1所示：
表1链式存储
date域：称为数据域，用于存储二叉树结点中的数据元素，
1child域：称为左孩子指针域，用于存放指向本结点左孩子的指针(左指针)。

rchild域：称为右孩子指针域，用于存放指向本结点右孩子的指针(右指针)二叉链表中的所有存储结点通过它们的左、右指针的链接而形成一个整体。

根指针：每个二叉链表还必须有一个指向根结点的指针。

根指针具有标识二叉链表的作用，对二叉链表的访问能从根指针开始。

图2中（a）（b）表示一棵二叉树及其二叉链表。

值得注意的是，二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是指向该结点的一个孩子的指针，或者是空指针NULL。

二叉链表的类型定义如下：
Typedef struct btnode *bitreptr；
Struct btnode
{
Datatype data；
Bitreptr lchild,rchild；
}；
Bitreptr root；
若二叉树为空，则root=NULL。

若某结点的某个孩子不存在，则相应的指针为空。

具有n个结点的二叉树中，一共有2n个指针域，其中只有n-1个用来指向结点的的左右孩子，其余的n+1个指针域为NULL。

在二叉链表这种存储结构上，二叉树的多数基本运算如求根,求左、右孩子等很容易实现。

但求双亲运算PARENT(BT,X)的实现却比较麻烦，而且其时间性能不高。

3三叉链表
三叉链表的类型定义如下：
protected:
BiTreeNode<Elem> *lchild；// 指向左子树的指针
BiTreeNode<Elem> *rchild；// 指向右子树的指针
BiTreeNode<Elem> *parent；// 指向双亲的指针
三叉链表存储每个节点由四个域组成，具体结构为：
其中，data、lchild以及rchild三个域的意义同二叉链表结构；parent域为指向该结点双亲结点的指针。

这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。

为了便于查找任一结点的双亲结点，可以在结点中再增加一个指针域parent，它称为三叉链表。

如图2中的（a）(c)。

A
root
H
G
F
E
D
C
B
（a ）
（c ）
图 2二叉树的二叉链表和三叉链表。