二叉树遍历是树的最基本算法之一，是二叉树上进行其它运算之基础。

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。

访问结点所做的操作依赖于具体的应用问题。

① 前序遍历(PreorderTraversal亦称（先序遍历））

——访问根结点的操作发生在遍历其左右子树之前。

② 中序遍历(InorderTraversal)

——访问根结点的操作发生在遍历其左右子树之中（间）。

③ 后序遍历(PostorderTraversal)

——访问根结点的操作发生在遍历其左右子树之后。

④ 层次遍历(LevelTraversal)

——访问从根结点开始，逐层访问

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;

//二叉树的链式结构
class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;

  TreeNode(int x) {
    val = x;
  }
}

public class TestTraversalTreeNode {
  /**
   * 线序遍历
   * 
   * @param root   树根
   * @return
   */
  public static ArrayList<Integer> preorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    if (root == null)
      return result;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    while (!stack.isEmpty()) {
      TreeNode t = stack.pop();
      result.add(t.val);
      //先检查push右结点
      if (t.right != null) {
        stack.push(t.right);
      }
      if (t.left != null) {
        stack.push(t.left);
      }
    }
    return result;
  }

  /**
   * 中序遍历
   * 
   * @param root   树根
   * @return
   */
  public static ArrayList<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    if (root == null)
      return result;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode p = root;
    //如果有左结点则一直push
    while (!stack.isEmpty() || p != null) {
      if (p != null) {
        stack.push(p);
        p = p.left;
      } else {
        TreeNode n = stack.pop();
        result.add(n.val);
        p = n.right;
      }
    }
    return result;
  }

  /**
   * 后序遍历
   * 
   * @param root  树根
   * @return
   */
  public static ArrayList<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    if (root == null) {
      return result;
    }
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    TreeNode prev = null;// 记录当前结点的上一个结点
    while (!stack.empty()) {
      TreeNode curr = stack.peek();
      // 查看当前结点是否是叶节点，是的话就访问
      if (prev == null || prev.left == curr || prev.right == curr) {
        if (curr.left != null) {
          stack.push(curr.left);
        } else if (curr.right != null) {
          stack.push(curr.right);
        } else {// 当前结点是叶节点
          stack.pop();
          result.add(curr.val);
        }
        // 查看prev是否是的当前结点左结点
      } else if (curr.left == prev) {
        if (curr.right != null) {
          stack.push(curr.right);
        } else {
          stack.pop();
          result.add(curr.val);
        }
        // 查看prev是否是当前结点的右结点
      } else if (curr.right == prev) {
        stack.pop();
        result.add(curr.val);
      }
      prev = curr;
    }
    return result;
  }

  /**
   * 层次遍历
   * 
   * @param root  树根
   * @return
   */
  public static ArrayList<Integer> levelTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    LinkedList<TreeNode> current = new LinkedList<TreeNode>();
    if (root != null) {
      current.add(root);
      result.add(root.val);
    }
    while (current.size() > 0) {
      LinkedList<TreeNode> parents = current;
      current = new LinkedList<TreeNode>();
      for (TreeNode parent : parents) {
        if (parent.left != null) {
          current.add(parent.left);
          result.add(parent.left.val);
        }
        if (parent.right != null) {
          current.add(parent.right);
          result.add(parent.right.val);
        }
      }
    }
    return result;
  }

  /**
   * 遍历二叉树的第k行
   * 
   * @param root 二叉树根
   * @param k 第k行
   * @return 第k行的遍历
   */
  public static String findLevelList2(TreeNode root, int k) {
    ArrayList<LinkedList<TreeNode>> result = new ArrayList<LinkedList<TreeNode>>();
    LinkedList<TreeNode> current = new LinkedList<TreeNode>();
    if (root != null) {
      current.add(root);
    }
    int count = 0;
    while (current.size() > 0) {
      result.add(current);
      if (count == k) {
        return listToString(current);
      }
      count++;
      LinkedList<TreeNode> parents = current;
      current = new LinkedList<TreeNode>();
      for (TreeNode parent : parents) {
        if (parent.left != null) {
          current.add(parent.left);
        }
        if (parent.right != null) {
          current.add(parent.right);
        }
      }
    }
    return null;
  }

  /**
   * 链表的结点转化为字符串进行输出
   * @param list
   * @return
   */
  public static String listToString(LinkedList<TreeNode> list) {
    int[] arr = new int[list.size()];
    int i = 0;
    for (TreeNode node : list) {
      arr[i] = node.val;
      i++;
    }
    return Arrays.toString(arr);
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);
    System.out.println("前序：" + preorderTraversal(root).toString());
    System.out.println("中序：" + inorderTraversal(root).toString());
    System.out.println("后序：" + postorderTraversal(root).toString());
    System.out.println("顺序：" + levelTraversal(root).toString());
    System.out.println("K序：" + findLevelList2(root, 2));
  }
}

原文   http://blog.csdn.net/lgcssx/article/details/41049091