文档介绍：二叉树的存储结构 二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可采用顺序 存储结构和链式存储结构。
二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。因此，必须把二叉树 的所有结二叉树的存储结构 二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可采用顺序 存储结构和链式存储结构。
二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。因此，必须把二叉树 的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关 系，用编号的方法从树根起，自上层至下层，每层自左至右地给所有结点编号，缺点是有可能对 存储空间造成极大的浪费，在最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1 个结点存储空间。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点 的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利 用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。图5-5(a)是一棵完全 二叉树，图5-5 (b)给出的图5-5(a)所示的完全二叉树的顺序存储结构。
A
B
C
D
E
F
数组下标123456
(a) 一棵完全二叉树
(b) 顺序存储结构
(b)改造后的完全二叉树
图5-5完全二叉树的顺序存储示意图
对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组 中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存 在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。如图5-6给出了 一棵一般二叉树改造后的完全二叉树形态和其顺序存储状态示意图。显然，这种存储对于需增加 许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时，会造成空间的大量浪费，不宜 用顺序存储结构。最坏的情况是右单支树，如图5-7所示，一棵深度为k的右单支树，只有k 个结点，却需分配2k—1个存储单元。
(a) 一棵二叉树
A B C A D E A A A F A A G
(c)改造后完全二叉树顺序存储状态
图5-6 一般二叉树及其顺序存储示意图
(a) 一棵右单支二叉树 (b)改造后的右单支树对应的完全二叉树
A
A
B
A
A
A
C
A
A
A
A
A
A
A
D
(c)单支树改造后完全二叉树的顺序存储状态
图5-7右单支二叉树及其顺序存储示意图
结构5-1二叉树的顺序存储
金
#define Maxsize 100 〃假设一维数组最多存放100个元素
typedef char Datatype; 〃假设二叉树元素的数据类型为字符
typedef struct
( Datatype bt[Maxsize];
int btnum;
}Btseq;
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。
通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结 点左孩子和右孩子所在的链结点的存储地址。其结点结构为：