【IT168 技术】 

　　二叉树的存储结构

　　二叉树的存储结构有多种，最常用的有两种：是顺序存储结构和链表存储结构。

　　顺序存储结构

　　二叉树可以存放在一维数组之中，这是一种简单的顺序存储结构。请看如下语句：

　　const int MAXSIZE 20

　　typedef char ElemType;

　　ElemType bt[MAXSIZE];

　　其中 Bt 就是一维数组(向量)，用它来存储一棵二叉树，每个数组元素存储树的一个结点的数据信息。假设让 bt[0] 闲置，让 bt[1] 存放根结点信息。假设按照自上而下、自左至右的顺序将图 6.4(a) 的满二叉树存入一维数组 bt ，可以发现图 6.4(a) 中结的编号恰好与数组元素的下标号相对应，详见 6.5 图。根据二叉树性质 5 ，在 bt 数组中可以方便地由某结点 bt[i] 的下标 i ，找到它的双亲结点 bt[i/2] 或者它的左、右孩子结点 bt[2i] 、 bt[2i+1] 。例如 bt[2] 结点值为 B ，它的双亲结点是 bt[1] 值为 A ，左孩子结点是 bt[4] 值为 D ，右孩子结点是 bt[5] 值为 E 。

▲

　　优点和缺点

　　① 对完全二叉树而言，顺序存储结构既简单又节省存储空间。

　　② 一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。

　　【例】最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点的存储空间。

　　③在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。

　　链式存储结构

　　用于二叉树存储的链表结构，常见的有二叉链表和三叉链表。二叉链表的每个结点有一个数据域和两个指针域，一个指针指向左孩子，另一个指针指向右孩子。结点结构描述：

　　typedef struct node

　　{ int data; /* 数据域 */

　　struct node *lch,*rch; /* 左、右指针域 */

　　}Bnode;

　　三叉链表的结点比前者多了一个指向双亲的指针域。结点结构描述：

　　typedef struct node3

　　{ int data; /* 数据域 */

　　struct node3 *lch, *par ， *rch; /* par 是双亲指针域 */

　　} Bnode3;

▲

　　对于图 6.6(a) 中二叉树 T ，它的二叉链表如图 6.6(b), 三叉链表如图 6.6(c) 。