二叉树的遍历方式有多种，前序遍历为其中一种，前序遍历的方式是按照根—左–右的顺序遍历的，即先遍历完所有的根，再遍历左，最后遍历右子树，如下图

前序遍历的理想结果是： 10, 6, 4, 8, 14, 12, 16

下面使用代码来实现上面的遍历，代码分别使用递归和非递归的方法实现，两者输出的结果一致

 package com.silverbox.user.web.htmdemo;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
 * 二叉树的前序遍历的非递归和递归的实现
 * 
 * @author ssj
 *
 */public class PreList {
public static void main(String[] args) {
// 创建一颗二叉树
TreeNode root = new TreeNode("10");
TreeNode n6 = new TreeNode("6");
TreeNode n14 = new TreeNode("14");
n6.setParent(root);
n14.setParent(root);
root.setLeft(n6);
root.setRight(n14);
TreeNode n4 = new TreeNode("4");
TreeNode n8 = new TreeNode("8");
n6.setLeft(n4);
n6.setRight(n8);
TreeNode n12 = new TreeNode("12");
TreeNode n16 = new TreeNode("16");
n14.setLeft(n12);
n14.setRight(n16);
System.out.println("---------递归遍历结果--------------------");
List list = new ArrayList();
preListDiGui(root, list);
System.out.println(list);


System.out.println("---------非递归遍历结果--------------------");
List list2 = preList(root);
System.out.println(list2);
}
/**
 * 递归前序遍历
 * 
 * @param root
 * @return
 */public static void preListDiGui(TreeNode root, List list) {
if (root == null) {
return;
}
list.add(root.name);
preListDiGui(root.left, list);
preListDiGui(root.right, list);
}
/**
 * 非递归前序遍历
 * 
 * @param root
 * @return
 */public static List preList(TreeNode root) {
Stack<TreeNode> sk = new Stack<TreeNode>();
List list = new ArrayList();
TreeNode n = root;
while (n != null) {
// 从当前节点开始，一直往左方向前进
while (n != null) {
// 输出当前节点
list.add(n.getName());
if (n.right != null) {
// 遇到右节点，入栈
sk.push(n.right);
}
n = n.left;
}
// 取出入栈的右节点
while (!sk.empty()) {
TreeNode n2 = sk.pop();
list.add(n2.getName());
if (n2.right != null) {
sk.push(n2.right);
}
// 如果该节点存在左节点，先输出所有的左节点，即重复以上过程
if (n2.left != null) {
n = n2.left;
break;
}
}
}
return list;
}
}
/**
 * 树节点
 * @author ssj
 *
 */class TreeNode {
public String name;
public TreeNode left;
public TreeNode right;
public TreeNode parent = null;
public boolean visitor=false;//标记该节点是否访问过
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public TreeNode(String name) {
super();
this.name = name;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}  

运行结果