完全二叉树
概念
百度百科：
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
下面我将用比较容易理解的文字来给大家阐述完全二叉树，并能做一些计算机二级考试或者数据结构的选择题。此篇博客暂不包含代码，后续补充。
二叉树的特点
- 非线性数据结构
- 数据元素（结点）按分支关系组织起来的结构
- 每个结点最多有两个子树的有序树
- 左子树和右子树是有顺序的，次序不能颠倒
- 每个结点的度最多为2
度：结点的分支数
（简单了解即可）~
判断是否为完全二叉树
所谓的完全二叉树，是二叉树的一种，每个结点最多有两个孩子结点，这里我们统称左孩子结点和右孩子结点。
和一般二叉树不同的是，完全二叉树必须从上至下逐排摆满，每个结点必须先有左孩子结点再有右孩子结点。如下图就是一个一般二叉树的例子：
由图可知，C结点没有左孩子结点，但却有右孩子结点，所以不满足完全二叉树的定义。
简而言之，画完全二叉树的时候必须一层一层的画满，第一层画一个，第二层画两个，第三层画四个······当然最后一层可以不画满，但倒数第二层及以前的层一定是满足1,2,4,8······的等比数量关系。并且每一层先画左孩子结点再画右孩子结点。
如下图所示就是一棵完全二叉树。
完全二叉树的特点
- 叶子结点只可能在倒数第一层和倒数第二层出现
- 对任意一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+1（子树必须向左对齐）
- 度为1的结点只有0或1个
- 第n层上至多含有2n-1个结点
- 高度为k的二叉树，最多有2k-1个结点
叶子结点：没有左右孩子的结点
树的高度：树的层数
1+2+3+4+······+k 利用高中学的等比数列公式可得2k-1
完全二叉树的练习题
-
一棵含有200个结点的完全二叉树，它的非叶结点有【 】个。
答案：100
方法一：
①因为27-1<200<28-1，根据完全二叉树的定义，这棵完全二叉树高度是八层
②前七层全部排满，总结点数是27-1=127个，第八层还剩200-127=73个叶子结点从左往右依次排列
③第八层每两个结点就会成为上一层对应结点的左右孩子结点，所以第八层的前72个结点会成为第七层的前36个结点的左右孩子结点
④第八层的第73个结点会成为第七层的第37个结点的左孩子结点
⑤在未排第八层之前，第七层原本有27-1=64个叶子结点，排完第八层后还剩64-37=27个叶子结点
⑥第七层有27个叶子结点，第八层有73个叶子结点，加起来一共27+73=100个叶子结点。
⑦非叶子结点数量=总结点数-叶子结点的数量=200-100=100个
方法二：
①由完全二叉树的性质可知，度为1的结点只有0或1个，因为第八层有73个叶子结点，是奇数，所以该完全二叉树度为1的结点有1个
②所以此处y的值为1，因为sum=200，sum=2x+y-1，可以得出x=100，即叶子结点的数量为100
③非叶子结点数量=总结点数-叶子结点的数量=200-100=100个
x：度为0（叶子结点）结点的数量
y：度为1结点的数量
z：度为2结点的数量
sum：总结点数
sum=x+y+z
x=z+1（总边数=度为2的结点个数*2+度为1的结点个数=总结点数-1，即2z+y=x+y+z-1，化简即可）
sum=2x+y-1
-
一棵完全二叉树总共有360个结点，则在该二叉树中度为1的结点个数为：
A. 0 B. 1 C. 180 D. 181
【答案】B
【思路】首先这个题说了，这是一棵完全二叉树，根据完全二叉树的性质，度为1的结点只有0个或1个，直接排除C和D。因为28-1<360<29-1，所以这棵完全二叉树有九层，观察最后一层的结点个数即可，奇数的话有1个度为1的结点，偶数的话没有度为1的结点。360-（28-1）=105，为奇数，所以则在该二叉树中度为1的结点个数为1，选B。
-
总结
在更新Java学习的道路上偶尔会穿插一些小问题，记录自己复习到的每一个知识点，会更加记得牢！
