二叉树各种遍历递归与非递归实现
/** * Created by zxm on 2018/4/11. * input:[1,2,3,4,5,6,8,9,10] */ class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(int x){ val=x; } } public class 二叉树 { public static void main(String args[]){ Scanner sc=new Scanner(System.in); while (sc.hasNext()){ String line=sc.nextLine(); TreeNode root=stringToTreeNode(line); LayerOrder(root); System.out.println(); LayerOrder1(root); PreOrder(root); System.out.println(); PreOrder1(root); System.out.println(); InOrder(root); System.out.println(); InOrder1(root); System.out.println(); PostOrder(root); System.out.println(); PostOrder1(root); System.out.println(); } } //由字符串[1,2,3,4,5,6,7,8,9] 层次构建二叉树 private static TreeNode stringToTreeNode(String input) { input=input.trim(); input=input.substring(1,input.length()-1); if(input.length()==0){ return null; } String[] parts=input.split(","); TreeNode root=new TreeNode(Integer.parseInt(parts[0])); Queue<TreeNode> queue=new LinkedList<>();//用队列保存所有节点的顺序，这样可以按顺序添加左右子树 queue.add(root); int index=1;//记录待添加进树的parts的位置 while(!queue.isEmpty()){ TreeNode node=queue.remove(); if(index==parts.length){ break; } String item=parts[index++].trim(); if(!item.equals("null")){ node.left=new TreeNode(Integer.parseInt(item)); queue.add(node.left); } if(index==parts.length){ break; } item=parts[index++].trim(); if(!item.equals("null")){ node.right=new TreeNode(Integer.parseInt(item)); queue.add(node.right); } } return root; } //层次遍历，递归实现 private static void LayerOrder(TreeNode root){ if(root!=null){ int depth=depth(root); for (int i=1;i<=depth;i++){ levelOrder(root,i); } } } private static int depth(TreeNode root) { if(root==null){ return 0; } int left=depth(root.left); int right=depth(root.right); if(left>right){ return left+1; }else { return right+1; } } private static void levelOrder(TreeNode root, int level) { if(root==null||level<1){ return; } if(level==1){ System.out.print(root.val); return; } //左子树 levelOrder(root.left,level-1); //右子树 levelOrder(root.right,level-1); } //层次遍历（广度优先遍历），非递归 private static void LayerOrder1(TreeNode root) { if (root==null){ System.out.println("Empty tree"); }else { Queue<TreeNode> queue=new LinkedList<>(); queue.add(root); while (!queue.isEmpty()){ TreeNode node=queue.remove(); System.out.print(node.val); if(node.left!=null) queue.add(node.left); if (node.right!=null) queue.add(node.right); } System.out.println(); } } //先序遍历，递归实现 private static void PreOrder(TreeNode root){ if(root!=null){ System.out.print(root.val); PreOrder(root.left); PreOrder(root.right); } } /**先序遍历，非递归实现 * 1、先入栈根结点，输出根结点val值，再先后入栈其右结点、左结点 * 2、出栈左结点，输出其val值，再入栈该左节点的右结点和左结点；直到遍历完该左结点所有子树。 * 3、再出栈右结点，输出其val值，再入栈该右结点的右结点和左结点；直到遍历完该右结点所有子树。 */ private static void PreOrder1(TreeNode root){ Stack<TreeNode> stack=new Stack<>(); if(root!=null){ stack.push(root); } while (!stack.isEmpty()){ TreeNode node=stack.pop(); System.out.print(node.val); //右结点先入栈，左结点后入栈 if(node.right!=null){ stack.push(node.right); } if(node.left!=null){ stack.push(node.left); } } } //中序遍历，递归实现 private static void InOrder(TreeNode root){ if (root!=null){ InOrder(root.left); System.out.print(root.val); InOrder(root.right); } } /**中序遍历，非递归实现 * 1、首先从根结点出发一路向左，入栈所有的左结点； * 2、出栈一个结点，输出该结点的val值，查询该结点是否存在右结点；若存在则从该右结点出发一路向左入栈该右结点的所在子树所有的左结点； * 3、若不存在右结点，则出栈下一个结点，输出该结点val值，同步骤2 操作； * 4、直到节点为null，且桟为空。 */ private static void InOrder1(TreeNode root){ Stack<TreeNode> stack=new Stack<>(); while (root!=null || !stack.empty()){ while(root!=null){ stack.push(root); root=root.left; } if(!stack.empty()){ TreeNode node=stack.pop(); System.out.print(node.val); root=node.right; } } } //后序遍历，递归实现 private static void PostOrder(TreeNode node){ if(node!=null){ PostOrder(node.left); PostOrder(node.right); System.out.print(node.val); } } /**后序遍历，非递归实现 * */ private static void PostOrder1(TreeNode node){ Stack<TreeNode> stack=new Stack<>(); Stack<TreeNode> output=new Stack<>();//构造一个中间栈来存储逆后续遍历的结果 while (node!=null||!stack.empty()){ if (node!=null){ output.push(node); stack.push(node); node=node.right; }else { node=stack.pop(); node=node.left; } } while (!output.empty()){ System.out.print(output.pop().val); } } }二叉树 前、中、后序遍历 非递归算法 通用版本 参考：YouTube
以二叉树先序遍历为例，我们访问一个节点，可以看成三步操作：打印改节点，访问该节点的左孩子，访问该节点的右孩子：
print A vistit Bvisit C对于结点B的访问，又分为三步：
print Bvisit Dvisit E用图来表示：
我们可以将节点和节点的操作封装成一个对象放入队列桟中，对于每个结点，要么是访问，要么是打印。
注意：遍历的顺序和压桟的顺序 应 刚好相反，如遍历界定 A ，应该是
print A vistit A.leftvisit A.right压桟顺序应刚好相反：
push(vistit A.right)push(vistit A.left)push(print A )按照这种思路，中序遍历和后序遍历就很容易了，只需要改变中间的三行代码就可以了。
前序遍历
class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result=new ArrayList<>();//存放结果 Stack<Guide> path=new Stack<>(); path.push(new Guide(0,root));//将根节点压桟 while(!path.isEmpty()){ Guide current=path.pop();//栈顶元素出栈 if(current.treeNode==null){//这里需要做判断，因为空节点也被放进了桟中 continue; } if(current.op==1){//如果是打印操作，则打印之 result.add(current.treeNode.val); }else{//按前序遍历的反序压桟 path.push(new Guide(0,current.treeNode.right)); path.push(new Guide(0,current.treeNode.left)); path.push(new Guide(1,current.treeNode)); } } return result; } private class Guide{ int op;//0 代表visit该节点,1 print 代表打印该节点 TreeNode treeNode; public Guide(int op,TreeNode node){ this.op=op; this.treeNode=node; } } }中序遍历：
class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result=new ArrayList<>(); Stack<Guide> path=new Stack<>(); path.push(new Guide(0,root)); while(!path.isEmpty()){ Guide current=path.pop(); if(current.treeNode==null){ continue; } if(current.op==1){ result.add(current.treeNode.val); }else{ path.push(new Guide(0,current.treeNode.right)); path.push(new Guide(1,current.treeNode)); path.push(new Guide(0,current.treeNode.left)); } } return result; } private class Guide{ int op;//0 代表visit该节点,1 print 代表打印该节点 TreeNode treeNode; public Guide(int op,TreeNode node){ this.op=op; this.treeNode=node; } } }后序遍历：
class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result=new ArrayList<>(); Stack<Guide> path=new Stack<>(); path.push(new Guide(0,root)); while(!path.isEmpty()){ Guide current=path.pop(); if(current.treeNode==null){ continue; } if(current.op==1){ result.add(current.treeNode.val); }else{ path.push(new Guide(1,current.treeNode)); path.push(new Guide(0,current.treeNode.right)); path.push(new Guide(0,current.treeNode.left)); } } return result; } private class Guide{ int op;//0 代表visit该节点,1 print 代表打印该节点 TreeNode treeNode; public Guide(int op,TreeNode node){ this.op=op; this.treeNode=node; } } }