4.binary_tree.md

二叉树

1. 每个节点的度最多为2
2. 度为0的节点比度为2的节点多1个

（链表就是只有一个孩子的树）

度为0的节点比度为2的节点多1个 推导过程

树中节点数量比边的数量多一个

所以不妨设度为0，1，2的节点分别为n0，n1，n2

有：

$n_0 + n_1 + n_2 = n_1 * 1 + n_2 * 2 + 1$

等式两边消去n1和n2

$n_0 = n_2 + 1$

也就是说给定一个树，给你叶子节点的数量，就能知道度为2的节点数量

二叉树的遍历

前中后

见代码 4.BST.cpp

完全二叉树和满二叉树

注意图中的完全二叉树如果删去5节点就不是完全二叉树了！

下面是二叉树-错误版

满二叉树的定义不是每一层全满了，而是只有度为0和2的节点

完全二叉树的特殊性质

1. 编号为i的节点，左孩子编号为2 * i，右孩子为2 * i + 1
2. 可以用连续空间存储

为什么说这种结构很优秀呢？是因为它可以不用存储左右孩子的指针！

也就是相当于不用存二叉树中边的信息，这样就节省了巨大的空间（能算的东西为什么要存）

引出算法优化思想：记录式和计算式

一个是节省时间，一个是节省空间

当我们能把一个完全二叉树看成是一个一维的数组，这说明我们的思想是非常高级，非常抽象的

因为表现形式为二维的一个二叉树，我们将它逻辑上物理上都看成一个一维的数组

深入理解树形结构

为什么树形结构重要？因为树的组成有节点和边，节点和边可以代表不同的意义

一般来说，树的节点代表集合，边代表关系。所以可以用来进行查找操作

学习二叉树的作用

1. 理解高级数据结构的基础

注意B-树可以读成B减树，但是不是和B+树是加减的对应关系，而是B树就叫B-树

2. 练习递归技巧的最佳选择（通过二叉树来锻炼递归）

递归程序四步走：

1. 数学归纳法->结构归纳法
2. 赋予递归函数一个明确的意义
3. 思考边界条件
4. 实现递归过程

而数学归纳法最美妙的一步就是假设$k_i$是正确的

一般步骤：$k_0$正确，也就是边界正确；假设$k_i$是正确的->$k_{i + 1}$正确

所以说呢，编写递归函数的要义不在于我们带入递归的视角去看哪一层进行到哪了

而是在于证明了数学归纳法是正确的

就不用管其他的

示例：

3. 左孩子右兄弟法节省空间

因为n叉树都可以转化成左孩子右兄弟法的二叉树

WHY？

以这个三叉树为例，可以看到浪费的指针域从13个变成了7个

如果是n个节点的k叉树呢(边比节点少1)

浪费的边: $k \times n - (n - 1)$

但是二叉树是: $2 \times n - (n - 1) = n + 1$条边