树的特点
- 由
根节点、子节点、兄弟节、父节点组成 - 没有任何节点的树叫做
空树 - 只包含一个节点的树，它的根节点也是该节点
- 一棵树又可划分为
左子树与右子树
树的几个概念含义
- 节点的度：节点的度是指其子树的个数
- 树的度：所有节点度中的最大值
- 叶子节点：度为
0的节点 - 非叶子节点：度不为
0的节点 - 层数（
level）：根节点在第一层，根节点的子节点在第二层，以此类推（有时候根节点是从0开始，依据需求来定） - 节点的深度（
depth）：从根节点到当前节点的唯一路径上的节点总数 - 节点的高度（
height）：从当前的节点到最远叶子节点的路径上的节点总数 - 树的深度：所有节点深度中的最大值
- 树的高度：所有节点高度中的最大值
树的分类
按照分类可以分为以下几种：
- 有序树：树中的任意节点的子节点之间有顺序关系
- 无序树：树中任意节点的子节点之间没有顺序关系，同时也成为
『自由树』 - 森林：由
m（m>=0）棵互不相交的树组成的集合 - 二叉树：每个节点的度
最大为2，左子树与右子树是有顺序的，即使某节点只有一棵子树，也需要区分左右子树
二叉树
二叉树是树中常用的结构，它有着如下的几个特性（假定 层数i是从1 开始）:
- 在非空二叉树的第
i层，最多有2^(i-1)个节点（i >= 1） - 在高度为
h的二叉树上最多有(2^h) - 1个节点（h >= 1） - 对于任何的一棵二叉树，如果叶子节点个数为
n0，度为2的节点个数为n2，则有：n0 = n2 + 1 - 假设度为1的节点个数为
n1，那么二叉树的节点总数n = n0 + n1 + n2 - 二叉树的边数
T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1
二叉树又分为以下几种类型:
- 真二叉树（
Proper Binary Tree）：所有节点的度要么为0，要么为2 - 满二叉树（
Full Binary Tree）：所有节点的度要么为0，要么为2，且所有的叶子节点都在最后一层 - 完全二叉树（
Compelete Binary Tree）：叶子结点只会出现在最后两层，且最后一层的叶子节点都靠左对齐
注意：
- 在同样高度的二叉树中，满二叉树的叶子节点数量最多，总结点数量最多
- 满二叉树一定是真二叉树，真二叉树不一定是满二叉树
- 完全二叉树从
根节点到倒数第二层是一棵满二叉树 - 满二叉树一定是完全二叉树，
完全二叉树不一定是满二叉树
完全二叉树
- 完全二叉树的基本属性:
- 度为
1的节点只有左子树 - 度为
1的节点要么是1个，要么是0个 - 同样节点数量的二叉树，完全二叉树的高度最小
- 假设完全二叉树的高度为
h（h >= 1），那么它至少有2^h-1个节点（n0 + n2），最多有 （2^h - 1）个节点(此时是一棵满二叉树) - 总结点个数为
n - 度为1的节点只有左子树
- 度为1的节点要么是
1个，要么是0个 - 同样节点数量的
二叉树，完全二叉树的高度最小
注意：
假如 完全二叉树 的高度为 h（h >= 1），总结点个数 n 个，那么有着以下重要特性：
- 2^(h-1) <= n < 2^h
- h-1 <= logn < h
- h = floor(logn) + 1（
floor是向下取整）
- 完全二叉树的性质
一棵有n个节点的完全二叉树（n > 0），从上到下、从左到右对节点从 1 开始进行编号，对任意第 i 个节点
- 如果
i = 1，它是根节点 - 如果
i > 1，它的父节点编号为floor(i/2) - 如果
2i <= n, 它的左节点编号为2i - 如果
2i > n，它无左子节点 - 如果
2i + 1 <= n，它的右子节点编号为2i + 1 - 如果
2i + 1 > n，它无右子节点
- 完全二叉树的节点之间的关系
如果一棵完全二叉树有768个节点，那么叶子节点的个数是多少？
假设叶子度为 0 的节点个数为 n0，度为 1 的节点个数为 n1，度为 2 的节点个数为 n2，那么总结点个数有这如下关系：
-
n = n0 + n1 + n2、n0 = n2 + 1 - 由
第1步得n = 2*n2 + n1 + 1或者n = 2*n0 + n1 - 1
由于完全二叉树度为 1 的数量要么是 0 ，要么是 1，所以这里分为两种情况：
- 当
n1 = 0的时候，n = 2 * n0 - 1，可以算出n0 = (n + 1) / 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)
