树介绍
在计算机科学中，树（英语：tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。
它是由 n（n>0）个有限节点组成一个具有层次关系的集合。它具有以下的特点：
- 每个节点都只有有限个子节点或无子节点；
- 没有父节点的节点称为根节点；
- 每一个非根节点有且只有一个父节点；
- 除了根节点外，每个子节点可以分为多个不相交的子树；
- 树里面没有环路(cycle)
树的分类
- 无序树：树中任意节点的子节点之间没有顺序关系，称为无序树，也称为自由树。
- 有序树：树中任意节点的子节点之间有顺序关系，为有序树：
- 二叉树
- 霍夫曼树
- B树
一些术语概念
- 结点：树上包含的一个数据元素；
- 根节点：树的开端的节点；
- 父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
- 子节点：一个节点含有的子树的根节点称为该节点的子节点；
- 兄弟节点：具有相同父节点的节点互称为兄弟节点；
- 节点的度：一个节点含有的子树的个数；
- 树的度：一棵树中，所有节点中度最大的称为树的度；
- 叶节点或终端节点：度 为零的节点；
- 非终端节点或分支节点：度不为零的节点；
- 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
- 深度：对于任意节点n，其深度为从根到n的唯一路径的长度，根的深度为0；
- 高度：对于任意节点n，其高度为从n到一叶子节点的最长路径长，所有叶子节点的高度为0；
- 树的深度：所有节点深度中的最大值；
- 树的高度：所有节点高度中的最大值；
- 一棵树可以没有任何阶段，则成为空树；
- 一棵树也可以只有一个节点，即根节点；
左右子树只在二叉树中有意义，因为二叉树非左即右：
- 左子树：以当前节点看，它的左子节点那一分支的子树，该子树以当前节点左子节点为根；
- 右子树：以当前节点看，它的右子节点那一分支的子树，该子树以当前节点右子节点为根；
二叉树
二元树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构；
- 每个节点的度最大为 2 （最多拥有两颗子树）；
- 左子树和右子树是有顺序的，即是某节点只有一个子树也要区分左右子树；
二叉树的性质
非空二叉树的第 i 层，最多有 2^i-1^ 个节点 (i ≥ 1)；
在高度为 h 的二叉树上最多有 2^h^ - 1 个节点 (h ≥ 1)；
对于任何一棵非空二叉树，如果叶子节点个数为n
0，度为 2 的节点个数为n2，则有：n0= n2+ 1；设度为 1 的节点个数为 n
1，那么二叉树的节点总数 n = n0+ n1+ n2，叉树的边数 T= n
1+ 2 * n2= n - 1 = n0+ n1+ n2- 1
真二叉树
真二叉树的所有节点的度要么为 0，要么为 2；
满二叉树
满二叉树的所有节点的度要么为 0，要么为 2，且所有叶子节点都在同一层；
在同样高度的二叉树中，满二叉树的叶子节点数量最多、总节点数量最多
满二叉树一定是真二叉树，真二叉树不一定是满二叉树；
假设满二叉树的高度为 h (h ≥ 1)，则有
- 第 i 层的节点数量为 2^i-1^
- 叶子节点数量为 2^h-1^
- 总节点数量 n = 2^h^ - 1 = 2^0^ + 2^1^ + 2^2^ + … + 2^h-1^
完全二叉树
完全二叉树的叶子节点只会出现在最后 2 层，且最后一层的叶子节点都靠左对齐；
也就是说，除最后一层外的其馀层都是满的，最后一层要么是满的，要么在右边缺少连续若干节点；
- 完全二叉树从根节点到倒数第二层是一棵满二叉树；
- 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树；
完全二叉树的性质
- 度为 1 的节点只有左子树；
- 度为 1 的节点要么是 1 个，要么是 0 个；
- 同样节点数量的二叉树，完全二叉树的高度最小；
假设完全二叉树的高度为 h ( h > 1 )，那么：
至少有 2^h-1^ 个节点( 2^0^ + 2^1^ + 2^2^ + … + 2^h-2^ + 1 )
最多有 2^h^ - 1 个节点(2^0^ + 2^1^ + 2^2^ + … + 2^h-1^，满二叉树)
总节点数量为 n，
- 2^h-1^ < n < 2^h^
- h - 1 < log2n < h
- h = floor(log2n) + 1
一棵有 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，它无右子节点；
若从 0 开始编号：
- 如果 i = 0，它是根节点；
- 如果 i > 0，它的父节点编号为 floor((i - 1)/2)；
- 如果 2i + 1 ≤ n - 1，它的左子节点编号为 2i + 1；
- 如果 2i + 1 > n - 1，它无左子节点；
- 如果 2i + 2 ≤ n - 1，它的右子节点编号为 2i + 2；
- 如果 2i + 2 > n - 1，它无右子节点；
测试题
如果一棵完全二叉树有768个节点，求叶子节点的个数
假设叶子节点个数为n0，度为1的节点个数为n1，度为2的节点个数为n2
总结点个数n = n0 + n1 + n2，而且n0 = n2 +1
n = 2 * n0 + n1 - 1
完全二叉树的 n1 要么为 0，要么为1
- n1为1时， n = 2* n0， n 必然是偶数；叶子节点个数n0= n/2，非叶子节点个数 n1 +n2 = n/2
- n1为0时， n=2 * n0 - 1， n 必然是奇数；叶子节点个数n0 = (n + 1)/2，非叶子节点个数 n1 + n2 = (n - 1) /2