数据结构 树笔记-4 二叉树存储结构
既然上面提到了二叉树的存储结构，那么我们进一步详细介绍二叉树的存储结构
先复习一下 逻辑结构 与 物理结构：
逻辑结构讲究的是数据之间的逻辑关系，分为：集合结构、线性结构、树形结构、图形结构
物理结构讲究的是数据的存储结构，分为：顺序存储结构、链式存储结构
二叉树的存储结构——顺序存储 或者 链式存储
以下针对如下这棵树讲解它的各种存储方式
顺序存储
代码定义：
// The sequential storage of binary trees
#define MAX_TREE_SIZE 100
#define TElemType char
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;
说明：
把树中的结点 从上至下按层，每一层按照从左至右的方式存放在一个一维数组中。
数组的第一个下标为0的元素不使用，从下标为1的元素开始存放树中的结点，
所以 树的根结点 永远放在下标为1的元素中。
注意：
因为这种方式既存放有值的结点，有存放空节点，
So这种存储方式适合 结点总数少 或者 每层结点数尽量最多的情况，因为不浪费空间。
如果一棵二叉树是单支树（从根开始，只要一个结点有孩子，那么只有一个左/右孩子），
那么这种存储方式很浪费空间。
这种存储方式一般用于完全二叉树和满二叉树。
链式存储
4种：
1. 二叉链表
2. 三叉链表
3. 线索链表
4. 双亲数组
——二叉链表（最常用）
代码定义：
// Binary list
#define ElemType char
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}*BiTree;
说明：
每个结点用一个结构体定义，结构体中的
data存放结点的数值；
lchild/rchild存放左/右孩子的地址；
注意：
左右孩子不是结构体 而是 指针，这样做的好处是：
1. 同样通过*符号访问孩子结点的成员
2. 结构体类型变量占的空间比指针大，结构体一般定义多个类型的成员，而指针就是一个地址变量，
可以通过程序的运算符sizeof查看这两种变量的内存占用字节大小
——三叉链表
代码定义：
// Trifurcate linked list
#define ElemType char
typedef struct TriTNode{
Elemtype data;
struct TriTNode *lchild,*rchild;
struct TriTNode *parent;
}TriTNode, *TriTree;
说明：
——双亲数组
代码定义：
#define MAX_TREE_SIZE 100
#define ElemType char
#define LRTagType int
#define lchild 0
#define rchild 1
typedef struct BPTNode{
ElemType data; //结点值域
int parent; //父结点在数组中的下标
LRTagType LRTag; //标志域:用于标记这个结点是父结点的左孩子还是右孩子
// 可以令其为0——左孩子，1——右孩子
}BPTNode;
typedef struct BPTree{
BPTNode nodes[MAX_TREE_SIZE];// 双亲数组
int n; // n:树中的结点个数
int r; // r:树根在数组中的下标
}BPTree;
说明：
如果一个双亲数组的内容如下