【算法】二叉树的前序、中序、后序遍历

原理

比如，有一个二叉树:

图片.png

前序遍历：DBEAFCG
中序遍历：ABDECFG
后序遍历：GCFAEBD

代码

前序遍历

    public static void main(String[] args) {
        TreeNode node7 = new TreeNode('G', null, null);
        TreeNode node6 = new TreeNode('F', null, null);
        TreeNode node5 = new TreeNode('E', null, null);
        TreeNode node4 = new TreeNode('D', null, null);
        TreeNode node3 = new TreeNode('C', node6, node7);
        TreeNode node2 = new TreeNode('B', node4, node5);
        TreeNode node1 = new TreeNode('A', node2, node3);

        traversalByFront(node1);
    }

    private static void traversalByFront(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            System.out.println(root.val);
            return;
        }
        if (root.left != null) {
            traversalByFront(root.left);
        }
        System.out.println(root.val);
        if (root.right != null) {
            traversalByFront(root.right);
        }
    }

中序遍历

    public static void main(String[] args) {
        TreeNode node7 = new TreeNode('G', null, null);
        TreeNode node6 = new TreeNode('F', null, null);
        TreeNode node5 = new TreeNode('E', null, null);
        TreeNode node4 = new TreeNode('D', null, null);
        TreeNode node3 = new TreeNode('C', node6, node7);
        TreeNode node2 = new TreeNode('B', node4, node5);
        TreeNode node1 = new TreeNode('A', node2, node3);

        traversalByMiddle(node1);
    }

    private static void traversalByMiddle(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            System.out.println(root.val);
            return;
        }
        System.out.println(root.val);
        if (root.left != null) {
            traversalByMiddle(root.left);
        }
        if (root.right != null) {
            traversalByMiddle(root.right);
        }
    }

后序遍历

    public static void main(String[] args) {
        TreeNode node7 = new TreeNode('G', null, null);
        TreeNode node6 = new TreeNode('F', null, null);
        TreeNode node5 = new TreeNode('E', null, null);
        TreeNode node4 = new TreeNode('D', null, null);
        TreeNode node3 = new TreeNode('C', node6, node7);
        TreeNode node2 = new TreeNode('B', node4, node5);
        TreeNode node1 = new TreeNode('A', node2, node3);

        traversalByBehind(node1);
    }

    private static void traversalByBehind(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            System.out.println(root.val);
            return;
        }
        if (root.right != null) {
            traversalByBehind(root.right);
        }
        System.out.println(root.val);
        if (root.left != null) {
            traversalByBehind(root.left);
        }
    }