使用非递归方式实现了二叉树的先序、中序、后序遍历
/** * 二叉树操作,包括: * 构造二叉树; * 先序遍历,中序遍历,后序遍历 * * @author cxp * @data 2016-9-19 * @modify */ public class BinaryTree { /** * 利用数组构造二叉树 * * @return */ public TreeNode createBinaryTree() { System.out.print("将使用下面的数字构建满二叉树:"); int[] values = { 5, 3, 7, 2, 4, 6, 8, 1 }; for (int i : values) { System.out.print(i + " "); } System.out.println(); System.out.println("-----------------------------------"); boolean isLeft = true;// 判断左节点是否已被赋值 int len = values.length;// 获取数组的长度 if (len == 0) return null; LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); TreeNode root = new TreeNode(values[0]);// 创建根结点 queue.addLast(root);// 将根结点添加到队列末尾 TreeNode parent = null; TreeNode current = null; for (int i = 1; i < len; i++) { current = new TreeNode(values[i]); queue.addLast(current);// 将当前结点添加到队列末尾 if (isLeft) parent = queue.getFirst();// 获取队列头的值 else parent = queue.removeFirst();// 移除队列头的值 if (isLeft) { parent.left = current; isLeft = false; } else { parent.right = current; isLeft = true; } } return root;// 返回二叉树的根结点 } /** * 二叉树的先序遍历(非递归) * 利用栈(后进先出)实现二叉树的先序遍历 * 压栈的时候访问结点值 * @param root * @return */ public List<Integer> preorderTraversal(TreeNode root) { List<Integer> nodeList = new ArrayList<Integer>();// 返回的先序遍历的结点列表 LinkedList<TreeNode> stack = new LinkedList<TreeNode>();// 链表实现的栈 if (root == null)// 根结点为空，直接返回 return nodeList; TreeNode current = null; stack.push(root);// 压入根结点 while (!stack.isEmpty()) {// 栈不为空时循环 current = stack.pop();// 当前结点出栈 nodeList.add(current.val);// 访问父结点 if (current.right != null)// 将当前结点的右子节点入栈 stack.push(current.right); if (current.left != null)// 将当前结点的左子节点入栈 stack.push(current.left); } return nodeList; } /** * 二叉树的中序遍历(非递归) * 利用栈(后进先出)实现二叉树的中序遍历 * 出栈的时候访问结点值 * @param root * @return */ public List<Integer> inorderTraversal(TreeNode root) { LinkedList<TreeNode> stack = new LinkedList<TreeNode>();// 用链表实现栈 List<Integer> nodeList = new ArrayList<Integer>();// 存储返回值的结点列表 TreeNode current = root; while (current != null || !stack.isEmpty()) { // 循环压入左结点 while (current != null) { stack.push(current);// 将当前结点压入栈中 current = current.left;//访问左结点 } current = stack.pop();// 结点出栈 nodeList.add(current.val);// 访问结点值 current = current.right;// 访问右结点 } return nodeList; } /** * 二叉树的后序遍历(非递归) * 总体思路是先将右边的值添加到结点列表(nodeList)中，再将左边的值添加进去(添加在列表头部) * 压栈的时候访问结点值 * @param root * @return */ public List<Integer> postorderTraversal(TreeNode root) { LinkedList<Integer> nodeList = new LinkedList<Integer>();// 返回的结点列表 LinkedList<TreeNode> stack = new LinkedList<TreeNode>();// 链表实现栈 if (root == null) return nodeList; TreeNode current = root;//根结点赋给当前访问结点 while (current != null || !stack.isEmpty()) { if (current != null) { stack.push(current);//将当前结点压入栈 nodeList.addFirst(current.val);//将结点值添加到结点列表的首部 current = current.right;//访问右结点，使右结点先入栈 } else { TreeNode node = stack.pop();//出栈 current = node.left;//访问左结点 } } return nodeList; } /** * 测试 * * @param args */ public static void main(String[] args) { // 创建二叉树类 BinaryTree binaryTree = new BinaryTree(); // 构造一个二叉树 TreeNode root = binaryTree.createBinaryTree(); // 先序遍历 System.out.println("先序遍历二叉树:"); System.out.println(binaryTree.preorderTraversal(root)); // 中序遍历 System.out.println("中序遍历二叉树:"); System.out.println(binaryTree.inorderTraversal(root)); // 后序遍历 System.out.println("后序遍历二叉树:"); System.out.println(binaryTree.postorderTraversal(root)); } }