1.有关树的术语
1.结点
和链表类似，树存储结构中也将存储的各个元素称为“结点”。
对于树中某些特殊位置的结点，还可以进行更细致的划分，比如：
父结点（双亲结点）、孩子结点和兄弟结点：
树根结点（简称“根节点”）：特指树中没有双亲（父亲）的结点，一棵树有且仅有一个跟结点。
叶子结点（简称“叶节点”）：特指树中没有孩子的结点，一棵树可以有多个叶子结点。
2.子树
通常我们将一棵树中的几个结点构成的“小树”称为这棵树的“子树”。
树也可以这样定义：树是由根节点和若干棵子树构成的。
注意：单个结点也可以看作是一棵树，该节点即为根节点。
3.结点的度
一个结点拥有有子树的个数，就称为该节点的度。
比较一棵树中所有结点的度，最大的度即为整棵树的度。
4.结点的层次
从一课数的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推。树中结点层次的最大值，称为这棵树的深度或者高度。
5.有序树和无序数
如果一棵树中，各个结点左子树和右子树的位置不能交换，那么这棵树就称为有序树。反之，如果树中结点的左、右子树可以互换，那么这棵树就是一颗无序树。
在有序树中，结点最左边的子树称为“第一个孩子”，最右边的称为“最后一个孩子”。
6.森林
由m (m >= 0)个互不相交的数组成的集合就称为森林。
前面讲到，数可以理解为是由根结点和若干子树构成的，而这若干子树本身就是一个森林，因此树还可以理解为是由根结点和森林组成的。
7.空树
空树指的是没有任何结点的树，连根结点都没有。
总结：树是一种非线性存储结构，通常用来存储逻辑关系为“一对多”的数据。
使用树结构存储的各个结点，他们之前的关系类似于家谱中的成员关系，比如有父子关系、兄弟关系、表兄弟关系等。
2.二叉树
满足以下两个条件的数就是二叉树：
1.本身是有序树；
2.2树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；
二叉树具有以下几个性质：
1. 二叉树中，第 i 层最多有 2i-1 个结点。
2. 如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。
3. 二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。
二叉树还可以继续分类，衍生出满二叉树和完全二叉树。
满二叉树
如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。
满二叉树除了满足普通二叉树的性质，还具有以下性质：
1. 满二叉树中第 i 层的节点数为 2i-1 个。
2. 深度为 k 的满二叉树必有 2k-1 个节点 ，叶子数为 2k-1。
3. 满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底 层。 4. 具有 n 个节点的满二叉树的深度为 log2(n+1)。
完全二叉树
如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二
叉树被称为 完全二叉树。
完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质，比如说，n 个结点的完全
二叉 树的深度为 ⌊log2n⌋+1。 对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右
依次标号，对于任意一个结点 i ， 完全二叉树还有以下几个结论成立：
1. 当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）
2. 如果 2i>n（总结点的个数） ，则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2i 。
3. 如果 2i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2i+1 。