递归遍历

  1. import java.util.Stack;
  3. /**
  4.  * @Description:分别用递归和非递归实现二叉树前序、中序、后序遍历
  5.  * @Author: lizhouwei
  6.  * @CreateDate: 2018/4/14 9:32
  7.  */
  9. //前序递归
  10. public void recPreOrder(Node head) {
  11.     if (head == null) {
  12.         return;
  13.     }
  14.     System.out.print(head.value + " ");
  15.     recPreOrder(head.left);
  16.     recPreOrder(head.right);
  17. }
  19. //中序递归
  20. public void recInOrder(Node head) {
  21.     if (head == null) {
  22.         return;
  23.     }
  24.     recInOrder(head.left);
  25.     System.out.print(head.value + " ");
  26.     recInOrder(head.right);
  27. }
  29. //后序递归
  30. public void recPostOrder(Node head) {
  31.     if (head == null) {
  32.         return;
  33.     }
  34.     recPostOrder(head.left);
  35.     recPostOrder(head.right);
  36.     System.out.print(head.value + " ");
  37. }

前序非递归

  1. //------------非递归----------------//
  2.     //前序
  3.     public void preOrder(Node head) {
  4.         if (head == null) {
  5.             return;
  6.         }
  7.         Stack<Node> stack = new Stack<Node>();
  8.         stack.push(head);
  9.         while (!stack.isEmpty()) {
  10.             head = stack.pop();
  11.             System.out.print(head.value + " ");
  12.             if (head.right != null) {
  13.                 stack.push(head.right);
  14.             }
  15.             if (head.left != null) {
  16.                 stack.push(head.left);
  17.             }
  18.         }
  19.     }

中序非递归

  1.      //中序
  2.     public void inOrder(Node head) {
  3.         if (head == null) {
  4.             return;
  5.         }
  6.         Stack<Node> stack = new Stack<Node>();
  7.         while (!stack.isEmpty() || head != null) {
  8.             if (head != null) {
  9.                 stack.push(head);
  10.                 head = head.left;
  11.             } else {
  12.                 head = stack.pop();
  13.                 System.out.print(head.value + " ");
  14.                 head = head.right;
  15.             }
  16.         }
  17.     }
  20.     //中序
  21.     public void inOrder(Node head) {
  22.         if (head == null) {
  23.             return;
  24.         }
  25.         Stack<Node> stack = new Stack<Node>();
  26.         while (!stack.isEmpty() || head != null) {
  27.             while (head != null) {
  28.                 stack.push(head);
  29.                 head = head.left;
  30.             }  
  31.             head = stack.pop();
  32.             System.out.print(head.value + " ");
  33.             head = head.right;
  34.         }
  35.     }

后序非递归

  1.      //后序
  2.     public void postOrder(Node head) {
  3.         if (head == null) {
  4.             return;
  5.         }
  6.         Node cur = null;
  7.         Stack<Node> stack = new Stack<Node>();
  8.         stack.push(head);
  9.         while (!stack.isEmpty()) {
  10.             cur = stack.peek();
  11.             if (cur.left != null && cur.left != head && cur.right != head) {
  12.                 stack.push(cur.left);
  13.             } else if (cur.right != null && cur.right != head) {
  14.                 stack.push(cur.right);
  15.             } else {
  16.                 head = stack.pop();
  17.                 System.out.print(head.value + " ");
  18.             }
  19.         }
  20.     }
  22.      //后序遍历
  23.     public  void postOrder(Node head){
  24.          if(head == null) return;
  25.          Node pre = null;//当前节点的之前访问的节点
  26.          Node cur;
  27.          Stack<Node> stack = new Stack<>();
  28.          stack.push(root);
  29.          while(!stack.isEmpty()){
  30.              cur = stack.peek();
  31.              //当前节点是叶子节点，可以直接访问该节点
  32.              //如果前一个节点不为空并且是当前节点的左孩子或者右孩子，
  33.              //  -->当是左孩子时说明当前节点右孩子为空，
  34.              //  -->当是右孩子时，说明左右孩子都访问过了，且都不为空
  35.              if((cur.left == null && cur.right == null) ||  
  36.                 (pre != null &&(pre == cur.left|| pre == cur.right)))
  37.              {
  38.                 System.out.print(cur.val + "-->"); 
  39.                  pre = stack.pop();
  40.              }
  41.              else{ 
  42.                  //当前节点为栈顶元素  如果当前节点不是叶子节点，
  43.                  // -->在当前节点之前访问的那个节点不是当前节点的孩子，则进行压栈
  45.                   //先压栈右节点再压栈左节点 这样出栈时是先左后右
  46.                  if(cur.right != null) {
  47.                      stack.push(cur.right);
  48.                  }
  49.                  if(cur.left != null){     
  50.                      stack.push(cur.left);
  51.                  }
  52.              }
  53.          }
  54.      }

测试

  1.  //测试
  2.     public static void main(String[] args) {
  3.         Chapter3_1 chapter = new Chapter3_1();
  4.         int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  5.         Node head = NodeUtil.generTree(arr, 0, arr.length - 1);
  6.         //前序递归打印
  7.         System.out.print("前序递归打印:");
  8.         chapter.recPreOrder(head);
  9.         System.out.println();
  10.         //前序非递归打印
  11.         System.out.print("前序非递归打印:");
  12.         chapter.preOrder(head);
  13.         System.out.println();
  14.         System.out.println();
  16.         //中序递归打印
  17.         System.out.print("中序递归打印:");
  18.         chapter.recInOrder(head);
  19.         System.out.println();
  20.         System.out.print("中序非递归打印:");
  21.         chapter.inOrder(head);
  22.         System.out.println();
  23.         System.out.println();
  24.         //后序递归打印
  25.         System.out.print("后序递归打印:");
  26.         chapter.recPostOrder(head);
  27.         System.out.println();
  28.         System.out.print("后序非递归打印:");
  29.         chapter.postOrder(head);
  30.     }