5.2.2二叉树的存储结构

知识总览： 

二叉树的顺序存储：

 把二叉树上的节点连续顺序的存放

用TreeNode数组存储二叉树，TreeNode代表一个个节点，ElemType是真正存放的元素值比如1、2啥的吧？，isEmpty表示节点是否为空初始化的时候都是空，如下数组中的第一个Index没存任何节点数据，从Index=1位置上开始存正好和节点编号对应上，也可从index=0开始存储

i的父节点:i/2向下取整，完全二叉树适用

一个普通的二叉树即不是完全二叉树依次顺序存储到TreeNode数组里，数组编号/二叉树的编号已经不能反映出节点之间的关系，如下第3张图，按二叉树编号4是2的右孩子，根据2i=2*2=4编号4应该是编号2的做孩子，这些2i关系已不再适用普通二叉树，而在treeNode数组里依次存放后，左孩子2i=4也依然不再适用

解决普通二叉树不再适用完全二叉树节点编号的问题：

把普通二叉树不存在的编号写上然后再放到treeNode数组里，只是不存在的节点编号对应的Index位置存储的元素ElemType为空，isEmpty字段为true，因为如下：假设把普通二叉树不存在的节点按照完全二叉树的顺序也排布上，即虽然普通二叉树实际的节点数=8，但是按照顺序排布后认为是12个节点(最后一个节点编号是12)即n=12，当i=2时，判断i是否有左孩子2i<=n，2*2<=12条件成立但不适用，所以判断是否某个节点有左孩子要用isEmpty字段(根据视频上的讲解个人理解，可能理解有误)

采用顺序存储方式存储二叉树(普通二叉树)节点缺点：有大量空闲位置，只适用于存储完全二叉树

顺序存储即使存储普通二叉树也要把节点编号和二叉树的对应起来，即如下最后一张图一个高度为4的右子树，即使只有4个节点但是节点编号是15，也要按照顺序给不存在的节点留下空间

二叉树的链式存储：

 BiNode表示一个个节点，包括data域+2个指向左右孩子的指针，data存储节点具体的值，lchild指向左孩子的指针，rchild指向左孩子指针，没有左、右孩子lchild、rchild设置为null即可

一个节点有2个指针域，n个节点有2n个指针域，除了根节点之外，其他节点的头上总会有一个指针，即有n-1个节点头上有指针，n+1个指针会指向空节点，可以用这n+1个空链域构造线索二叉树

因为每个节点上都有2个指针，所以这种实现方式又叫二叉链表，有3个指针的叫三叉链表

代码实现：

定义一颗空树(现在还没有任何节点)，申请一片空间BiNode root = (BiTree)malloc(sizeof(BiNode))，插入根节点root数据域为1root->data={1}，只有根节点即左右孩子指向为null 即root->lchild = null  root->rchild=null，申请一片空间插入新节点数据域为2 BiNode *p = (BiNode *) malloc(sizeof(BiNode))[新节点是指针吗？？]，让根节点的左孩子指针指向P节点root->lchild=p，新节点的左右孩子指向都为空

 

三叉链表：

每个节点有指向左右孩子的指针，要找某个节点的做孩子直接找lchild指针指向的节点即可即找左右孩子容易找，找p节点的父节点即逆向找需要从根节点一个个往下找直到找到某个节点的孩子是P即找到了P节点的父节点，需要从父节点一个个遍历耗时大，因此会在BiNode链表节点上再加一个指向父节点的指针parent即三叉链表

 

知识回顾：