package myTest;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class myClass {
 
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 myClass tree = new myClass();
 int[] datas = new int[]{1,2,3,4,5,6,7,8,9};
 List<Node> nodelist = new LinkedList<>();
 tree.creatBinaryTree(datas, nodelist);
 Node root = nodelist.get(0);
 System.out.println("遞歸先序遍歷：");
 tree.preOrderTraversal(root);
 System.out.println();
 System.out.println("非遞歸先序遍歷：");
 tree.preOrderTraversalbyLoop(root);
 System.out.println();
 System.out.println("遞歸中序遍歷：");
 tree.inOrderTraversal(root);
 System.out.println();
 System.out.println("非遞歸中序遍歷：");
 tree.inOrderTraversalbyLoop(root);
 System.out.println();
 System.out.println("遞歸后序遍歷：");
 tree.postOrderTraversal(root);
 System.out.println();
 System.out.println("非遞歸后序遍歷：");
 tree.postOrderTraversalbyLoop(root);
 System.out.println();
 System.out.println("廣度優(yōu)先遍歷：");
 tree.bfs(root);
 System.out.println();
 System.out.println("深度優(yōu)先遍歷：");
 List<List<Integer>> rst = new ArrayList<>();
 List<Integer> list = new ArrayList<>();
 tree.dfs(root,rst,list);
 System.out.println(rst);
 }
 /**
 * 
 * @param datas 實現(xiàn)二叉樹各節(jié)點值的數(shù)組
 * @param nodelist 二叉樹list
 */
 private void creatBinaryTree(int[] datas,List<Node> nodelist){
 //將數(shù)組變成node節(jié)點
 for(int nodeindex=0;nodeindex<datas.length;nodeindex++){
  Node node = new Node(datas[nodeindex]);
  nodelist.add(node);
 }
 //給所有父節(jié)點設(shè)定子節(jié)點
 for(int index=0;index<nodelist.size()/2-1;index++){
  //編號為n的節(jié)點他的左子節(jié)點編號為2*n 右子節(jié)點編號為2*n+1 但是因為list從0開始編號，所以還要+1
  //這里父節(jié)點有1（2,3）,2（4,5）,3（6,7）,4（8,9） 但是最后一個父節(jié)點有可能沒有右子節(jié)點 需要單獨處理
  nodelist.get(index).setLeft(nodelist.get(index*2+1)); 
  nodelist.get(index).setRight(nodelist.get(index*2+2));
 }
 //單獨處理最后一個父節(jié)點 因為它有可能沒有右子節(jié)點
 int index = nodelist.size()/2-1;
 nodelist.get(index).setLeft(nodelist.get(index*2+1)); //先設(shè)置左子節(jié)點
 if(nodelist.size() % 2 == 1){ //如果有奇數(shù)個節(jié)點，最后一個父節(jié)點才有右子節(jié)點
  nodelist.get(index).setRight(nodelist.get(index*2+2));
 }
 }
 /**
 * 遍歷當前節(jié)點的值
 * @param nodelist
 * @param node
 */
 public void checkCurrentNode(Node node){
 System.out.print(node.getVar()+" ");
 }
 /**
 * 先序遍歷二叉樹
 * @param root 二叉樹根節(jié)點
 */
 public void preOrderTraversal(Node node){
 if (node == null) //很重要，必須加上 當遇到葉子節(jié)點用來停止向下遍歷
      return; 
 checkCurrentNode(node);
 preOrderTraversal(node.getLeft());
 preOrderTraversal(node.getRight());
 }
 /**
 * 中序遍歷二叉樹
 * @param root 根節(jié)點
 */
 public void inOrderTraversal(Node node){
 if (node == null) //很重要，必須加上
      return; 
 inOrderTraversal(node.getLeft());
 checkCurrentNode(node);
 inOrderTraversal(node.getRight());
 }
 /**
 * 后序遍歷二叉樹
 * @param root 根節(jié)點
 */
 public void postOrderTraversal(Node node){
 if (node == null) //很重要，必須加上
      return; 
 postOrderTraversal(node.getLeft());
 postOrderTraversal(node.getRight());
 checkCurrentNode(node);
 }
 
 /**
 * 非遞歸前序遍歷
 * @param node
 */
 public void preOrderTraversalbyLoop(Node node){
 Stack<Node> stack = new Stack();
 Node p = node;
 while(p!=null || !stack.isEmpty()){
  while(p!=null){ //當p不為空時，就讀取p的值，并不斷更新p為其左子節(jié)點，即不斷讀取左子節(jié)點
  checkCurrentNode(p);
  stack.push(p); //將p入棧
  p = p.getLeft();
  }
  if(!stack.isEmpty()){
  p = stack.pop();
  p = p.getRight();
  }
 }
 }
 /**
 * 非遞歸中序遍歷
 * @param node
 */
 public void inOrderTraversalbyLoop(Node node){
 Stack<Node> stack = new Stack();
 Node p = node;
 while(p!=null || !stack.isEmpty()){
  while(p!=null){
  stack.push(p);
  p = p.getLeft();
  }
  if(!stack.isEmpty()){ 
  p = stack.pop();
  checkCurrentNode(p);
  p = p.getRight();
  }
 }
 }
 /**
 * 非遞歸后序遍歷
 * @param node
 */
 public void postOrderTraversalbyLoop(Node node){
 Stack<Node> stack = new Stack<>();
 Node p = node,prev = node;
 while(p!=null || !stack.isEmpty()){
  while(p!=null){
  stack.push(p);
  p = p.getLeft();
  }
  if(!stack.isEmpty()){
  Node temp = stack.peek().getRight();
  if(temp == null||temp == prev){
   p = stack.pop();
   checkCurrentNode(p);
   prev = p;
   p = null;
  }else{
   p = temp;
  } 
  }
 }
 }
 
 /**
 * 廣度優(yōu)先遍歷（從上到下遍歷二叉樹）
 * @param root
 */
 public void bfs(Node root){
  if(root == null) return;
  LinkedList<Node> queue = new LinkedList<Node>();
  queue.offer(root); //首先將根節(jié)點存入隊列
  //當隊列里有值時，每次取出隊首的node打印，打印之后判斷node是否有子節(jié)點，若有，則將子節(jié)點加入隊列
  while(queue.size() > 0){ 
  Node node = queue.peek();
   queue.poll(); //取出隊首元素并打印
   System.out.print(node.var+" ");
   if(node.left != null){ //如果有左子節(jié)點，則將其存入隊列
    queue.offer(node.left);
   }
   if(node.right != null){ //如果有右子節(jié)點，則將其存入隊列
    queue.offer(node.right);
   }
  }
 }
 /**
 * 深度優(yōu)先遍歷
 * @param node
 * @param rst
 * @param list
 */
 public void dfs(Node node,List<List<Integer>> rst,List<Integer> list){
 if(node == null) return;
 if(node.left == null && node.right == null){
  list.add(node.var);
  /* 這里將list存入rst中時，不能直接將list存入，而是通過新建一個list來實現(xiàn)，
  * 因為如果直接用list的話，后面remove的時候也會將其最后一個存的節(jié)點刪掉*/
  rst.add(new ArrayList<>(list));
  list.remove(list.size()-1);
 }
 list.add(node.var);
 dfs(node.left,rst,list);
 dfs(node.right,rst,list);
 list.remove(list.size()-1);
 }
 /**
 * 節(jié)點類
 * var 節(jié)點值
 * left 節(jié)點左子節(jié)點
 * right 右子節(jié)點
 */ 
 class Node{
 int var;
 Node left;
 Node right;
 public Node(int var){
  this.var = var;
  this.left = null;
  this.right = null;
 }
 public void setLeft(Node left) {
  this.left = left;
 }
 public void setRight(Node right) {
  this.right = right;
 }
 public int getVar() {
  return var;
 }
 public void setVar(int var) {
  this.var = var;
 }
 public Node getLeft() {
  return left;
 }
 public Node getRight() {
  return right;
 }
 
 }

}