5-4 二叉树的性质和存储结构

二叉树的顺序存储

实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素

二叉树的顺序存储：

#define MAXTSIZE 100
typedef TElemType SqBiTree[MAXTSIZE] 
SqBiTree bt;

提问：为什么不以[a b c d e f g]的形式来存储？

在e和f中间放0表示我们的树并非满二叉树，每个0对应了他们所在的结点位置

二叉树的顺序存储缺点：如果树为单支树，需要很多的空间来存储0或者NULL。对空间造成了浪费

最坏情况：深度为k的且只有k个结点的单支树需要长度为$2^{k}-1$的一维数组

特点：结点间关系蕴含在其存储位置中

浪费空间，适于存满二叉树和完全二叉树

5-4 二叉树的链式存储结构

二叉树的链式存储结构

二叉链表存储结构：

typedef struct BiNode {
	TElemType data;
	struct BiNode *lchild, *rchild; //左右孩子指针
}BiNode, *Bitree;