概念
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的二叉树组成
满二叉树
所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上
完全二叉树
如果一棵具有N个结点的二叉树的结构与满二叉树的前N个节点 的结构相同，称为完全二叉树（特别说明：满二叉树是特殊的完全二叉树，而完全二叉树不一定是满二叉树）
二叉树的性质
若规定根节点的层次为1，则一棵非空二叉树第n层上最多有2^（n-1）（n>=1）个结点，（^代表次方）
若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大结点数是2^ (n-1) (n>=0)，特别说明：这里的深度与上面的层次概念只不过是换一种的说法
对任何一棵二叉树，如果其叶结点个数为n0，度为2的非叶结点个数为n2,则有n0 = n2+1
具有n个结点的完全二叉树，如果按照从上至下从左到右的顺序对所有结点从1开始编号，则对于序号为i的结点有：
如果i>1，则序号为i的结点的双亲结点的序号为i/2取整 如果i=1，则序号为i的结点为根节点，无双亲结点
如果2i<n，则序号为i的双亲结点的左孩子序号是2i右孩子序号是2i+1 如果2i>=n，则序号为i结点无右孩子结点
如果2i+1<=n，则序号为i结点的右孩子结点的序号为2i+1
如果2i+1>n，则序号为i结点无右孩子结点
二叉树的存储结构
顺序存储（就是用一组连续的存储单元存放二叉树中的结点）
优点：存储完全二叉树，简单省空间，如上图
缺点：对一般二叉树尤其单支树，存储空间利用不理想，如上图
链式存储（就是用链表来表示一棵二叉树，即用链来指示元素的逻辑关系）
包含数据域和左右指针域的链表
增加一个双亲字段parent,用来指向其双亲结点的链表
二叉树的基本操作
二叉树的创建
依照顺序存储结构来创建（如上的存储结构所述）
依照链式存储结构来创建（如上的存储结构所述）
二叉树的遍历
前序遍历（遵循先遍历双亲结点后再遍历左结点最后才遍历右结点的顺序，简称：中左右）打印的顺序为：12485367
中序遍历（遵循先遍历左结点后遍历双亲结点再最后才遍历右结点的顺序，简称：左中右）打印的顺序为：84251637
后序遍历（遵循先遍历左结点后遍历右结点再最后才后遍历双亲结点的顺序，简称：左右中）打印的顺序为：84526731
层序遍历（前面的都是深度优先而层级遍历则是广度优先）打印顺序为：12345678
