二叉树遍历：

import java.util.*;
​
public class Main {
    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;
​
        //递归方式
        preOrder(nodeA);
        System.out.println();
        midOrder(nodeA);
        System.out.println();
        postOrder(nodeA);
        System.out.println();
        //非递归方式
        preOrder2(nodeA);
        System.out.println();
        midOrder2(nodeA);
        System.out.println();
        postOrder2(nodeA);
        System.out.println();
        //层序遍历
        bfs(nodeA);
        System.out.println();
        List<List<String>> lists = bfs2(nodeA);
        for (List<String> list : lists) {
            for (String str : list) {
                System.out.print(str);
            }
            System.out.println();
        }
    }
​
    public static class Node {
        private String value;
        private Node left;
        private Node right;
​
        public Node(String value) {
            this.value = value;
        }
    }
​
    //递归方式
    //先序遍历
    private static void preOrder(Node root) {
        if (root == null) return;
        System.out.print(root.value);
        preOrder(root.left);
        preOrder(root.right);
    }
​
    //中序遍历
    private static void midOrder(Node root) {
        if (root == null) return;
        midOrder(root.left);
        System.out.print(root.value);
        midOrder(root.right);
    }
    //后序遍历
    private static void postOrder(Node root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.value);
    }
​
    //非递归方式
    //先序遍历
    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);
        }
    }
​
    //中序遍历
    private static void midOrder2(Node root) {
        if (root == null) return;
        Stack<Node> stack = new Stack<>();
        Node cur = root;
        while (cur != null || !stack.isEmpty()) {
            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;
        }
    }
    //后序遍历
    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<>();
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
​
        List<String> temp;
        while (!queue.isEmpty()) {
            int size = queue.size();
            temp = new ArrayList<>();
            while (size-- > 0) {
                Node node = queue.poll();
                temp.add(node.value);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            res.add(temp);
        }
​
        return res;
    }
​
​
}