import java.util.Queue;
import java.util.Stack;

/**
 * @ClassName tree
 * @Description
 *  * 遍歷二叉樹
 *  * 分別以遞歸和非遞歸實現(xiàn)前序惕澎、中序蚀之、后序遍歷二叉樹靴跛、與層級遍歷
 * @Version V1.0
 **/
public class tree {

  //遞歸
  //前序遍歷

  public void preOrder(Node node){
    if(node==null){
      return;
    }
    System.out.println("前序"+node.getValue());
    preOrder(node.getLeft());
    preOrder(node.getRight());
  }
  //中序遍歷
  public void inOrder(Node node){
    if(node == null){
      return;
    }
    inOrder(node.getLeft());
    System.out.println("中序"+node.getValue());
    inOrder(node.getRight());
  }
  //后序遍歷
 public void postOrder(Node node){
    if(node == null){
       return;
    }
    postOrder(node.getLeft());
    postOrder(node.getRight());
    System.out.println("后序"+node.getValue());
 }
  //非遞歸
  //前序遍歷-- 使用棧
  public void preOrderTraversal(Node node){
    if(node == null){
      return;
    }
    Stack<Node>  nodeStack  =  new Stack<>();
    nodeStack.push(node);
    while (!nodeStack.isEmpty()){
      Node cur_node = nodeStack.lastElement();
      nodeStack.pop();
      if(!nodeStack.isEmpty() && nodeStack.lastElement()==null){
        nodeStack.pop();
        System.out.println("前序"+cur_node.getValue());
        continue;
      }
      if(cur_node.getRight()!=null){
         nodeStack.push(cur_node.getRight());
      }
      if(cur_node.getLeft()!=null){
        nodeStack.push(cur_node.getLeft());
      }
      //前序 nullptr 標(biāo)記當(dāng)前節(jié)點的左右子樹已經(jīng)遍歷
      nodeStack.push(null);
      nodeStack.push(cur_node);
    }
  }
  //中序遍歷
  public void inOrderTraversal(Node node){
    if(node == null){
      return;
    }
    Stack<Node>  nodeStack  =  new Stack<>();
    nodeStack.push(node);
    while (!nodeStack.isEmpty()){
      Node cur_node = nodeStack.lastElement();
      nodeStack.pop();
      if(!nodeStack.isEmpty() && nodeStack.lastElement()==null){
        nodeStack.pop();
        System.out.println("中序"+cur_node.getValue());
        continue;
      }
      if(cur_node.getRight()!=null){
        nodeStack.push(cur_node.getRight());
      }
      //中序 nullptr 標(biāo)記當(dāng)前節(jié)點的左右子樹已經(jīng)遍歷
      nodeStack.push(null);
      nodeStack.push(cur_node);
      if(cur_node.getLeft()!=null){
        nodeStack.push(cur_node.getLeft());
      }

    }
  }
  //后序遍歷
  public void postOrderTraversal(Node node){
    if(node == null){
      return;
    }
    Stack<Node>  nodeStack  =  new Stack<>();
    nodeStack.push(node);
    while (!nodeStack.isEmpty()){
      Node cur_node = nodeStack.lastElement();
      nodeStack.pop();
      if(!nodeStack.isEmpty() && nodeStack.lastElement()==null){
        nodeStack.pop();
        System.out.println("后序"+cur_node.getValue());
        continue;
      }
      //后序 nullptr 標(biāo)記當(dāng)前節(jié)點的左右子樹已經(jīng)遍歷
      nodeStack.push(null);
      nodeStack.push(cur_node);
      if(cur_node.getRight()!=null){
        nodeStack.push(cur_node.getRight());
      }

      if(cur_node.getLeft()!=null){
        nodeStack.push(cur_node.getLeft());
      }

    }
  }

  //層級遍歷
    //實現(xiàn)過程
    //1、首先將二叉樹的根節(jié)點push到隊列中糟趾，判斷隊列不為NULL，就輸出隊頭的元素黎烈，
    //2唠粥、判斷節(jié)點如果有孩子，就將孩子push到隊列中蛉艾，
    //3钳踊、遍歷過的節(jié)點出隊列，
    //4勿侯、循環(huán)以上操作拓瞪，直到Tree == NULL。
  public void levelOrder(Node node){
    if(node ==null){
      return;
    }
    Queue<Node> queue = null;
    if(node!=null){
      queue.add(node);
    }
    while (!queue.isEmpty()){
      System.out.println(queue.peek().getValue());
      if(queue.peek().getLeft()!=null){
         queue.add(queue.peek().getLeft());
      }
      if(queue.peek().getRight()!=null){
        queue.add(queue.peek().getRight());
      }
      queue.poll();
    }
  }
}
class Node {

  private  int value;
  private  Node left;
  private  Node right;

  public Node(int value){
    this.value=value;
    this.left=null;
    this.right=null;
  }

  public int getValue() {
    return value;
  }

  public void setValue(int value) {
    this.value = value;
  }

  public Node getLeft() {
    return left;
  }

  public void setLeft(Node left) {
    this.left = left;
  }

  public Node getRight() {
    return right;
  }

  public void setRight(Node right) {
    this.right = right;
  }

}