一、二叉树的递归遍历

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;
            }
        }
    }

四、二叉树遍历算法的应用

4.1由二叉树先序和中序序列建立二叉树

假如一个二叉树的先序序列为ABCDEFG,中序序列为：CBDAEGF,恢复此二叉树；
1.首先由先序序列找出二叉树的根为A;
2.根据A在中序序列中的位置，把中序序列分为左子树(CBD)和右子树(EGF)的序列；
3.接着通过步骤2可以把先序序列也分为左子树（BCD）和右子树（EFG）;
4.依次类推，直到左右子树全部递归完成；
其递归算法如下：

static void createBitTree(int[] pre,int[] inOrd,int n,BitTree bitTree){
        if (n<=0)bitTree=null;
        else {
            preInOrder(pre,inOrd,0,n-1,0,n-1,bitTree);
        }
    }

static void preInOrder(int[] preOrd, int[] inOrd, int preStart, int preEnd,
 int inStart, int inEnd, BitTree bitTree){
        int m = inStart;
        bitTree.setData(preOrd[preStart]);
        //在中序序列中找到先序序列中根元素的位置
        while (preOrd[preStart] != inOrd[m])m++;
        //说明左子树为null；
        if (m==inStart)bitTree.setLeft(null);
        else {
            bitTree.setLeft(new BitTree());
            preInOrder(preOrd,inOrd,preStart+1,preStart+m-inStart,inStart,m-1,bitTree.getLeft());
        }

        if (m==inEnd)bitTree.setRight(null);
        else {
            bitTree.setRight(new BitTree());
            preInOrder(preOrd,inOrd,preStart+m-inStart+1,preEnd,m+1,inEnd,bitTree.getRight());
        }
    }

·最后说明:二叉树的后序序列和中序序列也可以唯一确定一颗二叉树，因为中序序列可以确定左右子树，后续序列可以确定二叉树；但是前序和后序序列不可以确定一颗二叉树，因为缺少中序序列无法确定左右子树；

4.2二叉树的叶子结点计算

叶子结点就是指左右子树同时为空的节点；

    static int bitTreeLeaf(BitTree bitTree){
        if (bitTree==null)return 0;
        if (bitTree.getLeft()==null && bitTree.getRight()==null)return 1;
        return bitTreeLeaf(bitTree.getLeft())+bitTreeLeaf(bitTree.getRight());
    }

4.3二叉树的深度计算

对于一颗二叉树，如果只有一个节点，左右子树都为空，则深度为1；如果是个空树深度为0；对于其它情况先求出左右子树的深度depthL和depthR,整棵树的深度为1+Max(depthL,depthR);
所以整棵树的深度算法如下：

    static int depthTree(BitTree bitTree){
        if (bitTree==null)return 0;
        if (bitTree.getLeft()==null && bitTree.getRight()==null)return 1;
        int depthL = depthTree(bitTree.getLeft());
        int depthR = depthTree(bitTree.getRight());
        return 1+Math.max(depthL,depthR);
    }

二叉树的基本算法