树的相关概念
在学习二叉树之前，我们需要先了解什么是树。
树的概念与结构
树是一种非线性的数据结构，与线性表不同，它是由 n(n>=0) 个有限节点组成一个具有层次关系的集合。之所以称之为树，是因为它看起来像是一颗倒挂的树，根是朝上的，叶子结点是朝下的。
- 它有一个特殊的节点，叫做根节点，这个节点是没有前驱节点的。
- 除了根节点之外，剩下的其他节点被分成 M(M>0) 个互不相交的集合 T1, T2, T3...Tm。其中一个集合 Ti(1<=i<=M) 又是一颗结构与树类似的子树。每棵子树的根节点有且只会有一个前驱，可以有 0 个或者多个后驱，因此，树是递归定义的。
注意：树形结构中，子树不能有交集，否则不是树形结构。
非树形结构的示例如下（子树中有交集）：
- 标有问号的就是子树中有交集的，这样就不是树形结构了，如果相交了，那就是图，不是树了。
- 除了根节点之外，其他节点有且仅有一个父节点。
- 一颗 N 节点的树有 N-1 条边。
树的相关术语
介绍树的相关术语，我们可以参考下图：
- 父节点/双亲节点：若一个节点含有子节点，那么这个节点成为其子节点的父节点；如 A 是 B 的父节点。
- 子节点/孩子节点：一个结点含有的子树的根节点成为该节点的子结点；如 B 是 A 的子结点。
- 结点的度：一个结点有几个孩子，那它的度就是多少；比如 A 的度是 6，F 的度是 2 等。
- 树的度：一棵树中，最大结点的度称为树的度，如上图中树的度为 6。
- 叶子结点/终端结点：度为 0 的结点成为叶结点，如 B、C、H、I 等。
- 分支结点/非终端结点：度不为 0 的结点，如 D、E、F、G 等。
- 兄弟结点：具有相同父结点的结点互相称为兄弟结点，如 B、C 是兄弟结点。
- 结点的层次：从根开始定义起，根为第 1 层，根的子结点是第 2 层，以此类推。
- 树的高度或者深度：树中结点的最大层次；如上图中树的高度为 4。
- 结点的祖先：从根到该结点所经分支上的所有结点；如 A 是所有节点的祖先。
- 路径：一条从树任意结点出发，沿父结点 - 子结点连接，达到任意结点的序列；比如 A 到 Q 的路径为 A-E-J-Q。
- 子孙：以某个结点为根的子树中任一结点都称为该节点的子孙。如所有节点都是 A 的子孙。
- 森林：由 m(m>0) 棵互补相交的树的集合称为森林。
树的表示方法
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。
在这么多方法里面，我们选择孩子兄弟表示法，这也是前辈们在最初探索树的时候想出来的，因为这种方法比较容易理解。
下面是树的结构体：
data;
};
