二叉树是n个结点的有限集合，它的定义具有递归性：
（1）当n=0时，为空树；
（2）当n=1时，只有一个结点，该节点称为根结点；
（3）当n>1时，除了根结点外的其他节点可分为互不相交的两个子集，称为左右子树，且左右子树本质上也都是二叉树。
图1二叉树
根据二叉树的结构和定义，可总结出二叉树的特点：
（1）非空二叉树的第i层最多有2∧（i-1）个结点；
（2）深度为k的二叉树最多有2∧k-1个结点
二叉树是非线性的结构，其每个结点最多有一个“前驱”，但可以有多个“后继”。它可以采用顺序存储结构和链式存储结构。
1、顺序存储结构
二叉树的顺序存储，就是用一组连续的存储单元存放二叉树的结点。必须把二叉树的所有结点安排成一个恰当的序列结点在这个序列中的相互位置能反映出结点之间的逻辑关系。
要介绍顺序存储结构，首先要了解一个概念——完全二叉树。如果深度为k，有n个结点的二叉树，当k与n满足2∧(k-1)≦n≦2∧k-1时，该二叉树称为完全二叉树。
对于一个二叉树，如果其不是一个完全二叉树，则首先增添一些并不存在的空结点，使之称为一个完全二叉树的形式，然后按照从上到下、从左到右的顺序将树中的结点存储在数组中。
以图1为例，其补成完全二叉树如图2所示。
图2补完后的二叉树
其顺序存储状态为：
ABCDE∧H∧∧FGI
显然，当一个非完全二叉树采用顺序存储结构时，由于需要增加许多空结点，因此会造成空间的大量浪费。
2、链式存储结构
二叉树的链式存储结构是指用链来表示二叉树结点之间的逻辑关系。
通常的方法是链表中的每个结点由3个域组成：
左指针域＋数据域＋右指针域
即：Lchild+data+Rchild
其中：data域存放结点的数据信息；
Lchild和Rchild分别存放左、右支的指针，当某一支不存在时，相应的指针域为空(用符号∧国NULL表示)。
如图1中的c结点，因其左支不存在，因此其Lchild的值为NULL。
二叉树常用的遍历方式有：前序遍历、中序遍历、后续遍历以及层序遍历。
1、前序遍历
先访问根结点，然后是左子树，最后是右子树。
图1的前序遍历结果为：
A->B->D->E->F->G->C->H->I
2、中序遍历
先访问左子树，然后是根结点，最后是右子树。
图1的中序遍历结果为：
D->B->F->E->G->A->C->I->H
3、后续遍历
先访问左子树，然后是右子树，最后是根结点。
图1的后续遍历结果为：
D->>F->G->E->I->H->B->C->A
4、层序遍历
从顶层的结点开始，从左向右依次遍历，之后转到第二层，继续从左向右遍历，……，直到所有的结点都遍历完成。
图1的层序遍历结果为：
A->B->C->D->E->H->F->G->I
