前言

哈喽，大家好，这里是面包园的知识分享，在上一篇文章中我们学习了树的相关概念，了解了树形结构，那今天让我们进一步学习树的特殊结构——二叉树。

一、什么是二叉树？

二叉树的概念：根节点➕左子树➕右子树

注意⚠️⚠️：

1. 二叉树节点的度是≤2的；
2. 二叉树的子树有左右之分，先左后右；这是因为跟我们数组有关，数组可以变成完全二叉树的结构。

二叉树的几种情况：

正因为二叉树的度是≤2的，所以我们可以分出一下几种情况：

1. 空树（无根节点）
2. 只有根节点
3. 只存在左子树
4. 只存在右子树
5. 左右子树都存在

现实中的二叉树

相信大家在生活中遇到这样的树，一定会拜一拜，哈哈哈哈，这可是我们程序员的灯塔呀！！！

二、特殊的二叉树

2.1 满二叉树

满二叉树的概念： 一般我们管每个节点的度都是2的二叉树叫做满二叉树

如图：满二叉树就是每个节点都有两个孩子节点，除了最后的一层的叶子结点。

2.2 完全二叉树

完全二叉树的概念：在满二叉树的基础上，可以去除任意个数的叶子结点。也就是说完全二叉树就是在最后一层上有改动，其他层都是满的。

三、二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2^h-1
3. 对任何一棵二叉树, 设度为0的叶结点个数为 n0 , 度为2的分支结点个数为 n2 ,都有 n0＝n2 ＋1
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log(n+1) （以2为底）

重要性质！！！

我们的数组其实是跟完全二叉树一一对应的，所以我们可以利用数组的性质找到完全二叉树的双亲结点和孩子结点的关系：

四、练习题

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
   A 不存在这样的二叉树
   B 200
   C 198
   D 199
2. 下列数据结构中，不适合采用顺序存储结构的是（ ）
   A 非完全二叉树
   B 堆
   C 队列
   D 栈
3. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
   A n
   B n+1
   C n-1
   D n/2
4. 一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
   A 11
   B 10
   C 8
   D 12
5. 一个具有767个节点的完全二叉树，其叶子节点个数为（）
   A 383
   B 384
   C 385
   D 386

答案：
1.B
2.A
3.A
4.B
5.B