java implements the creation of binary tree and five traversal methods of summary

Using java array to create 2 cross trees and recursive first traversal, recursive in order traversal, recursive after traversal, non-recursive before traversal, non-recursive in order traversal, non-recursive after traversal, depth first traversal, breadth first traversal:

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(" Recursive traversal first: ");
 tree.preOrderTraversal(root);
 System.out.println();
 System.out.println(" Non-recursive sequential traversal: ");
 tree.preOrderTraversalbyLoop(root);
 System.out.println();
 System.out.println(" Sequential traversal in recursion: ");
 tree.inOrderTraversal(root);
 System.out.println();
 System.out.println(" Sequential traversal in non-recursive: ");
 tree.inOrderTraversalbyLoop(root);
 System.out.println();
 System.out.println(" Recursive sequential traversal: ");
 tree.postOrderTraversal(root);
 System.out.println();
 System.out.println(" Non-recursive post-traversal: ");
 tree.postOrderTraversalbyLoop(root);
 System.out.println();
 System.out.println(" Breadth first traversal: ");
 tree.bfs(root);
 System.out.println();
 System.out.println(" Depth-first traversal: ");
 List<List<Integer>> rst = new ArrayList<>();
 List<Integer> list = new ArrayList<>();
 tree.dfs(root,rst,list);
 System.out.println(rst);
 }
 /**
 * 
 * @param datas  implementation 2 An array of the values of each node in the cross-tree 
 * @param nodelist 2 tree list
 */
 private void creatBinaryTree(int[] datas,List<Node> nodelist){
 // Change the array to node node 
 for(int nodeindex=0;nodeindex<datas.length;nodeindex++){
  Node node = new Node(datas[nodeindex]);
  nodelist.add(node);
 }
 // Assign child nodes to all parent nodes 
 for(int index=0;index<nodelist.size()/2-1;index++){
  // Numbers for n Its left child node is numbered 2*n  The right child node number is 2*n+1  But because list from 0 I'm going to start numbering, so I'm going to have to +1
  // Here the parent node has 1 ( 2,3 ) ,2 ( 4,5 ) ,3 ( 6,7 ) ,4 ( 8,9 )   But in the end 1 It is possible for a parent node to have no right children   It needs to be dealt with separately 
  nodelist.get(index).setLeft(nodelist.get(index*2+1)); 
  nodelist.get(index).setRight(nodelist.get(index*2+2));
 }
 // Separate processing end 1 A parent node   Because it might not have a right child 
 int index = nodelist.size()/2-1;
 nodelist.get(index).setLeft(nodelist.get(index*2+1)); // First set the left child node 
 if(nodelist.size() % 2 == 1){ // If you have an odd number of nodes, finally 1 A right child is a right child 
  nodelist.get(index).setRight(nodelist.get(index*2+2));
 }
 }
 /**
 *  Iterate over the value of the current node 
 * @param nodelist
 * @param node
 */
 public void checkCurrentNode(Node node){
 System.out.print(node.getVar()+" ");
 }
 /**
 *  The first sequence traversal 2 tree 
 * @param root 2 Fork root node 
 */
 public void preOrderTraversal(Node node){
 if (node == null) // Very important, must be added   Use to stop the downward traversal when a leaf node is encountered 
      return; 
 checkCurrentNode(node);
 preOrderTraversal(node.getLeft());
 preOrderTraversal(node.getRight());
 }
 /**
 *  In the sequence traversal 2 tree 
 * @param root  The root node 
 */
 public void inOrderTraversal(Node node){
 if (node == null) // Very important, must be added 
      return; 
 inOrderTraversal(node.getLeft());
 checkCurrentNode(node);
 inOrderTraversal(node.getRight());
 }
 /**
 *  After the sequence traversal 2 tree 
 * @param root  The root node 
 */
 public void postOrderTraversal(Node node){
 if (node == null) // Very important, must be added 
      return; 
 postOrderTraversal(node.getLeft());
 postOrderTraversal(node.getRight());
 checkCurrentNode(node);
 }
 
 /**
 *  Non-recursive preorder traversal 
 * @param node
 */
 public void preOrderTraversalbyLoop(Node node){
 Stack<Node> stack = new Stack();
 Node p = node;
 while(p!=null || !stack.isEmpty()){
  while(p!=null){ // when p When not empty, read p , and constantly updated p Is its left child node, that is, it continuously reads the left child node 
  checkCurrentNode(p);
  stack.push(p); // will p Into the stack 
  p = p.getLeft();
  }
  if(!stack.isEmpty()){
  p = stack.pop();
  p = p.getRight();
  }
 }
 }
 /**
 *  Order traversal in non-recursion 
 * @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();
  }
 }
 }
 /**
 *  Non-recursive post-traversal 
 * @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;
  } 
  }
 }
 }
 
 /**
 *  Breadth first traversal (top to bottom traversal 2 Fork tree) 
 * @param root
 */
 public void bfs(Node root){
  if(root == null) return;
  LinkedList<Node> queue = new LinkedList<Node>();
  queue.offer(root); // The root node is first queued 
  // When there is a value in the queue, take the first of the queue each time node Print, print and determine node Whether there are children, and if so, the children are queued 
  while(queue.size() > 0){ 
  Node node = queue.peek();
   queue.poll(); // Take out the header element and print 
   System.out.print(node.var+" ");
   if(node.left != null){ // If there is a left child node, it is queued 
    queue.offer(node.left);
   }
   if(node.right != null){ // If there is a right child node, it is queued 
    queue.offer(node.right);
   }
  }
 }
 /**
 *  Depth-first traversal 
 * @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);
  /*  There will be list deposit rst When, you can't just put list I'm going to put it in, but I'm going to create it 1 a list To do this, 
  *  Because if I use it directly list In the back remove "Will also put it last 1 Delete the saved nodes */
  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);
 }
 /**
 *  Node class 
 * var  Node values 
 * left  The left child of the node 
 * right  The right child node 
 */ 
 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;
 }
 
 }

}

Operation results:

Recursive traversal first:
1 2 4 8 9 5 3 6 7

Non-recursive sequential traversal:
1 2 4 8 9 5 3 6 7

Sequential traversal in recursion:
8 4 9 2 5 1 6 3 7

Sequential traversal in non-recursive:
8 4 9 2 5 1 6 3 7

Recursive sequential traversal:
8 9 4 5 2 6 7 3 1

Non-recursive post-traversal:
8 9 4 5 2 6 7 3 1

Breadth first traversal:
1 2 3 4 5 6 7 8 9

Depth-first traversal:
[[1, 2, 4, 8], [1, 2, 4, 9], [1, 2, 5], [1, 3, 6], [1, 3, 7]]