package com.tree.traverse;import java.util.ArrayList;import java.util.List;/** * @author Caijh * * 2017年6月2日 下午7:21:10 */public class BuildTreePreOrderInOrder {  /**    *       1    *       / /   *      3  5    *      /   /   *     7    11   *    /    *   9       */   public static int treeNode = 0;//記錄先序遍歷節點的個數  private List<Node> nodeList = new ArrayList<>();//層次遍歷節點的隊列  public static void main(String[] args) {    BuildTreePreOrderInOrder build = new BuildTreePreOrderInOrder();    int[] preOrder = { 1, 3, 7, 9, 5, 11};    int[] inOrder = { 9, 7, 3, 1, 5, 11};        treeNode = preOrder.length;//初始化二叉樹的節點數    Node root = build.buildTreePreOrderInOrder(preOrder, 0, preOrder.length - 1, inOrder, 0, preOrder.length - 1);    System.out.print("先序遍歷：");    build.preOrder(root);    System.out.print("/n中序遍歷：");    build.inOrder(root);    System.out.print("/n原二叉樹：/n");    build.prototypeTree(root);  }  /**   * 分治法   * 通過先序遍歷結果和中序遍歷結果還原二叉樹   * @param preOrder  先序遍歷結果序列   * @param preOrderBegin   先序遍歷起始位置下標   * @param preOrderEnd  先序遍歷末尾位置下標   * @param inOrder  中序遍歷結果序列   * @param inOrderBegin  中序遍歷起始位置下標   * @param inOrderEnd   中序遍歷末尾位置下標   * @return   */  public Node buildTreePreOrderInOrder(int[] preOrder, int preOrderBegin, int preOrderEnd, int[] inOrder, int inOrderBegin, int inOrderEnd) {    if (preOrderBegin > preOrderEnd || inOrderBegin > inOrderEnd) {      return null;    }    int rootData = preOrder[preOrderBegin];//先序遍歷的第一個字符為當前序列根節點    Node head = new Node(rootData);    int divider = findIndexInArray(inOrder, rootData, inOrderBegin, inOrderEnd);//找打中序遍歷結果集中根節點的位置    int offSet = divider - inOrderBegin - 1;//計算左子樹共有幾個節點，節點數減一，為數組偏移量    Node left = buildTreePreOrderInOrder(preOrder, preOrderBegin + 1, preOrderBegin + 1 + offSet, inOrder, inOrderBegin,inOrderBegin + offSet);    Node right = buildTreePreOrderInOrder(preOrder, preOrderBegin + offSet + 2, preOrderEnd, inOrder, divider + 1, inOrderEnd);    head.left = left;    head.right = right;    return head;  }  /**   * 通過先序遍歷找到的rootData根節點，在中序遍歷結果中區分出：中左子樹和右子樹   * @param inOrder  中序遍歷的結果數組   * @param rootData  根節點位置   * @param begin  中序遍歷結果數組起始位置下標   * @param end  中序遍歷結果數組末尾位置下標   * @return return中序遍歷結果數組中根節點的位置   */  public int findIndexInArray(int[] inOrder, int rootData, int begin, int end) {    for (int i = begin; i <= end; i++) {      if (inOrder[i] == rootData)        return i;    }    return -1;  }  /**   * 二叉樹先序遍歷結果   * @param n   */  public void preOrder(Node n) {    if (n != null) {      System.out.print(n.val + ",");      preOrder(n.left);      preOrder(n.right);    }  }  /**   * 二叉樹中序遍歷結果   * @param n   */  public void inOrder(Node n) {    if (n != null) {      inOrder(n.left);      System.out.print(n.val + ",");      inOrder(n.right);    }  }  /**   * 還原后的二叉樹   * 二叉數層次遍歷   * 基本思想：   *   1.因為推導出來的二叉樹是保存在Node類對象的子對象里面的，（類似于c語言的結構體）如果通過遞歸實現層次遍歷的話，不容易實現   *   2.這里采用List隊列逐層保存Node對象節點的方式實現對二叉樹的層次遍歷輸出   *   3.如果父節點的位置為i,那么子節點的位置為，2i 和 2i+1;依據這個規律逐層遍歷，通過保存的父節點，找到子節點。并保存，不斷向下遍歷保存。   * @param tree   */  public void prototypeTree(Node tree){    //用list存儲層次遍歷的節點    if(tree !=null){      if(tree!=null)        nodeList.add(tree);      nodeList.add(tree.left);      nodeList.add(tree.right);      int count=3;      //從第三層開始      for(int i=3;count<treeNode;i++){        //第i層第一個子節點的父節點的位置下標        int index = (int) Math.pow(2, i-1-1)-1;        /**         * 二叉樹的每一層節點數遍歷         * 因為第i層的最大節點數為2的i-1次方個，         */        for(int j=1;j<=Math.pow(2, i-1);){          //計算有效的節點的個數，和遍歷序列的總數做比較，作為判斷循環結束的標志          if(nodeList.get(index).left!=null)            count++;          if(nodeList.get(index).right!=null)            count++;          nodeList.add(nodeList.get(index).left);          nodeList.add(nodeList.get(index).right);          index++;          if(count>=treeNode)//當所有有效節點都遍歷到了就結束遍歷            break;          j+=2;//每次存儲兩個子節點，所以每次加2        }      }      int flag=0,floor=1;      for(Node node:nodeList){        if(node!=null)          System.out.print(node.val+" ");        else          System.out.print("# ");//#號表示空節點        flag++;        /**         * 逐層遍歷輸出二叉樹         *          */        if(flag>=Math.pow(2, floor-1)){          flag=0;          floor++;          System.out.println();        }      }    }  }  /**   * 內部類   * 1.每個Node類對象為一個節點，   * 2.每個節點包含根節點，左子節點和右子節點   */  class Node {    Node left;    Node right;    int val;    public Node(int val) {      this.val = val;    }  }}