数据结构学习笔记(二十二)——二叉树的存储结构

1 二叉树的存储结构主要有顺序存储结构和链式存储结构两种。

2 二叉树顺序存储结构：用一组地址连续的存储单元来存放二叉树的数据元素。

2.1 存放次序：对该树中每个节点进行编号，其编号从小到大的顺序就是节点存放在连续存储单元的先后次序。

2.2 编号过程：首先把树根节点的编号定为1，然后按照从上到下、从左到右的顺序，对每一节点进行编号。当某节点是编号为i的双亲节点的左孩子节点时，则它的编号应为2i；当它是右孩子节点时，则它的编号应为2i+1。

2.3 存储结构类型定义：

typedef ElemType SqBTree[MaxSize]；

其中，ElemType为二叉树中节点值的类型，当二叉树中某节点为空节点或无效节点（不存在该编号的节点）时，对应位置的值用特殊值（如“#”）表示。

2.4 实例：

3 二叉树的链式存储结构：用一个链表来存储一棵二叉树，二叉树中每一个节点用链表中的一个链节点来存储。在二叉树中，标准存储方式的节点结构为：

其中，data表示值域，用于存储节点的数据元素，lchild和 rchild分别表示左指针域和右指针域，分别存储左孩子节点和右孩子节点。这种链式存储结构称为二叉链。

3.1 类型定义

typedef struct node{

ElemType data;

struct node *lchild;

struct node *rchild;

}

3.2 实例：