1. 二叉树的定义：二叉树( Binary Tree )是n( n≥0 )个结点的有限集合，该集合或者空集( 称为空二叉树 )，或者由一个根节点和两棵互不相交的，分别称为根节点的左子树和右子树的二叉树组成。例如：图中就是一颗二叉树。
2. 二叉树的特点：
1>. 每个结点最多有两棵子树。
2>. 左子树和右子树是有顺序的。
3>. 即使树中某结点只有一棵子树，也要区分左右。
3. 二叉树的特殊情况：
1>. 斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都只有右子树的二叉树叫右斜树 所以在极端情况下二叉树会退化成线性表（线性表是树的特殊表现形式），这种情况也称之为非平衡树。例如：
2>. 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树 满二叉树是一种平衡二叉树。例如：
3>. 完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，( 即树中结点的分布从左到右依次布满 )则这颗二叉树称为完全二叉树 完全二叉树也是一种平衡二叉树。例如：
4. 完全二叉树的特点：
1>. 叶子节点只能出现在最下两层。
2>. 最下层的叶子一定集中在左部连续位置。
3>. 倒数二层，若有叶子结点，一定都在右部连续位置。
4>. 如果结点度为1，则该结点只有左孩子。
5>. 同样结点个数的二叉树，完全二叉树的深度最小。
5. 二叉树的性质：
1>. 在二叉树的第i层上至多有2^( i−1 )个结点( i≥1 )。
2>. 深度为k的二叉树至多有2^k−1个结点( k≥1 )。
3>. 对任何一棵二叉树，如果终端结点数为n0，度为2的结点数为n2，则n0= n2+1。
4>. 具有n个结点的完全二叉树的深度为⌊log2n⌋+1。
5>. 如果对于一棵有n个结点的完全二叉树的结点按层序编号
如果i=1，结点无双亲；如果i＞1，则双亲是⌊i/2⌋；
如果2i>n，则结点i无左孩子；否则其左孩子为2i；
如果2i+1>n，则结点i无右孩子；否则有孩子为2i+1。
注意：" ⌊ ⌋ "符号表示向下取整。
6. 二叉树的顺序存储结构：二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现出之间的逻辑关系。如：
但是顺序存储结构在极端情况下浪费空间，只适合平衡树的存储。
7. 二叉树的链式存储结构：二叉树每个结点最多有两个孩子，所以设计为一个数据域和两个指针域的结点进行链接，这种链表也叫作二叉链表。
如图是二叉链表结点的定义：
如图是二叉树的链式存储结构：
8. 二叉树的遍历：主要分为两类：深度优先遍历DFS和广度优先遍历BFS
1>. 深度优先遍历：前序遍历，中序遍历，后序遍历
2>. 广度优先遍历：层序遍历
9. 深度优先遍历：
1>. 前序遍历( DLR )：规则是若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。
2>. 中序遍历( LDR )：规则是若二叉树为空，则空操作返回，否则从根结点开始，中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树。
3>. 后序遍历( LRD )：规则是若二叉树为空，则空操作返回，否则从根结点开始，后序遍历根节点的左子树，然后后序遍历右子树，最后访问根节点。
10. 广度优先遍历：
层序遍历：规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
