二叉树
二叉树定义
二叉树（Binary Tree）是n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
二叉树特点：
1.每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。没有子树或者有一棵子树是可以的，最多有两棵子树。
2.左子树和右子树是有顺序的，次序不能颠倒。
3.即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。
二叉树具有五种基本形态：1.空二叉树；2.只有一个根结点；3.根结点只有左子树；4.根结点只有右子树；5.根结点既有左子树又有右子树。
二叉树的性质
性质一：在二叉树的第i层上至多有 2i−1 个结点（i≥1）。—–归纳法
性质二：深度为k的二叉树至多有 2k−1 个结点（k≥1）。—–归纳法
性质三：对任何一棵二叉树T，如果其终端结点数为 n0，度为2的结点数为 n2，则 n0=n2+1。
设 n1 为度是1的结点数，那么T结点总数 n=n0+n1+n2 。换个角度，数数连接连线，因为根结点只有分支出去，没有分支进入，所以分支线总数为结点总数减去1，分支线总数为 n−1=n1+2n2 ，两个式子相减得到 n0=n2+1。
性质四：具有n个结点的完全二叉树的深度为 |log2n|+1（其中|x|表示不大于x的最大整数）。
性质五：如果对一棵有n个结点的完全二叉树（深度为 |log2n|+1）的结点按层序编号（从第1层到第 |log2n|+1层，每层从左到右），对任一结点i（1≤i≤n）有：
1.如果 i=1，则结点i是二叉树的根，无双亲；如果 i>1，则其双亲是结点|i/2|。
2.如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
3.如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。
二叉树顺序存储结构
二叉树比较特殊，所以可以使用顺序存储结构可以实现。二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，例如双亲与孩子的关系，左右兄弟的关系等等。完全二叉树的存储可以根据结点的编号来存储，一般的二叉树，尽管层序编号不能反映逻辑关系，但是可按完全二叉树编号，将不存在的结点设置为“∧”。若是考虑极端情况，例如右斜树，k个结点，却分配 2k−1 个存储单元空间，浪费了存储空间。所以，顺序存储结构一般只用于完全二叉树。
二叉树的建立
建立二叉树，其实也利用了递归的原理，只不过在打印结点的地方，改成生成结点、给结点赋值的操作。当然也可以用中序或后续遍历的方式实现二叉树的建立，只是结点生成和左右子树的构造顺序需要交换一下，另外，输入的字符也要相应的变化。
基本方法及源码
1 |
特殊二叉树
斜树
所有的结点都只有左子树的二叉树叫左斜树。所有的结点都是只有右子树的二叉树叫右斜树。这二者统称为斜树。斜树有明显特点，每一层都只有一个结点，结点的个数和二叉树的深度相同。斜树和线性表结构一样，线性表结构是树的一种特殊表现形式。
满二叉树
在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。单是每个节点都存在左右子树，不能算是满n二叉树，还必须要所有的叶子结点都在同一层上，这样就做到了整棵树的平衡。所以，满二叉树的特点是：1.叶子只能出现在最下一层，出现在其他层就不能达到平衡；2.非叶子结点的度一定是2；3.在同样深度的二叉树中，满二叉树的结点最多，叶子数最多。
完全二叉树
对一棵具有n个结点的二叉树 按层序编号 ，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这颗二叉树称为完全二叉树。
完全二叉树的特性：
（1）叶子结点只能出现在最下两层。
（2）最下层的叶子一定集中在左部连续位置。
（3）倒数第二层，若有叶子结点，一定都在右部连续位置。
（4）如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。
（5）同样结点数的二叉树，完全二叉树的深度最小。
二叉链表
二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域，称这样的链表叫做二叉链表。下面列出二叉链表的结点结构定义代码：
/二叉树的二叉链表结点结构定义/
typedef struct BitNode{ //结点结构
TElemType data; //结点数据
struct BiTNode lchild,rchild; //左右孩子指针
}BitNode，*BiTree；