【数据结构】—— 二叉树
引入
上一章我们学习了树的基本概念以及树的存储结构，其中兄弟孩子表示法使用最广，它可以将一颗复杂的树转换成二叉树，这样我们就可以利用二叉树的算法和特性来处理问题！那什么是二叉树呢？
对于在某个阶段都是两种结果的情形，比如开和关、0 和 1、真和假、上和下、对与错，正面与反面等，都适合用树状结构来建模，而这种树是一种很特殊的树状结构，叫做二叉树。
二叉树的定义
二叉树(Binary Tree)是n(n≥0)个结点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
二叉树的特点
- 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的。
- 左子树和右子树是有顺序的，次序不能任意颠倒。就像人是双手、双脚，但显然左手、左脚和右手、右脚是不一样的，右手戴左手套、右脚穿左鞋都会极其别扭和难受。
- 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。
注意：对于任意的二叉树都是由以下几种情况复合而成的：
特殊的二叉树
我们再来介绍一些特殊的二叉树。这些树可能暂时你不能理解它有什么用处，但先了解一下，以后会提到它们的实际用途。
斜树
顾名思义，斜树一定要是斜的，但是往哪斜还是有讲究。所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。斜树有很明显的特点，就是每一层都只有一个结点，结点的个数与二叉树的深度相同。
满二叉树
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是 说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
单是每个结点都存在左右子树，不能算是满二叉树，还必须要所有的叶子都在同一层上，这就做到了整棵树的平衡。因此，满二叉树的特点有:
- 叶子只能出现在最下一层。出现在其他层就不可能达成平衡。
- 非叶子结点的度一定是2。否则就是“缺胳膊少腿”了。
- 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
完全二叉树
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
这可能有点难以理解！首先从字面上要区分，“完全”和“满”的差异，满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满二叉树。其次，完全二叉树的所有结点与同样深度的满二叉树，它们按层序编号相同的结点，是一一对应的。这里有个关键词是按层序编号，像下图的左树，因为5结点没有左子树，却有右子树，那就使得按层序编号的第 10个编号空档了。同样道理，下图的右树，由于3结点没有子树，所以使得 6、7 编号的位置空档了。所以它们都不是完全二叉树！！！
从上面的例子，也给了我们一个判断某二叉树是否是完全二叉树的办法，那就是看着树的示意图，心中默默给每个结点按照满二叉树的结构逐层顺序编号，如果编号出现空档，就说明不是完全二叉树，否则就是。
二叉树的性质
性质1：若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 个结点.
这个性质不用证明了，你直接画一颗满二叉树的图一看就知道了。
性质2：若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 .
这样也一样，看图说话！
性质3：对任何一棵二叉树T，如果其终端结点数（叶子结点)为 ，度为2的结点数为
，则
=
+1
证明：对于一棵二叉树，除了叶子结点外，剩下的就是度为1或2的结点数了，我们设为度是1的结点数为。则树T结点总数n=
+
+
。
比如上图例子，结点总数为10，它是由A、B、C、D度为2结点，F、G、H、I、J等度为0的叶子结点和E这个度为1的结点组成。总和为 4+1+5=10。
我们换个角度，再数一数它的连接线数，由于根结点只有分支出去，没有分支进入，所以分支线总数为结点总数减去1。如上图所示就是9个分支。对于A、B、C、D结点来说，它们都有两个分支线出去，而E结点只有一个分支线出去。所以总分支线为4x2+1x1=9。用代数表达就是分支线总数= n-1 = + 2
。因为刚才我们有等式n=
+
+
；所以可推导出
+
+
- 1=
+ 2
。结论就是
=
+1；证明完毕！
性质4：若规定根节点的层数为1，具有n个结点的满二叉树的深度：h= log (n + 1)(ps： 是log以2为底，n + 1为对数)
证明：对于一颗满二叉树而言，假设它的深度为h，那么这颗满二叉树的结点个数n为；
也就是说： =
;（对等式两边取对数）得：h= log (n + 1)证明完毕！！
性质5：对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为 i 的结点有：
若 i > 0，i 位置节点的双亲结点序号：(i - 1) / 2；i=0，i为根节点编号，无双亲节点；
若 i > 0，则2i + 1为左孩子序号：若2i + 1 >= n则无左孩子
若 i > 0，则2i + 2为右孩子序号：若2i + 2 >= n则无右孩子
该性质也不证明，直接看图说话！唯一要注意的是如果二叉树的起始序号不是0；上述的推导关系，需要重新推导！！
二叉树的存储结构
前面我们已经谈到了树的存储结构，并且谈到顺序存储对树这种一对多的关系结构实现起来是比较困难的。但是二叉树是一种特殊的树，由于它的特殊性，使得用顺序存储结构也可以实现。也就是说；对于二叉树，我们可以使用顺序存储结构和链式存储结构。
顺序存储结构
二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。这就需要用到二叉树的性质5；
但是要注意顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆（堆就是一颗完全二叉树）才会使用数组来存储，关于堆我们下一个章节会专门讲解。因此，二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
链式存储结构
既然顺序存储适用性不强，我们就要考虑链式存储结构。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。结点结构图所示。
结构定义如下所示：
typedef char BTDataType;
// 二叉链
typedef struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
}BTNode;链式存储结构可以分为二叉链、三叉链；当前我们的学习主要还是以二叉链为主要的结构；其实，三叉链的存储结构只是在二叉链的基础上添加了一个指向双亲结点的指针；这种结构的设计，后续会使用到。
二叉树的遍历
二叉树的遍历(traversing binary tree)是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。
这里有两个关键词：访问和次序。
访问其实是要根据实际的需要来确定具体做什么，比如对每个结点进行相关计算，输出打印等，它算作是一个抽象操作。在这里我们可以简单地假定就是输出结点的数据信息。
二叉树的遍历次序不同于线性结构，最多也就是从头至尾、循环、双向等简单的遍历方式。树的结点之间不存在唯一的前驱和后继关系，在访问一个结点后，下一个被访问的结点面临着不同的选择。由于选择方式的不同，遍历的次序就完全不同了。
二叉树的遍历方式可以很多，如果我们限制了从左到右的习惯方式，那么主要就分为四种：前序遍历、中序遍历、后序遍历、层序遍历
前序遍历
规则：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。简单来说；就是先访问根结点——左子树——右子树；对此的解释：从根结点开始，访问它的data，接着访问当前结点的左子树（前提是当前左子树不为NULL)，接着从左子树的根结点开始，重复上述操作，直到左子树为NULL，才去访问右子树。
如下图所示：该树的前序遍历的顺序为:ABDGHCEIF
通过观察上图的遍历顺序，有没有感觉想是递归调用的图示！没错，除了层序遍历，其余的所有遍历都可以采用递归实现！而前序遍历的实现如下：
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
printf("%c ", root->_data);
//递归调用
PrevOrder(root->_pLeft);
PrevOrder(root->_pRight);
}中序遍历
规则：若树为空，则空操作返回，否则从根结点开始(注意并不是先访问根结点)，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。访问的顺序：左子树——根结点——右子树
这个可能不是很好理解！，我们还是看上一个二叉树的图示；我要从根结点开始访问，但是，要访问根节点之前就一定要先访问根节点的左子树；而要访问根结点A的左子树B，需要先访问B的左子树D，依次递归下去，直到左子树为空，才能访问根结点，访问完根结点才能访问右子树。所以该树的中序遍历的顺序为:GDHBAEICF。
中序遍历的实现如下：
void InOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
//递归调用
InOrder(root->_pLeft);
printf("%c ", root->_data);
InOrder(root->_pRight);
}后序遍历
规则：若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。访问顺序：左子树——右子树——根结点；对于后序遍历的解释，还是依托与中序遍历一样！要访问当前子树的根结点；需要先访问当前结点的左子树，右子树；该树的后序遍历的顺序为:GHDBIEFCA。
后序遍历的实现如下：
void PostOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
//递归调用
PostOrder(root->_pLeft);
PostOrder(root->_pRight);
printf("%c ", root->_data);
}层序遍历
规则：若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。如下图的中序遍历的顺序为:ABCDEFGHI。
对于层序遍历，它其实就是一种暴力搜索的思想。它和广度优先搜索（简称：BFS)的实现逻辑一样，将当前的所有可能结果全部入队，再以队中元素作为中转点，将所有可能的结果入队。如果没有学过可能会有点迷糊！不过没关系，我们可以以二叉树的层序遍历为起始，来了解BFS。
我们直接来一道题目：二叉树的层序遍历
思想：由于层序遍历，需要用到队列，而C语言没有STL所有需要自己去实现一个队列；太麻烦了！我直接用C++调用STL进行代码编写；重点是思想！！
首先，如果这颗二叉树不是空树，那么我就将这颗树的根结点入队！(注意：入队的是二叉树结点，不是结点的数据)
| 队头 | 队尾 | |
| 队列： | A |
接着将队头元素出队，将队头元素的左右非空子树的根结点入队，
| 队头 | 队尾 | ||
| 队列： | B | C |
重复上述操作！，直到队列为空。这就是层序遍历的总体思想！但是对于该题来说，还差点意思，思考如何一行输出一层的所有结点？提示，考虑队列元素的个数。假设我是从根结点开始，现在队列的元素个数为1，那么我只需要出队一次，就可以将B、C入队；那么我只需要出队2次就可以将B、C的左右子树的根结点入队，思考一下是不是？
代码参考：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
//定义队列
vector< vector<int> > vv;
queue<TreeNode*> q;
if(root == nullptr)
return vv;
else
q.push(root);
while(!q.empty())
{
/**
第一次入队，就一个节点，也就是说第一层就一个数，在出的同时入队
那么循环结束后，队列中的所有节点都是下一层的节点
*/
vector<int> v;
int len = q.size();
for(int i = 0; i < len; i++)
{
TreeNode* tmp = q.front();
q.pop();
v.push_back(tmp->val);
if(tmp->left != nullptr)
q.push(tmp->left);
if(tmp->right != nullptr)
q.push(tmp->right);
}
vv.push_back(v);
}
return vv;
}
};到此关于二叉树的概念、性质、遍历全部梳理完毕！其中对于二叉树的的遍历来说，初学还是很抽象的，如果对于遍历的过程还是不太理解，一定要求配合代码，画函数的递归调用的图示，这对我们理解二叉树的遍历很有帮助！