树（ Tree ）是一种非常重要的非线性数据结构，是以分支关系定义的层次结构，很像自然界中倒挂的树，经常用来描述具有层次关系的问题。二叉树是最常用的树形结构。
树是由一个或多个结点组成的有限集合，它或者为空，称为空树，或者非空（至少有一个结点）。对于非空树，有且仅有一个结点称为树的根，其余结点分属于 m （ m ≥0）个互不相交的集合。每个集合又构成一棵树，称为根结点的子树，并且树的根结点是每棵子树根结点的前驱，而每棵子树的根结点是所在树的根结点的后继。
在一棵非空树中，每个结点的后继结点个数称为该结点的度；树中所有结点的度中最大值称为树的度；度数为0 的点称为叶子结点，不为0 的点称为分枝点；结点的后继结点称为该结点的子女结点，该结点称为子女结点的双亲，同一个双亲结点的子女结点称为兄弟；每个结点的子树中的所有结点称为该结点的子孙，而从树根到达该结点所经过的结点称为该结点的祖先；树根称为第一层，它的子树称为第二层，以此类推，树中结点的最大层数称为树的高度或深度；规定了子树次序的树称为有序树，否则称为无序树。
二叉树（ Binary Tree ）是有限个结点的集合，该集合或者为空，或者由一个称为根的结点及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。
二叉树是有序树，即使树中结点只有一棵子树，也要区分它是左子树还是右子树。因此二叉树具有5 种基本形态：空二叉树，单个结点二叉树，只有左子树的二叉树，只有右子树的二叉树，左右子树都有的二叉树。
在一棵二叉树中，当第 i 层的结点数为2i-1 个时，称此层的结点是满的。当树中每一层都满时，称此树为满二叉树。
在一棵二叉树中，除最后一层外，其他各层都是满的，并且最后一层或者是满的，或者在最右边缺少连续若干个结点，则称此树为完全二叉树。
二叉树的存储通常采用链式存储结构。每一个结点由3 个域组成，1 个数据域，两个指针域，分别存放左子树和右子树根结点的地址。
[left] [data] [right]
data 存放结点的数据， left 与 right 分别存放左子树和右子树根的地址，当左子树或右子树不存在时，相应指针域值为空（用 NULL 或∧表示）。
二叉树的遍历是二叉树中非常重要的运算，在很多程序设计中都有应用。所谓二叉树遍历就是按一定的次序访问二叉树中的所有结点，并且每个结点值仅被访问一次的过程。