依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

但对于一般的二叉树，为了让数组下标能反映二叉树中结点之间的逻辑关系，只能添加一些并不存在的空结点让其每个结点与完全二叉树上的结点相对照，再存储到一维数组的相应分量中。
然而，在最坏的情况下，一个高度为 H 且只有 H 个结点的单支树却需要占据接近 \(2^H-1\) 个储单元。
二叉树的顺序存储结构如图 4-4 所示，其中 0 表示并不存在的空结点。

注意：
这种存储结构显然要从数组下标 1 开始存储树中的结点，如果从数组下标 0 开始存储，则不满足性质 4 的描述，（比如结点 A 存储在 0 下标位置上时，則无法根据性质 4 来计算出其孩子结点在數组中的位置），这是考生在书写程序的时候容易忽略的。
注意区别树的顺序存储结构与二叉树的顺序存储结构。
在树的顺序存储结构中，数组下标代表结点的编号，下标上所存的内容指示了结点之间的关系。
而在二叉树的顺序存储结构中，数组下标既代表了结点的编号，也指示了树中各结点之间的关系，这种关系借助完全二又树的性质反应，当然，二叉树属于树，因此二叉树都可以用树的存姑结构来存储，但是树却不都能用二叉树的存储结构来存储。

（2）链式存储结构

由于顺序存储对空间利用率较低，因此，一般二叉树都采用链式存储结构。
链式结构是指用—个链表来存储一棵二叉树，二叉树中每一个结点用链表的一个链结点来存储。
在二叉树中，结点结构通常包括若干数据域及若干个指针域。
二叉链表至少包含 3 个域： 数据域 data、 左指针域 lchild 和右指针域 rchild,如图 4-5 所示。

图 4-6 所示为常用的二叉链表的存储结构。
而实际在不同的应用中，还可以增加某些指针域，如增加指向父结点的指针，则变为三叉链表的存储结构。

二叉树的链式存储结构描述如下：

typedef struct BiTNode {
    ElemType data; //数据域
    struct BiTNode *lchild,*rchild; //左、 右孩子指针
} BiTNode,*BiTree;

使用不同的存储结构，实现二叉树操作的算法也会不同，因此，要根据实际应用的场合（二叉树的形态和需要进行的运算）来选择合适的存储结构。
容易验证，在含有 n 个结点的二叉链表中含有 n+1 个空链域（重要结论，经常出现在选择题中）。
在下一节中，我们将利用这些空链域来组成另一种链表结构—线索链表。

4.3 二叉树的遍历和线索二叉树

4.3.1 二叉树的遍历

所谓二叉树的遍历，是指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。
由二叉树的递归定义可知，遍历一棵二叉树便要决定对根结点 N、左子树 L 和右子树 R 的访问顺序。
按照先遍历左子树再遍历右子树的原则，常见的遍历次序有先序（NLR）、中序（LNR）和后序（LRN）三种遍历算法。
其中，序指的是根结点在何时被访问。

（1）先序遍历（PreOrder）

先序遍历的操作过程为：
如果二叉树为空，什么也不做。
否则：

1. 访问根结点：
2. 先序遍历左子树：
3. 先序遍历右子树。

对应的递归算法如下：

void PreOrder(BiTree T) {
    if(T!=NULL) {
        visit(T); //访问根结点
        PreOrder(T->lchild); //递归遍历左子树
        PreOrder(T->rchild); //递归遍历右子树
    }
}

对于图 4-4 所示的二叉树，先序遍历所得到的结点序列为：1 2 4 6 3 5。

（2）中序遍历（InOrder）

中序遍历的操作过程为：
如果二叉树为空，什么也不做。
否则：

1. 中序遍历左子树；
2. 访问根结点;
3. 中序遍历右子树。

对应的递归算法如下：

void InOrder(BiTree T) {
    if(T!=NULL) {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

对于图 4-4 所示的二叉树，中序遍历所得到的结点序列为：2 6 4 1 3 5。

（3）后序遍历（PostOrder）

后序遍历的操作过程为：
如果二叉树为空，什么也不做。
否则：

1. 后序遍历左子树；
2. 后序遍历右子树；
3. 访问根结点。

对应的递归算法如下：

void PostOrder(BiTree T) {
    if(T!=NULL) {
        PostOrder(T->lchild); //递归遇历左子树
        PostOrder(T->rchild); //递归遍历右子树
        visit(T); //访问根结点
    }
}

对于图 4-4 所示的二叉树，后序遍历所得到的结点序列为：6 4 2 5 3 1。

三种遍历算法中递归遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。
不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，故时间复杂度都是 \(\mathcal{O}(n)\)。
在递归遍历中，递归工作找的栈深恰好为树的深度，所以在最坏的情况下，二叉树是有 n 个结点且深度为 n 的单
支树，遍历算法的空间复杂度为 \(\mathcal{O}(n)\)。

（编辑：ASP站长网）