算法-二叉树遍历（递归和非递归）

import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Scanner; import java.util.Stack; /** * Created by mifeng on 8/8/17. */ class Node { public String data; public Node left; public Node right; } class BiTree { Node root; public BiTree(){ this.root = null; } } public class TreeApp { /** * 先序递归建立二叉树 * @param node * @return */ public static Node create(Node node){ Scanner in = new Scanner(System.in); String value = in.next(); if("#".equals(value) ){ node = null; }else{ node = new Node(); node.data = value; node.left = create(node.left); node.right = create(node.right); } return node; } /** * 先序遍历二叉树-递归形式 * @param root */ public static void preOrderVisitByRecursive(Node root){ if(root == null){ return; }else{ System.out.print(root.data); preOrderVisitByRecursive(root.left); preOrderVisitByRecursive(root.right); } } //先序遍历二叉树-非递归 public static void preOrderVisit(Node root){ if(root == null){ return; }else{ // Stack<String> stack = new Stack<String>(); // stack.push(root.data); // System.out.println(stack.pop()); Stack<Node> stack = new Stack<Node>(); stack.push(root); // System.out.println(stack.pop()); while (stack.size()!=0){ // Node currentNode = root; // //stack.push(currentNode.data); // if(root.right!=null) // stack.push(root.right.data); // if(root.left!=null) // stack.push(root.left.data); // System.out.println(stack.pop()); // //root = root.right; Node currentNode = stack.pop(); System.out.print(currentNode.data); //stack.push(currentNode.data); // if(root.right!=null) // stack.push(root.right); // if(root.left!=null) // stack.push(root.left); // System.out.println(stack.pop()); if(currentNode.right!=null) stack.push(currentNode.right); if(currentNode.left!=null) stack.push(currentNode.left); //System.out.println(stack.pop()); } // while(stack.size()!=0){ // stack.pop(); // } // Stack<Node> stack = new Stack<Node>(); // stack.push(root); } } public static void preOrderVisit2(Node root){ Stack<String> stack = new Stack<String>(); if(root == null){ return; }else{ stack.push(root.data); while(true){ System.out.println(root.data); if(root.right!=null) stack.push(root.right.data); if(root.left!=null) stack.push(root.left.data); String data = stack.pop(); System.out.println(data); } } } //中序遍历-递归 public static void InOrderVisitByRecursive(Node root){ if(root == null){ return; } InOrderVisitByRecursive(root.left); System.out.print(root.data); InOrderVisitByRecursive(root.right); } //中序遍历-非递归 public static void InOrderVisit(Node root){ Stack<String> stack = new Stack<String>(); if(root!=null){ stack.push(root.data); while(root!=null){ root = root.left; } } } public static void InorderVisit2(Node root){ Stack<Node> stack = new Stack<Node>(); if(root!=null){ stack.push(root); while(root!=null){ stack.push(root); root = root.left; } Node currentNode = stack.pop(); System.out.print(currentNode.data); root = currentNode.right; System.out.println(currentNode.data); } } public static void InOrderVisit3(Node root){ Stack<Node> stack = new Stack<Node>(); if(root!=null){ //stack.push(root); while(!stack.isEmpty()||root!=null){ if(root!=null){ stack.push(root); root = root.left; }else{ Node currentNode = stack.pop(); System.out.print(currentNode.data); root = currentNode.right; } } // Node currentNode = stack.pop(); // System.out.print(currentNode.data); // root = currentNode.right; // System.out.println(currentNode.data); } } //层次序列化二叉树 public static void visitByLevel(Node head){ Queue<Node> queue = new LinkedList<Node>(); if(head == null){ return ; } queue.offer(head); while(!queue.isEmpty()){ Node currNode = queue.poll(); System.out.println(currNode.data); if(currNode.left!=null) queue.offer(currNode.left); if(currNode.right!=null) queue.offer(currNode.right); } //return ""; } public static void main(String[] args){ BiTree tree = new BiTree(); tree.root = create(tree.root); //System.out.println(tree.root.data); //System.out.println(tree.root.left.data); System.out.println("先序遍历二叉树-递归"); preOrderVisitByRecursive(tree.root); System.out.println("先序遍历二叉树-非递归"); preOrderVisit(tree.root); System.out.println("中序遍历二叉树-递归"); InOrderVisitByRecursive(tree.root); System.out.println("中序遍历二叉树-非递归"); InOrderVisit3(tree.root); System.out.println("层次遍历："); visitByLevel(tree.root); //List<String> list = new ArrayList<String>(new ArrayList<String>()); } }