树的相关概念
在深入二叉树之前，先理解通用的树结构。生活中常见的树根在下、枝叶在上，而数据结构中的树是倒置的，根节点朝上，叶子节点朝下。
1. 树的概念与结构
树是一种非线性的数据结构，由 n(n>=0) 个有限节点组成一个具有层次关系的集合。它有一个特殊的节点叫做根节点，这个节点没有前驱节点。除了根节点之外，剩下的其他节点被分成 M(M>0) 个互不相交的集合，每个集合本身又是一棵结构与树类似的子树。每棵子树的根节点有且只会有一个前驱，因此树是递归定义的。
这里要注意一点：树形结构中，子树不能有交集，否则就不是树形结构了，相交了就变成了图。除了根节点之外，其他节点有且仅有一个父节点。一颗 N 节点的树有 N-1 条边。
2. 树的相关术语
为了更清晰地描述树的结构，我们需要掌握一些基本术语。以一张典型的树为例：
- 父节点/双亲节点：若一个节点含有子节点，那么这个节点成为其子节点的父节点。
- 子节点/孩子节点：一个结点含有的子树的根节点成为该节点的子结点。
- 结点的度：一个结点有几个孩子，那它的度就是多少。
- 树的度：一棵树中，最大结点的度称为树的度。
- 叶子结点/终端结点：度为 0 的结点成为叶结点。
- 分支结点/非终端结点：度不为 0 的结点。
- 兄弟结点：具有相同父结点的结点互相称为兄弟结点。
- 结点的层次：从根开始定义起，根为第 1 层，跟的子结点是第 2 层，以此类推。
- 树的高度或者深度：树中结点的最大层次。
- 结点的祖先：从根到该结点所经分支上的所有结点。
- 路径：一条从树任意结点出发，沿父结点 - 子结点连接，达到任意结点的序列。
- 子孙：以某个结点为根的子树中任一结点都称为该节点的子孙。
- 森林：由 m(m>0) 棵互补相交的树的集合称为森林。
3. 树的表示方法
树结构相对线性表就比较复杂了，要存储表示起来比较麻烦。既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。
在这么多方法里面，我们选择孩子兄弟表示法，这也是前辈们在最初探索树的时候想出来的，因为这种方法比较容易我们理解。
下面是树的结构体：
struct TreeNode {
struct TreeNode* child; // 指向第一个孩子
struct TreeNode* brother; // 指向下一个兄弟
int data; // 结点中的数据域
};
