考研专业课之统考计算机蓝宝书(19)

3.2.2 二叉树的存储

1．顺序存储结

所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。这样结点在存储位置上的前驱后继关系并不一定就是它们在逻辑上的邻接关系，然而只有通过一些方法确定某结点在逻辑上的前驱结点和后继结点，这种存储才有意义。因此，依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

二叉树的顺序存储表示可描述为：
#define MAXNODE /*二叉树的最大结点数*/
typedef elemtype SqBiTree[MAXNODE] /*0号单元存放根结点*/
SqBiTree bt;
即将bt定义为含有MAXNODE个elemtype类型元素的一维数组。

2．链式存储结构

所谓二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。通常有下面两种形式。
（1）二叉链表存储
链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。结点的存储的结构为：

其中，data、lchild以及rchild三个域的意义同二叉链表结构；parent域为指
向该结点双亲结点的指针。这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。

• ·2010年迦思佑考研6000词逻辑辨证记忆
• ·2010年迦思佑张纪元考研6000词汇记忆课堂录音
• ·10版研究生英语难句过关-盘内容
• ·【VIP专享】2009新东方考研英语复试听力(音频+讲义)
• ·沪江考研原创：和我一起突破考研长难句1-33
• ·胡敏考研英语词汇-读故事记单词（09最新版）MP3
• ·2010淘金高阶考研英语词汇词典版MP3
• ·2010考研英语阅读理解精读100篇（高分版）文本下载
• ·2009年考研英语大纲词汇
• ·2010考研英语万能作文MP3

• 麦考瑞内部雅思7-7.5分部分题库
• 一月速背6000单词
• 英语口语需要自然流露
• 7月名师讲座
• 点滴积累学英语系列之一