47. 树
基本术语
二叉树性质
- 在二叉树得第i(i >= 1)层最多有$2^{i-1}$个节点
- 深度为k(k>=1)的二叉树上至多含$2^k-1$个节点
- 对任何一颗二叉树，若它含有$n_0$个叶子节点、$n_2$个度为2得节点，则必存在关系式：$n_0=n_2+1$
- 具有n个节点的完全二叉树的深度为$\lfloor{\log{_2n}+1} \rfloor$
- 若对含n个节点的完全二叉树从上到下且从左到右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点（简称为结点i），有以下关系：
- 若i=1，则结点i是二叉树的根，无双亲节点；若i>1,则结点$\lfloor{i/2} \rfloor $为其双亲结点
- 若2i>n，则节点i无左孩子;否则结点2i为其左孩子；
- 若2i+1>n，则结点i无右孩子；否则，结点2i+1为其右孩子。
定义
树（Tree）是n(n >= 0 )个结点的有限集。n = 0时称为空树。在任意一棵非空树中：（1）有且仅有一个特定的称为根（root）的结点；（2）在 n > 1 时，其余结点可分为m（m > 0）个互不相交的有限集 $T_1, T_2, T_3 … T_m$，其中每一个集合本身又是一颗树，并且称为根的子树（SubTree）。
n > 0时根结点是唯一的，不可能存在多个根结点。
m > 0时，子树的个数没有限制，但他们一定是互不相交的。
结点用用改的子树数称为结点的度。
度为0的结点称为叶子结点或终端结点；度不为0的结点称为非终端结点或分支结点。
除根结点之外，分支结点称为内部节点。
树的度是树内各结点度的最大值。
为什么$n$个结点的树，有$n - 1$条边
- 假设有1个结点时，则有0条边
- 有2个结点时，若是连通的且不能为环，所以就得有$1$条边将这两个结点连接在一起
- 若有3个结点时，将前两个看为一个整体，则必须有$1$条边，将这两个部分连接在一起
- 以此类推
【释】：整体化一思想