1.     // 递归版本前序遍历
    2.     public static void preOrder1(Node root){
    3.         if(root == null){
    4.             return ;
    5.         }
    6.         System.out.print( root.value+" ");
    7.         preOrder1(root.left);
    8.         preOrder1(root.right);
    9.     }
    11.     // 非递归版本前序遍历    头左右
    12.     // 1)把头节点压入栈中，从栈中弹出一个节点cur
    13.     // 2)打印cur
    14.     // 3)先右再左入栈（如果有的话）
    15.     // 4)重复操作
    16.     public static void preOrder2(Node head){
    17.         if(head == null){
    18.             return;
    19.         }
    20.         Stack<Node> stack = new Stack<>();
    21.         stack.add(head);
    22.         while(!stack.isEmpty()){
    24.             Node pop = stack.pop();
    25.             System.out.print(pop.value + " ");
    27.             if(pop.right != null){
    28.                 stack.push(pop.right);
    29.             }
    31.             if(pop.left != null){
    32.                 stack.push(pop.left);
    33.             }
    34.         }
    35.     }
    36.     // 归版本后序遍历     左右头
    37.     public static void laterOrder1(Node head){
    38.         if(head == null){
    39.             return;
    40.         }
    41.         laterOrder1(head.left);
    42.         laterOrder1(head.right);
    43.         System.out.print(head.value+" ");
    44.     }
    46.     // 非递归版本后序遍历     左右头
    47.     // 1)把头节点压入栈中，从栈中弹出一个节点cur，
    48.     // 2)把cur放入收集栈中
    49.     // 3)先左再右入栈（如果有的话）
    50.     // 4)重复操作 收集完打印    
    51.     // 头左右→头右左→左右头
    52.     public static void laterOrder2(Node head){
    53.         if(head == null){
    54.             return;
    55.         }
    56.         Stack<Node> stack1 = new Stack<>();
    57.         Stack<Node> stack2 = new Stack<>();
    59.         stack1.push(head);
    60.         while(!stack1.isEmpty()){
    61.             Node pop = stack1.pop();
    62.             stack2.push(pop);
    63.             if(pop.left != null){
    64.                 stack1.push(pop.left);
    65.             }
    67.             if(pop.right != null){
    68.                 stack1.push(pop.right);
    69.             }
    70.         }
    72.         while(!stack2.isEmpty()){
    73.             Node pop = stack2.pop();
    74.             System.out.print(pop.value+" ");
    75.         }
    77.     }
    79.     // 递归版本中序遍历   左头右
    80.     public static void MidOrder1(Node head){
    81.         if(head == null ){
    82.             return;
    83.         }
    84.         MidOrder1(head.left);
    85.         System.out.print(head.value + " ");
    86.         MidOrder1(head.right);
    87.     }
    88.     // 非递归版本中序遍历  左头右
    89.     // 每棵子树整棵树左边界进栈，依次弹出的过程中打印，对弹出节点的右树做重复操作压左边界进栈。
    90.     //    左头右(分解)
    91.     //        左头右....
    92.     public static void MidOrder2(Node head){
    93.         if(head == null ){
    94.             return;
    95.         }
    97.         Stack<Node> stack = new  Stack<>();
    98.         while(!stack.isEmpty() || head != null){
    100.             // 一直压左树，为空出栈打印，并对右树做同样操作。
    101.             if(head != null){
    102.                 stack.push(head);
    103.                 head = head.left;
    104.             }else {
    105.                 head = stack.pop();
    106.                 System.out.print(head.value + " ");
    107.                 head = head.right;
    108.             }    
    110.         }
    111.     }
    113.     // 树的宽度遍历
    114.     public static  void  WidthOrder(Node head){
    115.         if(head == null){
    116.             return;
    117.         }
    119.         Queue<Node> queue = new LinkedList<>();
    120.         queue.add(head);
    121.         while(!queue.isEmpty()){
    122.             Node poll = queue.poll();
    123.             System.out.print(poll.value + " ");
    125.             if(poll.left != null){
    126.                 queue.add(poll.left);
    127.             }
    129.             if(poll.right != null){
    130.                 queue.add(poll.right);
    131.             }
    132.         }
    134.     }