[数据结构与算法]数据结构-15.二叉树的顺序存储

顺序存储：

可以让第一个位置空缺，保证数组下标和结点编号一致。

#define MaxSize 100
struct TreeNode{
	ElemType value;
	bool isEmpty;	//结点是否为空
};
TreeNode t[MaxSize];
for(int i=0;i<MaxSize;i++){
	t[i].isEmpty=true;
}

定义一个长度为MaxSize的数组t，按照从上至下，从左到右的顺序依次存储完全二叉树中的各个结点。
根结点标号为1

i的左孩子：2I
i的右孩子：2I+1
i的父结点：[i/2] 下取整
i所在层次：log2(n+1) 上取整 或者 log2n+1 下取整

二叉树的顺序存储，只适用存储完全二叉树。

链式存储：

//二叉树的结点链式存储
typedef struct BiTNode{
	ElemType data;
	struct BiTNode *lchild,*rchild;	//左右孩子指针
}BiTNode,*BiTree;

n个结点的二叉链表共有n+1个空链域

//定义一个空树
BiTree root=NULL;
//插入根结点
root=(BiTNode*)malloc(sizeof(BiTNode));
root->data=1;
root->lchild=NULL;
root->child=NULL;
//插入新结点
BiTNode *p=(BiTNode*)malloc(sizeof(BiTNode));
p->data=2;
p->lchild=NULL:
p->rchild=NULL;
root->lchild=P;	//做为根结点的左孩子

三叉链表：

二叉链容易找到指定结点的左右孩子，但是找到指定结点的父结点需要从根结点遍历二叉树。
所以我们?父结点指针

typedef struct BiTNode{
	ElemType data;
	struct BiTNode *lchild,*rchild;//左右孩子指针
	struct BiTNode *parent;		   //父结点指针
}BiTNode,*BiTree;