二叉树的定义不多赘述，先贴上二叉树的代码

public class TreeNode {    int val;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val) {        // TODO Auto-generated constructor stub        this.val = val;    }}

 

前序遍历

　　递归实现：

public void preOrderRecur(TreeNode root){    if(root == null)        return root;    System.out.print(head.value+" ");    preOrderRecur(head.left);    preOrderRecur(head.right);}

　　非递归实现：

public void preOrderStack(TreeNode root){    if(root == null)        return root;    Stack
     
       stack = new Stack<>();    stack.push(root);    TreeNode cur = null;    while(!stack.isEmpty()){        cur = stack.pop();        System.out.print(cur.val+" ");        if(cur.right != null)            stack.push(cur.right);        if(cur.left != null)            stack.push(cur.left);            }}
     

 

中序遍历

　　递归实现：

public void inOrderRecur(TreeNode root){    if(root == null)        return root;    inOrderRecur(root.left);    System.out.print(root.value+" ");    inOrderRecur(root.right);    }

　　非递归实现：

public void inOrderStack(TreeNode root){    if(root == null)        return root;    Stack
     
       stack = new Stack<>();    TreeNode cur = root;    TreeNode node = null;    while(cur != null){        stack.push(cur);        cur = cur.left;        if(cur == null){            node = stack.pop();            System.out.print(node.val+" ");            cur = node.right;        }    }    }
     

 

后序遍历

　　递归实现：

public void posOrderRecur(TreeNode root){    if(root == null)        return root;    posOrderRecur(root.left);    posOrderRecur(root.right);    System.out.print(root.value+" ");    }

　　非递归实现：

public void posOrderStack(TreeNode root){    if(root == null)        return root;    Stack
     
       stack1 = new TreeNode<>();    Stack
      
        stack2 = new TreeNode<>();    TreeNode cur = root;    stack1.push(root);    while(!s1.isEmpty()){        cur = s1.pop();        stack2.push(cur);         if(cur.left != null)            stack1.push(cur.left);        if(cur.right != null)                    stack1.push(cur.right);    }        while(stack2.hasNext())        System.out.print(stack2.pop().val+" ");}
      
     

注：不论是递归还是非递归方法，遍历整棵树的时间复杂度都是O(N),额外的空间复杂度都是O(L),N为二叉树的节点数，L为二叉树的层数。