树、二叉树分类以及内部节点的关系

树的特点

• 由 根节点、子节点、兄弟节、父节点 组成
• 没有任何节点的树叫做 空树
• 只包含一个节点的树，它的根节点也是该节点
• 一棵树又可划分为 左子树 与 右子树

树的几个概念含义

1. 节点的度：节点的度是指其子树的个数
2. 树的度：所有节点度中的最大值
3. 叶子节点：度为 0 的节点
4. 非叶子节点：度不为 0 的节点
5. 层数（level）：根节点在第一层，根节点的子节点在第二层，以此类推（有时候根节点是从0开始，依据需求来定）
6. 节点的深度（depth）：从根节点到当前节点的唯一路径上的节点总数
7. 节点的高度（height）：从当前的节点到最远叶子节点的路径上的节点总数
8. 树的深度：所有节点深度中的最大值
9. 树的高度：所有节点高度中的最大值

树的分类

按照分类可以分为以下几种：

1. 有序树：树中的任意节点的子节点之间有顺序关系
2. 无序树：树中任意节点的子节点之间没有顺序关系，同时也成为 『自由树』
3. 森林：由 m（m>=0）棵互不相交的树组成的集合
4. 二叉树：每个节点的度 最大为2 ，左子树与右子树是有顺序的，即使某节点只有一棵子树，也需要区分左右子树

二叉树

二叉树是树中常用的结构，它有着如下的几个特性（假定 层数i是从1 开始）:

1. 在非空二叉树的第 i 层，最多有 2^(i-1) 个节点（i >= 1）
2. 在高度为 h 的二叉树上最多有 (2^h) - 1 个节点（h >= 1）
3. 对于任何的一棵二叉树，如果叶子节点个数为 n0，度为2的节点个数为 n2，则有：n0 = n2 + 1
4. 假设度为1的节点个数为 n1，那么二叉树的节点总数 n = n0 + n1 + n2
5. 二叉树的边数 T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1

二叉树又分为以下几种类型:

1. 真二叉树（Proper Binary Tree）：所有节点的度要么为 0，要么为 2
2. 满二叉树（Full Binary Tree）：所有节点的度要么为 0，要么为 2，且所有的 叶子 节点都在最后一层
3. 完全二叉树（Compelete Binary Tree）：叶子结点只会出现在最后两层，且最后一层的叶子节点都靠左对齐

注意：

1. 在同样高度的二叉树中，满二叉树的叶子节点数量最多，总结点数量最多
2. 满二叉树一定是真二叉树，真二叉树不一定是满二叉树
3. 完全二叉树从 根节点到倒数第二层 是一棵满二叉树
4. 满二叉树一定是完全二叉树，完全二叉树 不一定是 满二叉树

完全二叉树

• 完全二叉树的基本属性:

1. 度为 1 的节点只有左子树
2. 度为 1 的节点要么是 1 个，要么是 0 个
3. 同样节点数量的二叉树，完全二叉树的高度最小
4. 假设完全二叉树的高度为h（h >= 1），那么它至少有 2^h-1个节点（n0 + n2），最多有 （2^h - 1）个节点(此时是一棵满二叉树)
5. 总结点个数为 n
6. 度为1的节点只有左子树
7. 度为1的节点要么是 1 个，要么是 0 个
8. 同样节点数量的 二叉树 ，完全二叉树的 高度 最小

注意：
假如 完全二叉树 的高度为 h（h >= 1），总结点个数 n 个，那么有着以下重要特性：

1. 2^(h-1) <= n < 2^h
2. h-1 <= logn < h
3. h = floor(logn) + 1（floor是向下取整）

• 完全二叉树的性质

一棵有n个节点的完全二叉树（n > 0），从上到下、从左到右对节点从 1 开始进行编号，对任意第 i 个节点

1. 如果 i = 1 ，它是根节点
2. 如果 i > 1，它的父节点编号为 floor(i/2)
3. 如果 2i <= n, 它的左节点编号为 2i
4. 如果 2i > n，它无左子节点
5. 如果 2i + 1 <= n，它的右子节点编号为 2i + 1
6. 如果 2i + 1 > n，它无右子节点

• 完全二叉树的节点之间的关系

如果一棵完全二叉树有768个节点，那么叶子节点的个数是多少？
假设叶子度为 0 的节点个数为 n0，度为 1 的节点个数为 n1，度为 2 的节点个数为 n2，那么总结点个数有这如下关系：

1. n = n0 + n1 + n2、n0 = n2 + 1
2. 由 第1步 得 n = 2*n2 + n1 + 1 或者 n = 2*n0 + n1 - 1

由于完全二叉树度为 1 的数量要么是 0 ，要么是 1，所以这里分为两种情况：

1. 当 n1 = 0 的时候，n = 2 * n0 - 1 ，可以算出 n0 = (n + 1) / 2
2. 当 n1 = 1 的时候，n = 2 * n0 ，可以算出 n0 = n / 2

大致也能得出结论，总节点如果是奇数，那么叶子节点 n0 = (n + 1) / 2，为偶数的时候，叶子节点个数为 n0 = n / 2

在计算的时候可以简化两种情况，因为最终获取的内容为整数，所以如果统一两种行为，可以选择统一使用奇数情况计算，也即 n0 = (n + 1) / 2。这个计算方法在节点数为奇数的情况下是没有问题的，但是如果是偶数的情况下，结果会出现小数，多出的小数实际上在偶数情况下是不需要的，为了容错，所以此时可以采取向下取整的方式将小数舍弃，进而进行偶数的容错，从而达到两种情况兼容的目的。

所以最终的方法可以通用以下的方式来算出度为0的节点个数：
floor((n + 1) >> 1)