数据结构——初识树和二叉树
线性结构是一对一的关系，意思就是只有唯一的前驱和唯一的后继；
非线性结构，如树形结构，它可以有多个后继，但只有一个前驱；图形结构，它可以有多个前驱，也可以有多个后继。
树的定义
树是由根和子树组成，子树又是由子树的根和子树的子树组成，是一个递归的（嵌套的）结构。
示意图如下：
树的其他表现方式
树的基本术语
这个树的根有三个后继结点，每个后继结点只有一个前驱结点。
结点：数据元素以及指向子树的分支。
根结点：非空树中无前驱结点的结点，一个树当中，只有根节点没有前驱。
结点的度：结点拥有的子树数。
树的度：树内各结点的度的最大值。 上图树的度为3。
度为0的结点称为叶子结点，也叫终端结点。
度不为0的结点称为非终端结点，也叫分支结点。
内部结点：根结点以外的分支结点。
结点的子树的根称为该结点的孩子，该结点称为孩子的双亲。
兄弟结点：有共同双亲的结点。
堂兄弟：双亲在同一层的结点。
结点的祖先：从根到该结点所经分支上的所有结点。
结点的子孙：以某结点为根的子树中的任一节点。
树的深度：树中结点的最大层次。
有序树：树中结点的各子树从左至右有次序（最左边的为第一个孩子）。
无序树：树中结点的各子树无次序。
森林：是m（m>=0）棵互不相交的树的集合。
（1）把根节点删除树就变成了森林。
（2）一棵树可以看成一个特殊的森林。
（3）给森林中的各子树加上一个双亲结点，森林就变成了树。
树结构和线性结构的比较
| 线性结构 | 树结构 |
| 第一个元素（无前驱） | 根节点（无双亲） |
| 最后一个元素（无后继） | 叶子结点（无孩子） |
| 其他数据元素（一个前驱一个后继） | 其他结点——中间结点（一个双亲，多个孩子） |
| 一对一 | 一对多 |
二叉树的定义
为何要重点研究每结点最多只有两个的树?
- 二叉树的结构最简单，规律性最强;可以证明，所有树都能转为唯一对应的二又树，不失一般性。
- 普通树(多又树)若不转化为二又树，则运算很难实现
二叉树在树结构的应用中起着非常重要的作用，因为对二叉的许多操作算法简单，而任何树
都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。
二叉树是 n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的分别
称作这个根的左子树和右子树的二叉树组成。
特点：
1、每个结点最多有两个孩子（二叉树中不存在度大于2的结点）。
2、子树有左右之分，其次序不能颠倒。
3、二叉树可以是空集合，根可以有空的左子树或空的右子树。
注意：二叉树不是树的特殊情况，它们是两个概念。
二叉树结点的子树要区分左子树和右子树，即使只有一棵树也要进行区分，说明它是左子树还是右子树。
（也就是二叉树每个结点位置或者说次序都是固定的，可以是空，但是不可以说它没有位置，而树的结点位置是相对于别的结点来说的，没有别的结点时，它就无所谓左右了）。
二叉树的5种基本形态
注：虽然二叉树和树的概念不同，但有关树的基本术语对二叉树都适用。
二叉树的性质
- 在二叉树的第i层上至多有
个结点
- 深度为k的二叉树至多有
-1个结点
- 对于任何一颗二叉树，如果其终端节点数为n，度为2的节点数为m，则n=m+1
满二叉树：深度为k且含有-1个结点的二叉树，即每i层都有个结点
完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。
完全二叉树的特点：
(1）叶子结点只可能在层次最大的两层上出现；
(2)对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为1或l+1。