根据先序遍历和中序遍历建立二叉树

算法思想

先序遍历的顺序是根左右，中序遍历的顺序是左根右。根据这一特性，先序遍历的第一个元素确定是根节点。因此咱们只要在中序遍历中找到该根节点的值，根节点以左就是它的左子树，根节点以右就是它的右子树，而后就能够递归的方式建立二叉树web

假设如今有一颗二叉树以下

先序序列为（18，14，7，3，11，22，35，27）
中序序列为（3，7，11，14，18，22，27，35）
首先根据先序序列得二叉树的根节点是18，而后根据给定的先序序列能够得知18的左子树的中序序列为（3，7，11，14，），18的右子树的中序序列为（22，37，35），18的左子树的先序序列为（14，7，3，11），18的右子树的先序序列为（22，35，37），进而对18的左右子树分别类推动行处理，即可以肯定整颗二叉树。算法

public static TreeNode createByPreAndIn(Object[] pre,Object[] in,int preStart,int preEnd,int inStart,int inEnd){
        TreeNode root=null;
        if(pre==null||in==null||pre.length==0||in.length==0||pre.length!=in.length||preStart>preEnd||inStart>inEnd)
            return null;
        root=new TreeNode(pre[preStart]);
        int j=0;
        for(j=inStart;j<=inEnd;j++){
            if(pre[preStart]==in[j]){
                root.leftChild=createByPreAndIn(pre, in, preStart+1, preStart+j-inStart, inStart, j);
                root.rightChild=createByPreAndIn(pre, in, preStart+j-inStart+1, preEnd, j+1, inEnd);
            }
        }
        return root;
}

输出

public static void main(String[] args) {
        Object[] pre={18,14,7,3,11,22,35,27};
        Object[] in={3,7,11,14,18,22,27,35};
        TreeNode root=createByPreAndIn(pre, in, 0, pre.length-1, 0, in.length-1);
        System.out.print("先序序列为：");
        preOrder(root);
        System.out.println();
        System.out.print("中序序列为：");
        inOrder(root);
        System.out.println();
        System.out.print("后序序列为：");
        postOrder(root);
        System.out.println();
        System.out.print("层次遍历为：");
        levelOrder(root);
    }

二叉树遍历的过程能够参考二叉树的建立，递归遍历以及非递归遍历svg