二叉树的基本概念就不介绍了，这里主要学习二叉树的各种算法
建立二叉树
我们要建立如下的一棵树 
首先我们来看一下一棵树的结构
class MyTree {
String data;// 节点数据
MyTree left;// 左节点
MyTree right;// 右节点
}之后我们写一个增加节点的方法
/*
* tree 代表要在那个节点下建立子节点 child 带便建立左边节点还是右边 0代表左边 1代表右边 value 代表值
*/
public MyTree add(MyTree tree, int child, String value) {
MyTree newTree = new MyTree();
newTree.data = value;
if (child == 0) {
// 左边
tree.left = newTree;
} else {
// 右边
tree.right = newTree;
}
return newTree;
}我们新建一棵树，用传入的data来给节点赋值，用child 来判断我们这棵新树应该加在父亲树的左节点还是又节点
初始化一棵树
现在我们初始化我们在开头时提出的那棵树
public MyTree init() {
// 创建根节点
MyTree rootTree = new MyTree();
// 设置root节点的数据
rootTree.data = "A";
rootTree.left = null;
rootTree.right = null;
// 创建左侧节点
MyTree treeB = add(rootTree, 0, "B");
MyTree treeC = add(treeB, 0, "C");
MyTree treeD = add(treeB, 1, "D");
// 创建右侧节点
MyTree treeE = add(rootTree, 1, "E");
MyTree treeF = add(treeE, 0, "F");
MyTree treeG = add(treeE, 1, "G");
return rootTree;
}结合刚才讲的 add 方法，你应该可以理解这棵树的建立过程，但这里我是写死的你可以按照自己的方式去实现
先序遍历（DLR）
这个理解了就很简单，D代表的就是中间，L代表左边，R代表右边
先序遍历的方式，说白了讲，就是每一个节点先输出自己的值，然后喊左边输出，然后再喊右边输出
所以输出的应该是：ABCDEFG
再讲一下过程：
A先输出自己值，然后他先让左边（L）输出。
左边的B得到指令后先输出自己值（D），然后再通知自己的左边。
这时候左边的C（L）输出自己的值，然后，B再去通知自己的右边D。
D输出自己的值。
这时候A左侧已经输出完了，然后A就可以通知右边的E开始输出。
下面看一下代码：
// 先序便利
public void DLR(MyTree tree) {
if (tree == null)
return;
System.out.print(tree.data);
DLR(tree.left);
DLR(tree.right);
}我们把节点传入以后，方法首先会判断是否为空，为空直接结束，这是我们整个递归的结束条件，如到叶子节点（C、D、F、G）后，他们的左右节点就是null
如果不为空，我们就先让节点输出自己的信息(D),之后开始递归，让自己的左右节点继续去执行这个方法。
中序遍历(LDR)
请大家参考一下先序遍历（DLR），你大概已经能猜出来，中序遍历的逻辑是，每个节点 先通知自己左边的节点去输出，左边输出完毕后,节点自身再输出，最后去通知右边的节点去输出。
那这个中序遍历的结果应该是：CBDAFEG
// 中序遍历
public void LDR(MyTree tree) {
if (tree == null)
return;
LDR(tree.left);
System.out.print(tree.data);
LDR(tree.right);
}可以说和上面的先序遍历一模一样,就是顺序变了，如果你仔细观察应该不难发现D在LDR这样的位置的什么地方，就是什么遍历，在第一位就是先序遍历，在中间就是中序遍历，在最后就是我们等下要讲的后续遍历。
而D在什么位置，输出就在什么位置。
后序遍历(LRD)
后续遍历就是每一个节点先让左边的输出完毕，再让右边的输出完毕，最后自己输出
那这里的结果就是：CDBFGEA
// 后序遍历
public void LRD(MyTree tree) {
if (tree == null) {
return;
}
LRD(tree.left);
LRD(tree.right);
System.out.print(tree.data);
}一样先检查是否为空，不为空左边节点递归，然后右边节点递归，最后自己输出。
层次遍历
层析遍历就是按树的层，一层一层下去遍历
比如这棵树中的层次遍历就是：ABECDFG
先讲一下实现的思路
这里我们会用到队列这个概念，我们知道队列的特点是先进先出
那么我们新建一个队列，把根节点放进去，然后出队，输出自己的值，之后再取这个节点的左节点放入队列，之后是右节点，再重复上述的过程，知道队列变空。
来看一下这张图会理解的更加好
我们每一次都从队列中出一个节点，之后，再把他的子节点放入，同时利用先进先出这个特点来确保按层输出
下面看一下代码
/*层次遍历*/
public void traversalG(MyTree rootTree){
MyQueue myQueue = new MyQueue(20);//新建一个队列长度为20
myQueue.add(rootTree);//将节点放入队列
while(!myQueue.isEmpty()){//如果队列为空，结束
MyTree popTree=(MyTree)myQueue.pop();//出队一个
System.out.print(popTree.data);//打印值
//取左边的子节点 不为空 放入队列
if(popTree.left!=null) myQueue.add(popTree.left);
//取右边的子节点 不为空 放入队列
if(popTree.right!=null) myQueue.add(popTree.right);
}
}
这里的myQueue 是最基本的队列，如果你对队列还不清楚实现方式的话，可以看一下我介绍队列的文章。
如果你理解队列只要明白pop出队add入队就行了
节点个数
节点个数就是统计整棵树有几个节点
思路是这样的：我们每一个节点统计自己左边有多少个节点，右边有多少个节点，加起来再加上自己本身也算一个节点，三个数的总和就是当前节点的节点数
// 统计节点个数
public int getNodeNum(MyTree rootTree) {
// 判断是否为空，为空不能算节点，返回0
if (rootTree == null)
return 0;
return 1 + getNodeNum(rootTree.left) + getNodeNum(rootTree.right);
}这里也是一个递归，结束的条件是传入的节点为空，不为空我们就统计左边的节点总数getNodeNum(rootTree.left) 再统计右边的 getNodeNum(rootTree.right); 最后加上自己本身算一个节点就行了。
求二叉树的深度
还是先说一下思路：二叉树的深度的意思就是，我从根节点开始，走到叶子节点为止，所有走法中，经过节点数目最多的那一条路的节点总数就是深度。
如果只有一个根节点深度就是1
那我们可以想，我们让每一个节点问下自己，我左边深还是右边深，每个节点都把自己深的那一侧告诉上面的那个节点，连起来不就是最深的走法啦，不错我们又要用递归了。
// 求二叉树的深度
public int getDepth(MyTree rootTree) {
if (rootTree == null)
return 0;
int leftDepth = getDepth(rootTree.left);// 求左边树的深度
int rightDepth = getDepth(rootTree.right);// 求右边树的深度
// 比较左右树深度 谁深度大就用谁，当然自身还有深度1
return leftDepth > rightDepth ? (leftDepth + 1) : (rightDepth + 1);
}
从根节点开始我们挨个问下去，你这个节点的深度是多少，每个节点再去统计自己左右的深度，最后将值返回给询问深度的那个节点
询问深度的节点会得到左右两个深度，他去最大的深度+1,在告诉问他深度的那个节点。 
大致是这样一个过程，大家将就看，把一个问题分割到每一个节点上，然后递归。