基础知识：二叉树的遍历

  1 class TreeNode {
  2     private Object element;
  3     private TreeNode leftChild;
  4     private TreeNode rightChild;
  5 
  6     //preOrder traversal recursion style
  7      public void preOrder(TreeNode root) {
  8         if (root != null) {
  9             System.out.println(root.element);
 10             preOrder(root.leftChild);
 11             preOrder(root.rightChild);
 12         }
 13     }
 14 
 15     //preOrder traversal no-recursion style
 16      public void preOrderNR(TreeNode root) {
 17         Stack<TreeNode> stack = new Stack<>();
 18         TreeNode p = root;
 19         while (p != null || !stack.empty()) {
 20 
 21             // start from left-part until arrive leaf node
 22             // then pop the top item in stack to traversal the
 23             // right-part
 24             while (p != null) {
 25                 System.out.println(p.element);
 26                 stack.push(p);
 27                 p = p.leftChild;
 28             }
 29 
 30             // when left-traversal finished pop top item in stack
 31             // traversal right-part
 32             if (!stack.empty()) {
 33                 p = stack.pop();
 34                 p = p.rightChild;
 35             }
 36         }
 37     }
 38 
 39     //inOrder traversal recursion style
 40     public void inOrder(TreeNode root) {
 41          if (root != null) {
 42              inOrder(root.leftChild);
 43              System.out.println(root.element);
 44              inOrder(rightChild);
 45          }
 46     }
 47 
 48     //inOrder traversal no-recursion style
 49     // little different with preOrder
 50     // just the step to read the root element
 51     public void inOrderNR(TreeNode root) {
 52         Stack<TreeNode> stack = new Stack<>();
 53         TreeNode p = root;
 54         while (p != null || !stack.empty()) {
 55             while (p != null) {
 56                 stack.push(p);
 57                 p = p.leftChild;
 58             }
 59 
 60             if (!stack.empty()) {
 61                 p = stack.pop();
 62                 System.out.println(p.element);
 63                 p = p.rightChild;
 64             }
 65         }
 66     }
 67 
 68     //postOrder traversal recursion style
 69     public void postOrder(TreeNode root) {
 70         if (root != null) {
 71             inOrder(root.leftChild);
 72             inOrder(rightChild);
 73             System.out.println(root.element);
 74         }
 75     }
 76 
 77     //postOrder traversal no-recursion style
 78     // when return from child should know it is which child
 79     // if arrive left-child just add ot in stack
 80     // else get top item in stack , if its right-child was visited
 81     // just print top item element because all left-child were visited
 82     public void postOrderNR(TreeNode root) {
 83         Stack<TreeNode> stack = new Stack<>();
 84         TreeNode p = root;
 85         TreeNode flag = null;
 86         while (p != null || !stack.empty()) {
 87             if (p != null) {
 88                 stack.push(p);
 89                 p = p.leftChild;
 90             } else {
 91                 p = stack.peek();
 92                 if (p.rightChild != null && p.rightChild != flag) {
 93                     p = p.rightChild;
 94                 } else {
 95                     stack.pop();
 96                     System.out.println(p.element);
 97                     flag = p;
 98                     p = null;
 99                 }
100             }
101         }
102     }
103 }