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;//記錄先序遍歷節(jié)點的個數
  private List<Node> nodeList = new ArrayList<>();//層次遍歷節(jié)點的隊列
  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;//初始化二叉樹的節(jié)點數
    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];//先序遍歷的第一個字符為當前序列根節(jié)點
    Node head = new Node(rootData);
    int divider = findIndexInArray(inOrder, rootData, inOrderBegin, inOrderEnd);//找打中序遍歷結果集中根節(jié)點的位置
    int offSet = divider - inOrderBegin - 1;//計算左子樹共有幾個節(jié)點，節(jié)點數減一，為數組偏移量
    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根節(jié)點，在中序遍歷結果中區(qū)分出：中左子樹和右子樹
   * @param inOrder  中序遍歷的結果數組
   * @param rootData  根節(jié)點位置
   * @param begin  中序遍歷結果數組起始位置下標
   * @param end  中序遍歷結果數組末尾位置下標
   * @return return中序遍歷結果數組中根節(jié)點的位置
   */
  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對象節(jié)點的方式實現對二叉樹的層次遍歷輸出
   *   3.如果父節(jié)點的位置為i,那么子節(jié)點的位置為，2i 和 2i+1;依據這個規(guī)律逐層遍歷，通過保存的父節(jié)點，找到子節(jié)點。并保存，不斷向下遍歷保存。
   * @param tree
   */
  public void prototypeTree(Node tree){
    //用list存儲層次遍歷的節(jié)點
    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層第一個子節(jié)點的父節(jié)點的位置下標
        int index = (int) Math.pow(2, i-1-1)-1;
        /**
         * 二叉樹的每一層節(jié)點數遍歷
         * 因為第i層的最大節(jié)點數為2的i-1次方個，
         */
        for(int j=1;j<=Math.pow(2, i-1);){
          //計算有效的節(jié)點的個數，和遍歷序列的總數做比較，作為判斷循環(huán)結束的標志
          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)//當所有有效節(jié)點都遍歷到了就結束遍歷
            break;
          j+=2;//每次存儲兩個子節(jié)點，所以每次加2
        }
      }
      int flag=0,floor=1;
      for(Node node:nodeList){
        if(node!=null)
          System.out.print(node.val+" ");
        else
          System.out.print("# ");//#號表示空節(jié)點
        flag++;
        /**
         * 逐層遍歷輸出二叉樹
         * 
         */
        if(flag>=Math.pow(2, floor-1)){
          flag=0;
          floor++;
          System.out.println();
        }
      }
    }
  }
  /**
   * 內部類
   * 1.每個Node類對象為一個節(jié)點，
   * 2.每個節(jié)點包含根節(jié)點，左子節(jié)點和右子節(jié)點
   */
  class Node {
    Node left;
    Node right;
    int val;
    public Node(int val) {
      this.val = val;
    }
  }
}