PostOrderTraverse

By | November 26, 2014
0 Comment
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  
  1. public class PostOrderNonTraverse {
  3.     public static void main(String[] args){
  4.         Tree t17 = new Tree(17);
  5.         Tree t16 = new Tree(16);
  6.         Tree t15 = new Tree(15);
  7.         Tree t14 = new Tree(14);
  8.         Tree t13 = new Tree(13);
  9.         Tree t12 = new Tree(12);
  10.         Tree t11 = new Tree(11);
  11.         Tree t10 = new Tree(10);
  12.         Tree t9 = new Tree(9);
  13.         Tree t8 = new Tree(8);
  14.         Tree t7 = new Tree(7);
  15.         Tree t6 = new Tree(6);
  16.         Tree t5 = new Tree(5);
  17.         Tree t4 = new Tree(4);
  18.         Tree t3 = new Tree(3);
  19.         Tree t2 = new Tree(2);
  20.         Tree t1 = new Tree(1);
  21.         t8.left = t9;
  22.         t6.left = t8;
  23.         t5.right = t7;
  24.         t4.left = t5;
  25.         t4.right = t6;
  26.         t2.left = t4;
  27.         t1.left = t2;
  28.         t1.right = t3;
  29.         t6.right = t10;
  30.         t3.left = t11;
  31.         t3.right = t12;
  32.         t12.left = t13;
  33.         t12.right = t14;
  34.         t13.left = t15;
  35.         t13.right = t16;
  36.         PostTraverse(t1);
  37.     }
  39.     public static void PostTraverse(Tree tree){
  40.         ArrayList s = new ArrayList();
  41.         s.add(tree);
  42.         Tree prev = null;
  43.         Tree curr = null;
  44.         Tree next = null;
  45.         while(!s.isEmpty()){
  46.             curr = s.get(s.size()-1);
  47.             if(prev==null||prev.left==curr||prev.right==curr||(curr.left != prev)&&(curr.right != prev)){
  48.                 //新进来的
  49.                 if(curr.left==null&&curr.right==null){    //是叶子
  50.                     System.out.println(curr.value);
  51.                     s.remove(s.size()-1);
  52.                 }
  53.                 else{
  54.                     if(curr.right!=null){
  55.                         s.add(curr.right);
  56.                     }
  57.                     if(curr.left!=null){
  58.                         s.add(curr.left);
  59.                     }
  60.                 }
  61.             }
  62.             else if(curr.left == prev){    //从左子树返回的
  63.                 if(curr.right!=null){
  64.                     s.add(curr.right);
  65.                 }
  66.                 else{
  67.                     System.out.println(curr.value);
  68.                     s.remove(s.size()-1);
  69.                 }
  70.             }
  71.             else{    //从右子树返回
  72.                 System.out.println(curr.value);
  73.                 s.remove(s.size()-1);
  74.             }
  75.             prev = curr;
  76.         }
  77.     }
  78. }
  80. class Tree{
  81.     public Tree(int value){
  82.         this.value = value;
  83.     }
  84.     public Tree left;
  85.     public Tree right;
  86.     public int value;
  87. }