题记------学习别人的精髓，并加以总结，消化吸收，这就是提高！！！
一、二叉树的创建
部分思路参考自http://ocaicai.iteye.com/blog/1047397
1 package com.gongli.binary;
2
3 import java.util.ArrayList;
4 import java.util.List;
5
6 import org.junit.Test;
7
8
9 /**
10 * 创建二叉树，要注意以下几点
11 * 1、将数组转化为节点，最后一个父节点arr.length/2-1,由右边的子节点是否存在并不确定，需要单独处理
12 * 2、左孩子节点的索引parentIndex*2+1,右孩子节点的索引parentIndex*2+2
13 * @author Administrator
14 */
15 public class CreateBinary {
16 private int[] arr = {1,2,3,4,5,6,7,8,9};
17 private List<Node> nodeList = null;
18 class Node{
19 Node leftChild;
20 Node rightChild;
21 int data;
22 Node(int newData){
23 leftChild = null;
24 rightChild = null;
25 this.data = newData;
26 }
27 }
28 //生成二叉树
29 public List<Node> createBinary(){
30 nodeList = new ArrayList<Node>();
31 //将数组转化为节点
32 for(int i=0;i<arr.length;i++){
33 nodeList.add(new Node(arr[i]));
34 }
35 //对最后一个父节点前的节点按父子节点间的关系建立二叉树
36 for(int parentIndex = 0;parentIndex<arr.length/2-1;parentIndex++){
37 nodeList.get(parentIndex).leftChild = nodeList.get(parentIndex*2+1);
38 nodeList.get(parentIndex).rightChild = nodeList.get(parentIndex*2+2);
39 }
40 int lastIndex = arr.length/2-1;//最后一个父节点
41 //左孩子
42 nodeList.get(lastIndex).leftChild = nodeList.get(lastIndex*2+1);
43 if(arr.length%2==1){//存在右孩子
44 nodeList.get(lastIndex).rightChild = nodeList.get(lastIndex*2+2);
45 }
46 return nodeList;
47 }
48
49 }
二、先序、中序、后序三种遍历方式的实现（采用递归和迭代）
1、先序遍历
1 /**
2 * 递归实现先序遍历，即根左右
3 */
4 public void beforeTraversal(Node node){
5 if(node==null){
6 return;
7 }
8 System.out.print(node.data+" ");
9 beforeTraversal(node.leftChild);
10 beforeTraversal(node.rightChild);
11 }
12
13 /**
14 * 迭代实现先序遍历，即根左右，用栈作为辅助容器，顺便复习下栈，切记栈的先进后出原则
* 该方法思路，结构简单，但不具备扩展性15 */
16 public void beforeTraversalStack(Node node){
17 if(node==null) return;//如果节点为null则直接结束程序
18 Stack<Node> stack = new Stack<Node>();
19 stack.push(node);//节点入栈
20 //出栈顶元素，与左右孩子入栈，记住右孩子先入栈，才能保证左孩子先出栈
21 while(!stack.isEmpty()){
22 Node root = stack.pop();
23 System.out.print(root.data+" ");
24 if(root.rightChild!=null){
25 stack.push(root.rightChild);
26 }
27 if(root.leftChild!=null){
28 stack.push(root.leftChild);
29 }
30 }
31 }
2、中序遍历
1 /**
2 * 递归实现中序遍历，即左根右
3 */
4 public void middleTraversal(Node node){
5 if(node==null){
6 return;
7 }
8 middleTraversal(node.leftChild);
9 System.out.print(node.data+" ");
10 middleTraversal(node.rightChild);
11 }
12
13 /**
14 * 迭代实现中序遍历，即左根右,该方法实质是用栈模拟递归过程
15 */
16 public void middleTraversalStack(Node node){
17 if(node==null) return;//如果节点为null则直接结束程序
18 Stack<Node> stack = new Stack<Node>();
19 while(node!=null||!stack.isEmpty()){
20 while(node!=null){
21 stack.push(node);//将根节点入栈
22 node = node.leftChild;//递归让所有左节点先入栈
23 }
24 node = stack.pop();//左节点入栈完毕后出栈
25 System.out.print(node.data+" ");
26 node = node.rightChild;//处理右节点
27 }
28 }
3、后序遍历
1 /**
2 * 递归实现后序遍历，即左右根
3 */
4 public void afterTraversal(Node node){
5 if(node==null){
6 return;
7 }
8 afterTraversal(node.leftChild);
9 afterTraversal(node.rightChild);
10 System.out.print(node.data+" ");
11 }
12
13 /**
14 * 迭代实现后序遍历，即左右根,该方法实质是用栈模拟递归过程
15 */
16 public void afterTraversalStack(Node node){
17 if(node==null) return;//如果节点为null则直接结束程序
18 Stack<Node> input = new Stack<Node>();//用于封装node和他的左右孩子
19 Stack<Node> output = new Stack<Node>();//用于封装栈input翻转后的结果
20 input.push(node);//根节点入栈
21 while(!input.isEmpty()){
22 node = input.pop();//input栈出栈
23 output.push(node);//翻转后入栈
24 if(node.leftChild != null){
25 input.push(node.leftChild);
26 }
27 if(node.rightChild != null){
28 input.push(node.rightChild);
29 }
30 }
31 //循环输出output栈中的节点，即为后序遍历
32 while(!output.isEmpty()){
33 System.out.print(output.pop().data+" ");
34 }
35 }
三、二叉树节点个数（采用递归和迭代，迭代分别采用栈和队列作为辅助容器）
1 /**
2 * 求二叉树节点个数，使用递归，较简单
3 * 二叉树节点个数=左节点+右节点+根节点
4 */
5 public int getNodeNumber(Node node){
6 if(node == null){
7 return 0;
8 }
9 return getNodeNumber(node.leftChild)+getNodeNumber(node.rightChild)+1;
10 }
11
12 /**
13 * 求二叉树节点个数，使用迭代
14 * 用队列作为辅助容器
15 */
16 public int getNodeNumberQueue(Node node){
17 if(node==null)return 0;
18 Queue<Node> queue = new LinkedList<Node>();
19 queue.offer(node);
20 int count = 1;//初始化时先把根节点算上
21 while(!queue.isEmpty()){
22 node = queue.poll();//出队
23 if(node.leftChild!=null){
24 queue.offer(node.leftChild);//左节点入队，重新开始迭代的过程直到全部出队
25 count++;
26 }
27 if(node.rightChild!=null){
28 queue.offer(node.rightChild);
29 count++;
30 }
31 }
32 return count;
33 }
34
35 /**
36 * 求二叉树节点个数，使用迭代
37 * 用栈作为辅助容器
38 */
39 public int getNodeNumberStack(Node node){
40 if(node==null)return 0;
41 Stack<Node> stack = new Stack<Node>();
42 stack.push(node);
43 int count = 1;//初始化时先把根节点算上
44 while(!stack.isEmpty()){
45 node = stack.pop();//出栈
46 if(node.leftChild!=null){
47 stack.push(node.leftChild);//左节点入栈，重新开始迭代的过程直到节点全部出栈
48 count++;
49 }
50 if(node.rightChild!=null){
51 stack.push(node.rightChild);
52 count++;
53 }
54 }
55 return count;
56 }
四、二叉树的深度
1 /**
2 * 二叉树的深度，使用递归实现
3 * 二叉树的深度=max(leftDepth,rightDepth)+1,加1是因为要算上根节点的深度
4 */
5 public int getDepth(Node node){
6 if(node==null){return 0;}
7 int leftDepth = getDepth(node.leftChild);
8 int rightDepth = getDepth(node.rightChild);
9 return Math.max(leftDepth, rightDepth)+1;
10 }
五、二叉树的分层遍历
/**
* 二叉树的分层遍历(从上到下，从左到右)，采用迭代实现,递归还没想到
* 把辅助容器换成栈，则是先序遍历
*/
public void levelTraversal(Node node){
if(node==null)return;
Queue<Node> queue = new LinkedList<Node>();
queue.offer(node);
while(!queue.isEmpty()){
node = queue.poll();
System.out.print(node.data+" ");
if(node.leftChild!=null){
queue.offer(node.leftChild);
}
if(node.rightChild!=null){
queue.offer(node.rightChild);
}
}
}
六、二叉树第k层节点的个数
1 /**
2 * 求二叉树第k层节点的个数，采用递归
3 */
4 public int getNodes(Node node,int k){
5 if(node==null||k<1)return 0;
6 if(k==1)return 1;
7 int left = getNodes(node.leftChild,k-1);//左树k-1层的节点数
8 int right = getNodes(node.rightChild,k-1);//右树k-1层的节点数
9 return left+right;
10 }
七、判断是否为平衡二叉树
1 /**
2 * 判断二叉树是否为平衡二叉树
3 * 平衡二叉树条件必须满足两点
4 * 1、左右树的高度差不能超过一
5 * 2、必须是二叉树
6 */
7 public boolean isAVLTree(Node node){
8 if(node==null)return true;
9 if(Math.abs(getDepth(node.leftChild)-getDepth(node.rightChild))>1){return false;}//getDeth()为上面写过的树的深度
10 return isAVLTree(node.leftChild)&&isAVLTree(node.rightChild);
11 }