在树——概述我们看到，任何树都可以表示成二叉树。二叉树和树是两个完全不同的概念，一个二叉树可以没有任何节点，树至少有一个节点。对于二叉树我们要区分左子树和右子树，而对于树来说，子树的顺序是无关紧要的。
1.二叉树定义：是有限多个结点的集合，这个集合或者是空集，或者由一个根结点和两棵互不相交的，分别成为左子树和右子树的二叉树组成。根据定义，二叉树有5种基本形态， 如下图所示。
2. 二叉树的性质：
1）在二叉树中，第i层的节点树最多为
,i>=1。（注：说的是具体哪一层的结点数，不是全部层数的结点数）
2）在深度为k的二叉树中，结点总数最多为
，k>=1.
3) 在任何非空的二叉树T，如果叶子结点的个数为n，而度为2的结点数m， 则 n = m + 1.
根据以上的性质，下面我们定义满二叉树和完全二叉树：
满二叉树：一棵深度为k且具有个结点的二叉树称为满二叉树。
完全二叉树：完全二叉树是由满二叉树而引出来的。对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结
点一一对应时称之为完全二叉树。
下图是完全二叉树的示例
下图是一个满二叉树的简单示例
3. 二叉树的存储表示：
1）数组存储表示：下图的编号方案给出了二叉树说的第一种存储表示方法。由于结点是从1到n进行编号的，因此，可以用一维数组来存储这些结点（这里不使用数组的第0个位置）
克一使用数组来表示任何二叉树，尽管在许多情况下，数组会有很多未用的空间。对于完全二叉树，由于这种存储表示不浪费任何存储空间，所以，这种存储表示是理想的。但对于倾斜二叉树（看下图）只有不到一半的数组空间得到利用。
倾斜二叉树 左边倾斜二叉树的数组存储表示
从上图可以看出，数组空间的利用率很低，因此我们要采取另一种存储方式。
2）链式存储表示：
虽然顺序存储表示对完全二叉树是可以接受的，但是对于许多其他的二叉树，这种存储表示却浪费了存储空间。此外，这种存储方式存在着与其他顺序存储表示方法一样的缺点，就是在中间插入和删除结点需要移动大量的结点。
二叉树采用链式存储可以克服上面的问题。在这种存储表示方法中，每个结点都有三个域——左儿子，数据，右儿子。Java实现如下：
class BTNode {
private int value;
private BTNode leftChild, rightChild;
public BTNode() {
value = 0;
leftChild = null;
rightChild = null;
}
public BTNode(int value, BTNode leftChild, BTNode rightChild) {
this.value = value;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
public BTNode(int value) {
this(value, null, null);
}
public BTNode getLeftChild() {
return leftChild;
}
public void setLeftChild(BTNode leftChild) {
this.leftChild = leftChild;
}
public BTNode getRightChild() {
return rightChild;
}
public void setRightChild(BTNode rightChild) {
this.rightChild = rightChild;
}
public int getValue() {
return value;
}
}
虽然这种结构难于确定结点的父亲，但它对于绝大多数应用都是令人满意的。若要知道结点的父亲，只需在结点中增加一个父亲域就OK了。