二叉树遍历

public class BinaryTree {   
      // Root node pointer. Will be null for an empty tree.   
      private Node root ;   
      private static class Node {   
          Node left ;   
          Node right ;   
          int data ;   
          Node( int newData) {   
              left = null ;   
              right = null ;   
              data = newData;   
          }   
      }   
      /**  
       Creates an empty binary tree -- a null root pointer.  
      */  
  
      public BinaryTree() {   
          root = null ;   
      }   
      /**  
       Inserts the given data into the binary tree.  
       Uses a recursive helper.  
      */  
      public void insert( int data) {   
//      System.out.println(data);   
        root = insert( root , data);   
      }   
      /**  
       Recursive insert -- given a node pointer, recur down and  
       insert the given data into the tree. Returns the new  
       node pointer (the standard way to communicate  
       a changed pointer back to the caller).  
       二叉搜索树  
      */  
  
      private Node insert(Node node, int data) {             
        if (node== null ) {   
          node = new Node(data);   
        }else {   
          if (data <= node. data ) {   
//            System.out.println("left:"+data);   
            node. left = insert(node. left , data);            
          }else {   
//              System.out.println("right:"+data);   
            node. right = insert(node. right , data);   
  
          }   
        }   
        return (node); // in any case, return the new pointer to the caller   
      }   
  
      public void buildTree( int [] data){   
          for ( int i=0;i<data.length ;i++){   
             insert(data[i]);   
          }    
  
      }   
  
      public void printTree() {   
          afterErgodic( root );   
          System. out .println();   
         }   
  
      private void printTree(Node node) {   
          if (node == null ) return ;   
          // left, node itself, right   
          printTree(node. left );   
          System. out .print(node. data + "  " );            
          printTree(node. right );   
         }   
  
      /**  
       * 先序遍历  
       * @param node  
       */  
      public void preErgodic(Node node){   
          if(node==null){   
              return;   
          }   
          Stack sk=new Stack();   
          Node p=node;   
          while(p!=null){   
              //把p节点的左子树的左子树的值获取出来   
              //把p节点的右子节点入栈，最上面的是右叶子节点   
              //栈底的节点为根的右子节点   
              while(p!=null){   
                  System.out.print(p.data+" ");   
                  //右子树入栈   
                  if(p.right!=null) sk.push(p.right);   
                  //进入下一个左子树   
                  p=p.left;   
              }   
              //遍历右子树，从右叶子节点开始，然后往上，若有左子节点，则执行上面的while步骤   
              if(!sk.isEmpty()){   
                  //进入下一个右子树   
                  p=(Node)sk.pop();   
//                System.out.print(p.data+ " ");   
              }   
          }   
      }   
       
      /**  
       * 中序遍历  
       * @param node  
       */  
      public void centerErgodic(Node node){   
          if(node==null){   
              return;   
          }   
          Stack sk=new Stack();   
          Node p=node;   
          while(p!=null||!sk.isEmpty()){   
              //把p节点的左子节点入栈，最上面的是左叶子节点   
              while(p!=null){   
                  sk.push(p);   
                  p=p.left;   
              }   
              //第一步是先把左叶子节点出栈，此时右节点为null   
              //第二步是把左叶子节点的父节点出栈，此时的右节点则是右叶子节点   
              //第三步则是把左叶子节点的父节点的父节点出栈，此时右节点含有子节点   
              //第四步开始则是对右节点开始遍历，步骤则是重复前三步   
              //第五步则是重复执行第三步和第四步，直到sk里面无节点为止   
              if(!sk.isEmpty()){   
                  p=(Node)sk.pop();   
                  System.out.print(p.data+" ");   
                  p=p.right;   
              }   
          }   
      }   
      /**  
       * 后序遍历  
       * @param node  
       */  
      public void afterErgodic(Node node){   
          if(node==null){   
              return;   
          }   
          Stack sk=new Stack();   
          Node p=node;   
             
          while(p!=null||!sk.isEmpty()){   
              //先左后右不断深入   
              while(p!=null){   
                  sk.push(p);//将根节点入栈   
                  if(p.left!=null) p=p.left;   
                  else p=p.right;   
              }   
                 
              //这里主要是叶子节点的获取   
              if(!sk.isEmpty()){   
                  p=(Node)sk.pop();   
                  System.out.print(p.data+" ");                  
              }   
                 
              //满足条件时，说明栈顶根节点右子树已访问，应出栈访问之   
              //这里肯定是非叶子节点   
              while(!sk.isEmpty()&&((Node)sk.peek()).right==p){   
                  p=(Node)sk.pop();   
                  System.out.print(p.data+" ");   
              }   
              //转向栈顶根节点的右子树继续后序遍历   
              if(!sk.isEmpty()) p=((Node)sk.peek()).right;   
              else p=null;               
          }   
      }   
         
      /**  
       * 另外一种建立二叉树的方法，非递归形式  
       * @param data  
       */  
      public void createBinary(int[] data){   
          Node temp = null;              
          for(int i=0;i<data.length;i++){   
              // 创建根节点    
              if(root==null){   
                  root = temp = new Node(data[i]);    
              }else{   
                // 回到根结点   
                  temp=root;   
                  // 添加节点      
                  while (temp.data != data[i]) {      
                      if(temp.data>data[i]){//左子树                             
                          if (temp.left != null) {   
//                            System.out.println(data[i]+" "+22);   
                              //如果有左子树，则把左子树赋值给temp，此次while循环结束，开始下次循环。   
                              //直到没有左子树为止，即新增加一个左子树   
                              temp = temp.left;   
                          }else{   
                              //新增左子树   
//                            System.out.println(data[i]+" "+11);   
                              temp.left=new Node(data[i]);   
                              //这里可以减少循环的次数，新增之后再判断时则会跳出循环   
                              temp = temp.left;   
                          }   
                      }else{//右子树   
                          if(temp.right!=null){   
                              //同左子树   
                              temp = temp.right;     
                          }else{   
                              temp.right=new Node(data[i]);   
                              //同上   
                              temp = temp.right;     
                          }   
                      }   
                  }   
              }          
          }   
//        return root;   
      }   
         
         
    /**  
     * @param args  
     */  
    public static void main(String[] args) {   
        BinaryTree bt=new BinaryTree();   
        //数据貌似不能是排好序的，但必须有顺序，貌似是前序遍历的顺序   
        int[] array={4, 2, 6, 1, 3, 5, 7};   
//      bt.buildTree(array);   
        bt.createBinary(array);   
        bt.printTree();   
//      #      4   
//      #    /    \   
//      #   2      6   
//      #  / \    / \   
//      # 1  3   5   7    
//      # 前序遍历：4 2 1 3 6 5 7      
//      # 中序遍历：1 2 3 4 5 6 7      
//      # 后序遍历：1 3 2 5 7 6 4      
    }   
  
}