二叉树三种遍历递归及非递归实现

二叉树的三种遍历方式包括：

前序遍历中序遍历后序遍历

三种遍历的递归方法都非常好实现，而且简单易懂。非递归实现也是通过使用栈来模拟遍历的过程。顺便提一句，能用递归做的，基本都能用栈来实现。前序遍历和中序遍历的非递归写法相对比较简单，只需要模拟遍历过程即可。后序遍历非递归写法比较难，需要借助一个辅助指针来记录右子树是否访问过，以防止重复访问陷入死循环。下面分别给出三种遍历方法的递归和非递归实现的代码：

前序遍历

递归：

public void PreOrderTraversal(TreeNode root) { if (root == null) { return; } System.out.print(root.val); if (root.left != null) { PreOrderTraversal(root.left); } if (root.right != null) { PreOrderTraversal(root.right); } }

非递归：

public void PreOrderTraversal2(TreeNode root){ Stack<TreeNode> stack = new Stack<>(); TreeNode node; if (root == null) { return; } stack.push(root); while (!stack.empty()) { node = stack.pop(); System.out.print(node.val); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); }//end if } }

将根节点放入栈中，当栈不空时，取出栈顶元素x，访问x的值，如果x的左孩子不为空，将其左孩子入栈；如果其右孩子不为空，将其右孩子入栈，直至栈空。

中序遍历

递归：

public void InOrderTraversal(TreeNode root) { if (root == null) { return; } if (root.left != null) { InOrderTraversal(root.left); } System.out.print(root.val); if (root.right != null) { InOrderTraversal(root.right); } } 非递归：

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

1、先遍历到二叉树的最左结点

2、弹出栈顶元素x并访问

3、考察x的右子树是否为空，如果为空则执行2，否则将当前结点设为x的右子树并执行1.

后序遍历

递归：

public void PostOrderTraversal(TreeNode root) { if (root == null) { return; } if (root.left != null) { PostOrderTraversal(root.left); } if (root.right != null) { PostOrderTraversal(root.right); } System.out.print(root.val); } 非递归：

public void PostOrderTraversal2(TreeNode root) { if (root == null) { return; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); TreeNode node = root.left; TreeNode lastVisit = null; while (node != null) { stack.push(node); node = node.left; } while (!stack.empty()) { node = stack.pop(); if (node.right == null || node.right == lastVisit) { System.out.print(node.val); lastVisit = node; } else { stack.push(node); node = node.right; while (node != null) { stack.push(node); node = node.left; } } } }

后序遍历非递归做法需要设置一个指针lastVisit指向上次输出的元素。

1、从根节点开始遍历到最左节点

2、当栈不空时弹出栈顶元素

3、如果栈顶元素x的右子树为空或者x的右子树等于lastVisit说明该右子树已经访问过，访问当前节点x并将lastVisit指向x。

否则将x压回栈中，并且将当前节点指向x的右子树，执行步骤1.