47. 树

1. 基本术语

2. 二叉树性质

1. 在二叉树得第i(i >= 1)层最多有$2^{i-1}$个节点
2. 深度为k(k>=1)的二叉树上至多含$2^k-1$个节点
3. 对任何一颗二叉树，若它含有$n_0$个叶子节点、$n_2$个度为2得节点，则必存在关系式：$n_0=n_2+1$
4. 具有n个节点的完全二叉树的深度为$\lfloor{\log{_2n}+1} \rfloor$
5. 若对含n个节点的完全二叉树从上到下且从左到右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点（简称为结点i），有以下关系：
   1. 若i=1，则结点i是二叉树的根，无双亲节点；若i>1,则结点$\lfloor{i/2} \rfloor $为其双亲结点
   2. 若2i>n，则节点i无左孩子;否则结点2i为其左孩子；
   3. 若2i+1>n，则结点i无右孩子；否则，结点2i+1为其右孩子。