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é)點(diǎn)的個(gè)數(shù)
  private List<Node> nodeList = new ArrayList<>();//層次遍歷節(jié)點(diǎn)的隊(duì)列
  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é)點(diǎn)數(shù)
    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);
  }

  /**
   * 分治法
   * 通過先序遍歷結(jié)果和中序遍歷結(jié)果還原二叉樹
   * @param preOrder  先序遍歷結(jié)果序列
   * @param preOrderBegin   先序遍歷起始位置下標(biāo)
   * @param preOrderEnd  先序遍歷末尾位置下標(biāo)
   * @param inOrder  中序遍歷結(jié)果序列
   * @param inOrderBegin  中序遍歷起始位置下標(biāo)
   * @param inOrderEnd   中序遍歷末尾位置下標(biāo)
   * @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];//先序遍歷的第一個(gè)字符為當(dāng)前序列根節(jié)點(diǎn)
    Node head = new Node(rootData);
    int divider = findIndexInArray(inOrder, rootData, inOrderBegin, inOrderEnd);//找打中序遍歷結(jié)果集中根節(jié)點(diǎn)的位置
    int offSet = divider - inOrderBegin - 1;//計(jì)算左子樹共有幾個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)減一，為數(shù)組偏移量
    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é)點(diǎn)，在中序遍歷結(jié)果中區(qū)分出：中左子樹和右子樹
   * @param inOrder  中序遍歷的結(jié)果數(shù)組
   * @param rootData  根節(jié)點(diǎn)位置
   * @param begin  中序遍歷結(jié)果數(shù)組起始位置下標(biāo)
   * @param end  中序遍歷結(jié)果數(shù)組末尾位置下標(biāo)
   * @return return中序遍歷結(jié)果數(shù)組中根節(jié)點(diǎn)的位置
   */
  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;
  }
  /**
   * 二叉樹先序遍歷結(jié)果
   * @param n
   */
  public void preOrder(Node n) {
    if (n != null) {
      System.out.print(n.val + ",");
      preOrder(n.left);
      preOrder(n.right);
    }
  }
  /**
   * 二叉樹中序遍歷結(jié)果
   * @param n
   */
  public void inOrder(Node n) {
    if (n != null) {
      inOrder(n.left);
      System.out.print(n.val + ",");
      inOrder(n.right);
    }
  }
  /**
   * 還原后的二叉樹
   * 二叉數(shù)層次遍歷
   * 基本思想：
   *   1.因?yàn)橥茖?dǎo)出來的二叉樹是保存在Node類對象的子對象里面的，（類似于c語言的結(jié)構(gòu)體）如果通過遞歸實(shí)現(xiàn)層次遍歷的話，不容易實(shí)現(xiàn)
   *   2.這里采用List隊(duì)列逐層保存Node對象節(jié)點(diǎn)的方式實(shí)現(xiàn)對二叉樹的層次遍歷輸出
   *   3.如果父節(jié)點(diǎn)的位置為i,那么子節(jié)點(diǎn)的位置為，2i 和 2i+1;依據(jù)這個(gè)規(guī)律逐層遍歷，通過保存的父節(jié)點(diǎn)，找到子節(jié)點(diǎn)。并保存，不斷向下遍歷保存。
   * @param tree
   */
  public void prototypeTree(Node tree){
    //用list存儲層次遍歷的節(jié)點(diǎn)
    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層第一個(gè)子節(jié)點(diǎn)的父節(jié)點(diǎn)的位置下標(biāo)
        int index = (int) Math.pow(2, i-1-1)-1;
        /**
         * 二叉樹的每一層節(jié)點(diǎn)數(shù)遍歷
         * 因?yàn)榈趇層的最大節(jié)點(diǎn)數(shù)為2的i-1次方個(gè)，
         */
        for(int j=1;j<=Math.pow(2, i-1);){
          //計(jì)算有效的節(jié)點(diǎn)的個(gè)數(shù)，和遍歷序列的總數(shù)做比較，作為判斷循環(huán)結(jié)束的標(biāo)志
          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)//當(dāng)所有有效節(jié)點(diǎn)都遍歷到了就結(jié)束遍歷
            break;
          j+=2;//每次存儲兩個(gè)子節(jié)點(diǎn)，所以每次加2
        }
      }
      int flag=0,floor=1;
      for(Node node:nodeList){
        if(node!=null)
          System.out.print(node.val+" ");
        else
          System.out.print("# ");//#號表示空節(jié)點(diǎn)
        flag++;
        /**
         * 逐層遍歷輸出二叉樹
         * 
         */
        if(flag>=Math.pow(2, floor-1)){
          flag=0;
          floor++;
          System.out.println();
        }
      }
    }
  }
  /**
   * 內(nèi)部類
   * 1.每個(gè)Node類對象為一個(gè)節(jié)點(diǎn)，
   * 2.每個(gè)節(jié)點(diǎn)包含根節(jié)點(diǎn)，左子節(jié)點(diǎn)和右子節(jié)點(diǎn)
   */
  class Node {
    Node left;
    Node right;
    int val;
    public Node(int val) {
      this.val = val;
    }
  }
}