数据结构之二叉树
Before：树
树形结构可以说是一种很重要的非线性结构了，其中以树和二叉树最为常用。
树（Tree）是具有n(n≥0)个结点的集合，在一颗非空树中，其具备有如下几个特征：
- 有且仅有一个特定的称为**根(Root)**的结点。
- 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T₁ ,T₂ ,…, Tₘ，其中每个集合本身又是一棵树，并且称为根的子树(Sub Tree)。如下图中的T₂ ={C,G}就是根A的一个子集。
因树下有树，树下还有树。可知，树的结构定义是一个递归的定义，即在树的定义中又用到了树的概念。那么在表示树的形式方面就还有其它的方法。如以嵌套集合的形式、广义表的形式、凹入表示法等。这里不作演示，按易于理解的来。
基本术语
一棵树中，结点是构成其的基本单位。结点包含一个数据元素及若干指向其它子树的分支。结点拥有的子树数称为结点的度（Degree），而度为0 的结点就称为叶子结点或终端结点，度不为0的结点称为非终端结点或分支结点。除根结点外，分支结点也称为内部结点。而一个树的度就是指树各内部结点的度的最大值。
结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲，而同一个双亲的孩子之间又互称为兄弟。其它什么祖先、子孙呀，相信大家用指头数数就懂了。
结点的层次（Level）从根开始定义起，根为第一层，其孩子就为第二层。树中结点的最大层次称为树的深度或高度。
如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。
About：二叉树
二叉树（Binary Tree）是另外一种树型结构，它的特点是每个结点至多只有两颗子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。由此可知，二叉树是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成的。
在二叉树中，具备以下性质需要谨记（可自推）：
- 在二叉树的第i层上至多有2ᶤ⁻¹个结点（i≥1）。
- 深度为k的的二叉树至多有2ᵏ-1各结点（k≥1）。
- 若一颗二叉树，其有n0个叶子结点，n2个度为2的结点，则n0=n2+1。
其中我们称一颗深度为K且有2ᵏ -1个结点的二叉树为满二叉树。即在满二叉树中，每一层的结点数都是最大的结点数。而对于叶子结点只可能在层次最大的两层上出现，且当其右分支下的子孙的最大层次为L，则其左分支下的子孙的最大层次为L或L+1的树，我们称其为完全二叉树。
初始化
对于二叉树，我们也有两类存储结构来存储——顺序和链式。
顺序存储结构
在顺序存储结构中我们规定用一组地址连续的存储单元依次自上而下、自左至右存储二叉树上的各结点，不存在的结点用‘0’表示。这种方式对于完全二叉树还是蛮适用的，可对于一般的二叉树而言却提不起精神。如有一颗深度为K且只有K个结点的单只树（树中不存在度为2的结点），却需要长度为2ᵏ⁻¹的一维数组来存储，可以说，这是及其浪费存储空间，所以我们一般采取链式存储的方式来存储二叉树。