二叉树遍历可以有两种方法：递归遍历的方式与非递归遍历的方式。
先序遍历就是先遍历根节点再左再右；
中序遍历就是先左再根再右；
后序遍历就是先左再右再根；
先构建这棵树，然后分别调用相应的方法实现，代码如下：
package binarytree; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Stack; public class Test { //递归遍历的方式与非递归遍历的方式: //一、递归的方式： //1、先序遍历： private static void preOrder1(Node root){ if(root == null) return; System.out.print(root.value); preOrder1(root.left); preOrder1(root.right); } //2、中序遍历： private static void midOrder1(Node root){ if(root == null) return; midOrder1(root.left); System.out.print(root.value); midOrder1(root.right); } //3、后序遍历： private static void postOrder1(Node root){ if(root == null) return; postOrder1(root.left); postOrder1(root.right); System.out.print(root.value); } //二、非递归的方式： //1、先序遍历： private static void preOrder2(Node root){ if(root == null) return; Stack<Node> stack = new Stack<>();//用栈来存储（先进后出） stack.push(root); while(!stack.isEmpty()){ Node node = stack.pop(); System.out.print(node.value); if(node.right != null) stack.push(node.right); if(node.left != null) stack.push(node.left); } } //2、中序遍历 private static void midOrder2(Node root){ if(root == null) return; Stack<Node> stack = new Stack<>(); Node cur = root; while(!stack.isEmpty() || cur != null){ while(cur != null){ stack.push(cur); cur = cur.left; } Node node = stack.pop(); System.out.print(node.value); if(node.right != null) cur= node.right; } } //3、后序遍历： private static void postOrder2(Node root){ if(root == null) return; Stack<Node> stack = new Stack<>(); Stack<Node> stack2 = new Stack<>(); stack.push(root); while(!stack.isEmpty()){ Node node = stack.pop(); stack2.push(node); if(node.left != null) stack.push(node.left); if(node.right != null) stack.push(node.right); } while(!stack2.isEmpty()){ System.out.print(stack2.pop().value); } } //三、层序遍历 private static void bfs(Node root){ if(root == null) return; Queue<Node> queue = new LinkedList<>();//用队列来存储（先进先出） queue.add(root); while(!queue.isEmpty()){ Node node = queue.poll(); System.out.print(node.value); if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } } private static List<List<String>> bfs2(Node root){ List<List<String>> res = new ArrayList<>();//存储节点（List里面套List） Queue<Node> queue = new LinkedList<>();//用队列来存储（先进先出） queue.add(root); List<String> list; while(!queue.isEmpty()){ int size = queue.size(); list = new ArrayList<>(); while(size-- > 0){ Node node = queue.poll(); list.add(node.value); if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } res.add(list); } return res; } public static void main(String[] args) { Node nodeA = new Node("A"); Node nodeB = new Node("B"); Node nodeC = new Node("C"); Node nodeD = new Node("D"); Node nodeE = new Node("E"); Node nodeF = new Node("F"); Node nodeG = new Node("G"); //构建二叉树 nodeA.left = nodeB; nodeA.right = nodeC; nodeB.left = nodeD; nodeB.right = nodeE; nodeC.right = nodeF; nodeE.left = nodeG; preOrder1(nodeA); System.out.println(); midOrder1(nodeA); System.out.println(); postOrder1(nodeA); System.out.println(); preOrder2(nodeA); System.out.println(); midOrder2(nodeA); System.out.println(); postOrder2(nodeA); System.out.println(); bfs(nodeA); bfs2(nodeA); } public static class Node{ //节点 public String value; public Node left; public Node right; public Node(String value){ this.value = value; } } }运行结果如下图所示：
其中，层序遍历这里多写了一个方法，将每层的节点存储起来：
private static List<List<String>> bfs2(Node root){ List<List<String>> res = new ArrayList<>();//存储节点（List里面套List） Queue<Node> queue = new LinkedList<>();//用队列来存储（先进先出） queue.add(root); List<String> list; while(!queue.isEmpty()){ int size = queue.size(); list = new ArrayList<>(); while(size-- > 0){ Node node = queue.poll(); list.add(node.value); if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } res.add(list); } return res; }在debug中查看res的结果：
