数据结构-5.5.二叉树的存储结构

一.二叉树的顺序存储：

a.完全二叉树：

1.顺序存储中利用了静态数组，空间大小有限：

2.基本操作：

(i是结点编号)

1.上述图片中i所在的层次后面的公式应该把n换成i(图片里写错了)；

2.上述图片判断i是否有左孩子，只需要判断是否2i<=n（2i代表第i个结点的左孩子，n代表完全二叉树的结点总数），如果2i<=n，就说明有左孩子，如果2i>n，说明没有左孩子(思路：把i当作是最后一个结点，此时i等于n，如果i有左孩子即2i，那么2i就大于n，此时结点总数为2i，显然不等于n，说明没有左孩子)，判断i是否有右孩子同理；

3.上述图片判断i是否是叶子/分支结点，只需要判断是否i>[n/2] (这里是对n/2向下取整)(i代表结点编号，n代表完全二叉树的结点总数)，如果i>[n/2]，就说明是叶子/分支结点，如果i<=[n/2]，就说明不是叶子/分支结点

b.普通二叉树：

(i是结点编号)

为了解决上述图片中无法从结点编号反应出结点间逻辑关系的问题，可以让普通二叉树的结点编号与完全二叉树一一对应起来：

但此时就会导致判断某结点是否有左/右孩子以及是否是叶子/分支结点无法用i与n之间的关系推导(例如上述图片中的二叉树如果是完全二叉树，那么编号为4的结点的右子结点的编号应该为9，但实际为7)，此时就只能通过刚开始创建的结构体TreeNode里的数据isEmpty来判断该结点是否为空(isEmpty为true时结点为空，反之非空)，

比如上述图片中要判断5号结点是否有左子结点即编号为10的结点，就需要判断编号为10的结点是否为空(到数组下标为10的单元判断)，若为空，则没有左子结点，反之有。

显然，采用这种顺序存储的方式来存储二叉树里面可能会有大量的空间浪费：

---

二.二叉树的链式存储：

1.一个结点包括数据域和左子结点指针，右子结点指针，如果左/右子结点没有，将其对应的指针设为NULL即可；

2.一个结点有两个指针域，如果有n个结点，就有2n个指针域；

3.除了根结点外，每一个结点头上都会连一个指针，因此共有n-1个结点头上连一个指针；

4.n个结点的二叉链表共有n+1个空链域(因为共有2n个指针域，共有n-1个结点头上连一个指针即用了n-1个指针域，剩下2n-(n-1)=n+1个指针域即空指针域，为NULL)，空链域可用于构造线索二叉树；

5.由于一个结点包括左子结点指针，右子结点指针，因此也叫二叉链表；

6.插入数据：

7.查找：

• 如果要查找某个结点的左/右子结点，只需要判断左/右子结点指针是否为空即可，为空代表没有左/右子结点，不为空时左/右子结点指针对应的结点就是要查找的结点；

• 要查找某结点如p结点的父结点，只能从根结点开始遍历寻找，看哪个结点的左/右子结点指针指向p结点，最终就可以找到p结点的父结点-->弊端：如果二叉树高度大，这种找父结点的方式就会很耗时，因为遍历的结点可能会很多，因此如果经常要逆向的查找某个结点的父结点或者要用到父结点，可以在二叉树结构体中再定义一个指针指向父结点，此时算上左子结点指针和右子结点指针总共就有3个指针，也叫三叉链表(根据实际需求决定要不要加父结点指针)

---

三.总结：

---