1. 树的概念及结构
树的概念
树是一种非线性的数据结构，与之相对的是顺序表、链表、栈和队列等线性的数据结构。它由n（n >= 0）个有限节点组成一个具有层次关系的集合。之所以被称为树是因为它的结构像一棵倒挂的树，也就是根朝上，而叶朝下。它具有以下特点：每个非根节点有且只有一个父节点，而每个节点有零个或多个子节点；没有父节点的节点称为根节点；除了根节点外，没个字节点可以分为多个不相交的树。
注意，树中的每个节点的左右子树都符合树的性质，也就是说树的定义是递归的，根节点是一棵树，根的左节点或者右节点又分别构成了不同的树。这一性质很重要，隐含着相当多的关于树的问题都可以通过递归来解决。
2. 与树相关的术语
- 节点的度：一个节点含有的子节点的个数称为该节点的度。
- 叶子节点：度为0的节点被称为叶子节点。
- 双亲节点/父节点：若一个节点含有子节点，则这个节点是它的子节点的双亲结点/父节点。
- 孩子节点/子节点：一个节点的子树的根节点称为这个节点的孩子节点/子节点。
- 兄弟节点：拥有相同的双亲节点的节点互为兄弟节点。
- 树的度：一棵树中，最大的节点的度称为这棵树的度。
- 节点的层次：从根开始算起，根为第1层，根节点的子节点称为第2层，以此类推。
- 树的高度/深度：树中节点的最大的层次称为树的高度/深度。
- 堂兄弟节点：双亲在同一层的节点互为堂兄弟。
- 节点的祖先：从根节点到该节点所经路径上所有的节点都是该节点的祖先。
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
- 森林：由m（m >= 0）棵不相交的树的集合称为森林。
3. 树的表示
树有多种表示方法：
- 双亲表示法
- 孩子表示法：只有指向孩子的指针，最常用。
- 孩子兄弟表示法：既有指向孩子的指针，还有指向兄弟的指针。
4. 二叉树
二叉树是一棵树，但其中的每个节点的度都不会超过2，即最多只会有左右孩子。
而且二叉树是一棵有序树，即孩子之间是有顺序的，不能颠倒。
5. 完全二叉树与满二叉树
- 满二叉树：如果一棵树的每层的节点数目都达到了最大值，则称之为满二叉树。
- 完全二叉树：假设一棵树有n个节点，而这n个节点与同层的满二叉树的前n个节点的位置完全相同，则称这棵树为完全二叉树。
6. 二叉树的存储
二叉树有两种最常见的存储方式，顺序存储与链式存储。
顺序存储即存储在数组里，一般这种存储方式只适合于完全二叉树的存储。
链式结构即用指针来存储节点间的对应关系，常见的链式存储的二叉树的节点结构如下：
struct BTreeNode {
int val;
struct BTreeNode* left;
struct BTreeNode* right;
}7. 二叉树的性质
- 对于一棵完全二叉树，从根节点开始按层编号，根节点为0号，以此类推。则一个编号为 i 的节点的两个子节点的编号为 i 2 + 1 和 i 2 + 2 。
- 接上条，一个编号为 i 的节点的双亲结点的编号为 (i - 1) / 2
- 若规定根节点的层数为1，则第 i 层最多有 $ 2^{i-1} $ 个节点
- 若规定根节点的层数为1，则高度为 i 的二叉树最多有 $ 2^{i}-1 $ 个节点
- 具有n个节点的完全二叉树的深度k为 $ log_2 (n+1) $
- 对于任意一棵二叉树，如果其叶节点的个数为 $ n_{0} $，度为2的节点的个数为 $ n_{2} $，则有$ n_{0} = n_{2} + 1 $
