一、二叉树的递归遍历

1.先序遍历
    static class BitTree {
        int data;
        BitTree left;
        BitTree right;
    }
    static void visit(BitTree bitTree) {
     //访问节点
    }
  //使用递归方法遍历二叉树
    static void preOrder(BitTree bitTree) {
        if (bitTree != null) {
            visit(bitTree);
            preOrder(bitTree.left);
            preOrder(bitTree.right);
        }
    }
2.中序遍历
  static void midOrder(BitTree bitTree) {
        if (bitTree != null) {
            midOrder(bitTree.left);
            visit(bitTree);
            midOrder(bitTree.right);
        }
    }
3.后序遍历
    static void postOrder(BitTree bitTree) {
        if (bitTree != null) {
            postOrder(bitTree.left);
            postOrder(bitTree.right);
            visit(bitTree);
        }
    }

二、二叉树的层次遍历

二叉树的层次遍历是指二叉树从上到下，从左到右遍历数据。同一层中的节点访问完了，接着访问下一层级的元素。先遇到的节点先访问，后遇到的节点后访问，访问顺利类似队列。所以针对每一个节点的访问顺序是
1.先访问 当前节点的数据；
2.如果当前节点有左孩子，左孩子入队；
3.如果当前节点有右孩子，右孩子入队；

      static void levelOrder(BitTree bitTree){
        //这里的数组长度是情况而定，写Int最大值是随意的。
        BitTree[] queue = new BitTree[Integer.MAX_VALUE];
        int font,rear;
        if (bitTree==null)return;
        font = -1;
        rear=0;
        //根节点入队
        queue[rear] = bitTree;
        while (font!=rear){
            font++;
            //访问出队节点
            visit(queue[font]);
            //出队节点的左孩子不为null就把左孩子入队
            if (queue[font].left!=null){
                rear++;
                queue[rear] = queue[font].left;
            }
            //出队节点的右孩子不为null就把右孩子入队
            if (queue[font].right!=null){
                rear++;
                queue[rear] = queue[font].right;
            }
        }
    }

三、二叉树的非递归遍历

中序遍历的非递归算法：访问节点时先访问其左孩子，再访问该节点，最后访问右孩子。
中序遍历的时候我们先从根节点的左孩子开始，一直深入孩子节点的左孩子，直到节点的左孩子为空返回，访问该节点。

    //中序遍历的非递归算法
    static void nrInOrder(BitTree bitTree){
        //加入100的长度够用
        int maxLength =100;
        BitTree[] bitTrees = new BitTree[maxLength];
        BitTree p = bitTree;
        int top = -1;
        //根节点为null，直接return;
        if (bitTree==null)return;
        while (!(top==0 && p==null)){
            while (p!=null){
                if (top < maxLength-1)bitTrees[++top]=p;
                p = p.left;
            }
            if (top==-1)return;
            else {
                p = bitTrees[top--];
                visit(p);
                p = p.right;
            }
        }
    }