树 Tree

以下面的树为例子

节点

• 节点：图中 1、2、3 等都是这棵树的节点
• 根节点：1
• 父节点：例如 1 是 2、3、4、5、6 的父节点，2 是 21、22的父节点
• 子节点：与父节点相反，2、3、4、5、6 是 1 的子节点，21、22 是 2 的子节点
• 兄弟节点：同一个父节点下的子节点互为兄弟节点，例如 21 和 22 是兄弟节点
• 空树：一棵树没有任何节点，包括没有根节点
• 一棵树可以只有一个节点，也就是根节点

子树

• 子树：一棵树可以有很多节点，而其中除了整体是一棵树外，其中的子节点也可以单独看成一棵树，例如 2、21、22、221、222、223 就是一颗子树
• 左子树：左侧的子节点称为左子树，例如 21 构成 2 的左子树
• 右子树：右侧的子节点称为右子树，例如 22（及其子节点） 构成 2 的右子树

度

• 节点的度：子树的个数，即子节点的个数，就是节点的度，例如根节点 1 有 5 个子节点，所以根节点 1 的度是 5。
• 树的度：所有节点的度的最大值，例如这棵树节点度最大的是根节点，所以这棵树的度是5
• 叶子节点：度为 0 的节点，即没有子节点的节点
• 非叶子节点：度不为 0 的节点，即有子节点的节点

深度

• 层数：根节点在第一层，根节点的子节点在第 2 层，以此类推（有些教科书可能从第 0 层开始计算）
• 节点的深度：从根节点到当前节点的唯一路径上的节点总数
  • 节点 2 的深度：1->2，经历2个节点，所以深度为2
  • 节点 223 的深度：1->2->22->223，经历 4 个节点，所以深度是 4
• 节点的高度：从当前节点到最远叶子节点的路径上的节点总数
  • 节点 2 的高度：2->22->221，经历 3 个节点，所以高度是 3
  • 节点 223 的高度: 223，只有一个节点，所以高度是 1
• 树的深度：所有节点深度的最大值，例如本树深度为 4
• 树的高度：所有节点高度的最大值，例如本树高度为 4

树的分类

• 有序树：树中任意节点的子节点之间有顺序关系，如果两棵树所有的值都一样，但是其中的子节点顺序不一样，就是两颗不同的有序树
• 无序树：树中任意节点的子节点之间没有顺序关系，也称为自由树
• 森林：由m（m >= 0）棵互不相交的树组成的集合

二叉树 Binary Tree

二叉树的性质

• 二叉树中每个节点的度最大为 2，即一个节点最多有 2 棵子树
• 二叉树中节点的左子树和右子树是有顺序的，例如所有节点的左子节点小于右子节点
• 即使某节点只有一棵子树，也要分左右子树

• 非空二叉树的第 $i$ 层的节点数量最多为 $2^{i-1},(i\geq1)$
• 高度为 $h$ 的二叉树最多有 $2^h-1$ 个节点 $(h\geq1)$
• 对于任意一棵非空二叉树，如果叶子节点的个数为 $n_0$，度为 2 的节点个数为 $n_2$，则有 $n_0=n_2+1$
  • 证明：设度为 1 的节点个数为 $n_1$，则二叉树总结点数 $n=n_0+n_1+n_2$，二叉树边数既满足 $T=n_1+2n_2$（计算节点脚下的边），也满足 $T=n-1$（计算节点头顶的边），结合三式，推出 $n_0=n_2+1$

真二叉树

• 真二叉树即所有的节点的度要么为 0，要么为 2

满二叉树

• 满二叉树即所有的节点的度要么为 0，要么为 2，且所有叶子节点都在最后一层
• 满二叉树一定是真二叉树，真二叉树不一定是满二叉树
• 在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多

• 满二叉树的第 $i$ 层的节点数量为 $2^{i-1}$
• 满二叉树的高度 $h$ 和 总节点数 $n$ 有如下关系
  • $n=2^h-1$
  • $h=log_2(n+1)$

完全二叉树

• 完全二叉树的叶子节点只会出现在最后 2 层，且最后 1 层的的叶子节点都靠左对齐
• 完全二叉树从根节点到倒数第二层是一棵满二叉树
• 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

• 度为 1 的节点只有左子节点
• 度为 1 的节点要么有 1 个，要么有 0 个
• 同样节点数量的二叉树，完全二叉树的高度最小
• 高度为 $h$ 的完全二叉树
  • 至少有 $2^{h-1}$ 个节点
  • 至多有 $2^h-1$ 个节点（满二叉树）
• 高度 $h$ 和 总节点数 $n$ 有如下关系
  • $2^{h-1} \leq n$
  • $n \leq 2^h-1$
  • $h-1 \leq n < h$，注意左闭右开
  • $h=floor(log_2n)+1$ ，$floor()$ 为向下取整函数，Java 中若使用强制转型，转成整型默认为向下取整
• 对于一棵节点数为 $n$ 的完全二叉树（$n>0$），如果按照从上到下，从左到右的顺序从 1 开始进行编号，则对任意第 $i$ 个节点：
  • 若 $i=1$，则该节点为根节点
  • 若 $i>1$，则它的父节点编号为 $floor(i/2)$
  • 若 $2i \leq n$，则它的左子节点编号为 $2i$
  • 若 $2i>n$，则它无左子节点（该节点为叶子节点）
  • 若 $2i+1 \leq n$，则它的右子节点编号为 $2i+1$
  • 若 $2i+1>n$，则它无右子节点（该节点不一定是叶子节点）
• 对于一棵节点数为 $n$ 的完全二叉树（$n>0$），如果按照从上到下，从左到右的顺序从 0 开始进行编号，则对任意第 $i$ 个节点：
  • 若 $i=0$，则该节点为根节点
  • 若 $i>0$，则它的父节点编号为 $floor(\frac{i-1}{2})$
  • 若 $2(i+1) \leq n$，则它的左子节点编号为 $2i+1$
  • 若 $2(i+1)>n$，则它无左子节点（该节点为叶子节点）
  • 若 $2(i+1)+1 \leq n$，则它的右子节点编号为 $2i+2$
  • 若 $2(i+1)+1>n$，则它无右子节点（该节点不一定是叶子节点）
• 对于完全二叉树，若总节点数 $n$ 为偶数，则最后一个节点为左子节点，若总节点数 $n$ 为奇数，则最后一个节点为右子节点
• 总节点数为 $n$ 的完全二叉树，其叶子节点数量为 $floor(\frac{n+1}{2})$

参考

• 恋上数据结构与算法（第一季）
• 小码哥《恋上数据结构与算法》笔记（七）：二叉树