概念如下：先序遍历
递归较为简单，我们只需将每个节点的遍历分为三步：
当前节点的读取
该节点左子树的先序遍历
该节点右子树的先序遍历
再附以特殊情况的判断——root==null即可。
代码如下：
public void preTravel_recursion(Tree_triple root){ if(root==null) return; visit(root); preTravel_recursion(root.left); preTravel_recursion(root.right); }【注】在这里我把Tree类型变量声明为了Tree_triple，仅仅是名字上的不同，还望见谅。
众所周知，只要是递归能够实现的，我们用栈同样可以，但需要考虑清楚先序遍历再压栈中的顺序——先压左子树(false)还是右子树(true)。
代码如下：
public void preTravel_non_recursion(Tree_triple root) throws Exception{ if(root==null) return; Stack s=new Stack(20); s.push(root);; while(!s.isEmpty()){ Tree_triple node=(Tree_triple) s.pop(); if(node==null) continue; visit(node); s.push(node.right);//先右后左——栈先进后出 s.push(node.left); } }【注】关于我在方法中使用了throws Exception大可不必深究（以下同理），这是由我使用的是自建栈Stack，看我之前发文中会有关于Stack的数组，链表实现的代码。
概念如下：中序遍历
同样比较简单，我们仅需改变读取顺序即可：
中序遍历左子树读取当前节点中序遍历右子树再附以null判断即可。
代码如下：
public void midTravel_recursion(Tree_triple root){ if(root==null) return; midTravel_recursion(root.left); visit(root); midTravel_recursion(root.right); }在这一步会变得比较难以理解，但我们需要明确如下几个步骤：
一直向左下遍历，直到获取最左下角的子节点。在向左下遍历的同时，将我们读到的每一个节点压入栈中。当我们找到最左下角的子节点时，如果栈不为空，开始退栈，并读取当前节点，然后指向它的右子树，重复1中的步骤。如果栈为空，退出1~4中的循环。代码如下：
public void midTravel_non_recursion(Tree_triple root) throws Exception{ if(root==null) return; Stack s=new Stack(20); Tree_triple p=root; while(true){ while(p!=null){ s.push(p); p=p.left; } if(!s.isEmpty()){ p=(Tree_triple) s.pop(); visit(p); p=p.right; } else break; } System.out.println(); }概念如下：后序遍历
同样比较简单，顺序如下：
后序遍历左子树后序遍历右子树读取当前节点再附以对null的判断即可。
代码如下：
public void bacTravel_recursion(Tree_triple root){ if(root==null) return; bacTravel_recursion(root.left); bacTravel_recursion(root.right); visit(root); }它的非递归实现比较复杂，如下呈现两种实现方法：
一：
构建两个Tree类型指针：curnode（当前节点）和prenode（上一个读取的节点）同样通过不断循环遍历寻找最左下角的节点，同时挨个压栈入stack，构建一个循环，标准为!stack.isEmpty()。开始退栈，curnode为stack.pop()，当且仅当curnode.right不为null而且curnode.right!=prenode时，表示该节点右右子树而且我们还没有遍历过，这时把弹出的curnode重新压入栈，继续循环开始遍历寻找最左下角的节点；否则，开始读取当前节点，并赋值curnode为prenode。代码如下：
public void bacTravel_non_recursion(Tree_triple root) throws Exception{ if(root==null) return; Stack s=new Stack(20); Tree_triple curnode=root; Tree_triple prenode=null; while(curnode!=null){ s.push(curnode); curnode=curnode.left; } while(!s.isEmpty()){ curnode=(Tree_triple) s.pop(); if(curnode.right!=null&&curnode.right!=prenode){ s.push(curnode); curnode=curnode.right; while(curnode!=null){ s.push(curnode); curnode=curnode.left; } } else{ visit(curnode); prenode=curnode; } } System.out.println(); }二：
包装树与一个计数常量tag，其中，tag为0表示第一次遍历该节点，它的出栈仅仅为了获取它的右子树，出栈后改tag为1再压栈； tag为1时表示第二次遍历该节点，它出栈后可以开始读取，再继续出栈。其余操作与之前中序遍历的非递归算法相似。代码如下：
Tree_tag类：
package NineWeek; public class Tree_tag { public Tree_forReview node; public int tag; public Tree_tag(){} }操作方法：
private static void visitInBacinclass(Tree_forReview root) throws Exception { // TODO Auto-generated method stub System.out.println("后序遍历："); Stack s=new Stack(20); Tree_tag Cnode=new Tree_tag(); Tree_forReview p=root; while(true){ while(p!=null){ Cnode.node=p; Cnode.tag=0; s.push(Cnode); p=p.left; } Cnode=(Tree_tag) s.pop(); p=Cnode.node; if(Cnode.tag==1){//第二次读取 visit(p); if(!s.isEmpty()){ Cnode=(Tree_tag) s.pop(); p=Cnode.node; } else return; }//第一次读取 Cnode.tag=1; s.push(Cnode); p=p.right; } }【注】这里的Tree_forReview 和Tree_triple一样，都是Tree类，由于两个版本的代码时是我在不同时期写入的，名称有别，还望见谅。
以下附上全部代码：
Tree_triple类：
package NineWeek; public class Tree_triple { public Tree_triple left; public Tree_triple right; public Object value; public Tree_triple(Object x){this.value=x;} public Tree_triple(){} public void addLeft(Object x){ this.left=new Tree_triple(x); } public void addRight(Object x){ this.right=new Tree_triple(x); } }功能实现：
package NineWeek; public class Tree_triple_tools { private void visit(Tree_triple root) { // TODO Auto-generated method stub System.out.print(root.value+", "); } public void preTravel_recursion(Tree_triple root){ if(root==null) return; visit(root); preTravel_recursion(root.left); preTravel_recursion(root.right); } /** * 先序遍历的非递归算法 * @param root * @throws Exception */ public void preTravel_non_recursion(Tree_triple root) throws Exception{ if(root==null) return; Stack s=new Stack(20); s.push(root);; while(!s.isEmpty()){ Tree_triple node=(Tree_triple) s.pop(); if(node==null) continue; visit(node); s.push(node.right);//先右后左——栈先进后出 s.push(node.left); } } public void midTravel_recursion(Tree_triple root){ if(root==null) return; midTravel_recursion(root.left); visit(root); midTravel_recursion(root.right); } /** * 中序遍历的非递归算法 * @param root * @throws Exception */ public void midTravel_non_recursion(Tree_triple root) throws Exception{ if(root==null) return; Stack s=new Stack(20); Tree_triple p=root; while(true){ while(p!=null){ s.push(p); p=p.left; } if(!s.isEmpty()){ p=(Tree_triple) s.pop(); visit(p); p=p.right; } else break; } System.out.println(); } public void bacTravel_recursion(Tree_triple root){ if(root==null) return; bacTravel_recursion(root.left); bacTravel_recursion(root.right); visit(root); } /** * 后序遍历的非递归算法 * @param root * @throws Exception */ public void bacTravel_non_recursion(Tree_triple root) throws Exception{ if(root==null) return; Stack s=new Stack(20); Tree_triple curnode=root; Tree_triple prenode=null; while(curnode!=null){ s.push(curnode); curnode=curnode.left; } while(!s.isEmpty()){ curnode=(Tree_triple) s.pop(); if(curnode.right!=null&&curnode.right!=prenode){ s.push(curnode); curnode=curnode.right; while(curnode!=null){ s.push(curnode); curnode=curnode.left; } } else{ visit(curnode); prenode=curnode; } } System.out.println(); } }结果如下：
preTravel: 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6, midTravel: 4, 2, 5, 1, 3, 6, 4, 2, 5, 1, 3, 6, bacTravel: 4, 5, 2, 6, 3, 1, 4, 5, 2, 6, 3, 1,
