数据结构与算法之美-二叉树
前言：本篇文章只是记录王争的数据结构与算法之美的学习笔记，写下来能强迫自己系统的再过一遍，加深理解。这门课
以实际开发中遇到的问题为例，引入解决问题涉及到的的数据结构和算法，但不会讲的太细，最好结合一本实体书进行学习。
1. 树
1.1 树的定义
树有一个根节点，很多个子节点，如下图所示：
image.png
1.2 树中节点间的关系
节点之间有着不同的关系，比如下面图中，A 是 B 的父节点，B 是 A 的子节点，B C D 都是 A 的子节点，互称为兄弟结点。没有父节点的节点就是根节点（E 节点），没有子节点的节点叫做叶子节点或者叶节点，比如 G H I J K L。
image.png
1.3 高度&深度&层
image.jpeg
- 节点的高度 = 节点到叶子节点的最长路径（边数）
- 节点的深度 = 根节点到这个节点所经历的边的个数
- 节点的层数 = 节点的深度 + 1
- 树的高度 = 根节点的高度
2. 二叉树
2.1 二叉树的分类
二叉树使我们最常用的，什么是二叉树？就是一个节点下面，最多有两个子节点，分别是左子节点和右子节点，如下图所示：
image.png
满二叉树（上图 2 号树）：
- 叶子结点全都在最底层
- 除了叶子节点外，每个节点都有左右两个子节点
- 满二叉树总的节点个数 = 2^n - 1 (n 为树的层数)
完全二叉树（上图 3 号树）：
- 叶子节点在最底下两层
- 最后一层叶子节点从左到右中间无间隔
- 除了最后一层，其他层节点数要达到最大
满二叉树属于完全二叉树，完全二叉树并不一定是满二叉树。
2.2 二叉树的存储
有了二叉树这种数据结构，我们肯定需要考虑如何存储。有两种方法：
- 基于指针或者引用的二叉链式存储法
- 基于数组的顺序存储法
2.2.1 链式存储
其实跟链表的结点大同小异，每个节点有三个字段：data存储数据，left right 分别指向左右两个子节点，这种方式比较常用，如下图所示：
image.jpeg
2.2.2 顺序存储
就是把根节点存储在下标 i = 1 的位置，左子节点存储在下标 2 * i = 2 的位置，右子节点存储在 2 * i + 1 = 3的位置，以此类推，如下图所示，存储的是完全二叉树：
image.jpeg
节点存储在数组中下标为 i 的位置，则其左子节点的下标为 2 * i，右子节点的下标为 2 * i + 1，父节点下标为 i / 2。
如果是非完全二叉树，如果用顺序存储的话会浪费一些空间，还是用链式存储比较合适，如下图所示：
image.jpeg
3. 二叉树的遍历
经典的方法有三种：
- 前序遍历：先打印这个节点，然后打印它的左子树，最后打印它的右子树
- 中序遍历：先打印节点的左子树，然后打印这个节点，最后打印它的右子树
- 后序遍历：先打印它的左子树，然后打印它的右子树，最后打印这个节点
如下图所示：
image.jpeg
这三种遍历其实就是一个递归的过程，递推公式如下：
前序遍历的递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
中序遍历的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
后序遍历的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r
代码如下：
void preOrder(Node* root) {
if (root == null) return;
print root // 此处为伪代码，表示打印root节点
preOrder(root->left);
preOrder(root->right);
}
void inOrder(Node* root) {
if (root == null) return;
inOrder(root->left);
print root // 此处为伪代码，表示打印root节点
inOrder(root->right);
}
void postOrder(Node* root) {
if (root == null) return;
postOrder(root->left);
postOrder(root->right);
print root // 此处为伪代码，表示打印root节点
}
从前面的前、中、后序遍历的顺序图，可以看出来，每个节点最多会被访问两次，所以遍历操作的时间复杂度，跟节点的个数 n 成正比，也就是说二叉树遍历的时间复杂度是 O(n)。
4. 练习
- 二叉树的前序、中序、后序递归遍历方法
- 二叉树的前序、中序、后序非递归遍历方法
- 二叉树的层序遍历
- 获取树的总得节点数
- 获取树的叶子节点数
- 求树的深度
- 求二叉树第k层的结点个数
- 判断两棵二叉树是否结构相同
- 求二叉树的镜像
- 求两个结点的最低公共祖先结点
