- 每棵树节点的度最大为2（最多拥有2棵子树）
- 左子树和右子树是有顺序的
- 即使某节点只有一颗子树，也要区分左右子树
二叉树是有序树
非空二叉树的第i层，最多有2i-1个节点（i >= 1）
- 在高度为h的二叉树上最多有2h-1个节点（h >= 1）
- 对于任何一颗非空树二叉树，如果叶子节点个数为n0，度为2的节点个数为n2，则有n0 = n2 + 1
- 假设度为0的节点个数为n0 ，度为1的节点个数为 n1 ，度为2的节点个数为 n2 ，那么二叉树的节点总数为 n = n0 + n1 + n2 (二叉树也就这几种度的情况)
- 二叉树的边数（两节点之间的连线）T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1
- n1 + 2 * n2 即为 度为1的则有1条边，度为2的则有2条边，所以边总数则是该公式
- n - 1 即为 换个角度思考，每个节点上方都有一条边，除了根节点，故总边数可为该公式
- 故 n1 + 2 * n2 = n0 + n1 + n2 - 1 可求证出 n0 = n2 + 1
真、满二叉树
真二叉树：所有节点的度不是0就是2
满二叉树：所有节点的度不是0就是2，且所有叶子节点都要在最后一层
- 在同样高度的二叉树中，满二叉树的叶子节点数量最多、总节点数量最多
- 满二叉树一定是真二叉树，真二叉树不一定是满二叉树
例如： 假设满二叉树的高度为 h（ h ≥ 1 ）
则：
- 第 i 层的节点数量： 2i-1
- 叶子节点数量： 2h-1
- 总节点数量 ：2h - 1 = 20 + 21 + 22 + ⋯ + 2h−1 ，则可反向推导出高度 h = log2(n + 1)
完全二叉树
叶子节点只会出现最后2层，且最后1层的叶子节点都靠左对齐（例如下树，如果J在右边，则不算是完全二叉树）
- 完全二叉树从根结点至倒数第 2 层是一棵满二叉树
- 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
- 度为 1 的节点只有左子树
- 度为 1 的节点要么是 1 个，要么是 0 个
- 至少有 2 h − 1 个节点 （ 2 0 + 2 1 + 2 2 + ⋯ + 2 h−2 + 1 ）
- 这里有点绕：如下图，这颗完全二叉树至少有1-8的节点，则为 (2h-1) - (2h-1) + 1 = 2h - 2h-1 = 2h(1 - 2-1) = 2h-1
- (2h-1) 为满二叉树的全部节点
- (2h-1) 为满二叉树的最后1层的节点数
- 最多有 2 h − 1 个节点（ 2 0 + 2 1 + 2 2 + ⋯ + 2 h−1，满二叉树 ）
完全二叉树的高度 h = floor( log2n ) + 1
- 因为节点总数的取值范围为 2 h − 1 ≤ n < 2 h ，左右取对数后，可得h-1 ≤ log2n < h
- 则，例如 log2n = 4.8（可能为小数），根据上公式，可得h仅能为5，则得出 h = floor( log2n ) + 1
- 扩展知识：floor 是向下取整，另外，ceiling 是向上取整
如下编号，如果节点 i > 1，它的父节点编号为 foor( i / 2 ) ，则 i 除以 2 向下取整；
- 如下编号，如果2i < n (n为总节点数)，它的左子节点编号为 2i；
- 如下编号，如果2i > n(n为总节点数)，它无左子节点；
- 如下编号，如果2i + 1 <= n (n为总节点数)，它的右子节点编号为 2i + 1；
- 如下编号，如果2i + 1 > n (n为总节点数)，它无右子节点；
扩展知识
向上取整、向下取整
二叉树遍历
二叉树的常见遍历方式有4种：
- 前序遍历（Preorder Traversal）
- 中序遍历（Inorder Traversal）
- 后序遍历（Postorder Traversal）
- 层序遍历（Level Order Traversal）
前序遍历
遍历顺序：根节点 -> 前序遍历左子树 -> 前序遍历右子树（根 - 左 - 右）
中序遍历
遍历顺序：中序遍历左子树 -> 根节点 -> 中序遍历右子树（左 - 根 - 右）
（二叉搜索树的中序遍历的结果是升序或者降序的）
后序遍历
遍历顺序：后序遍历左子树 -> 后序遍历右子树 -> 根节点（左 - 右 - 跟）
层序遍历
前驱节点
中序遍历时的前一个节点
- 如果是二叉搜索树，前驱节点就是前一个比它小的节点
后驱节点
中序遍历时的后一个节点
- 如果是二叉搜索树，后驱节点就是后一个比它大的节点
若有收获，就点个赞吧
0 人点赞
