Java二叉树的遍历

定义二叉树的节点类型

class TreeNode {

    int value;

    public TreeNode(int value) {
        this.value = value;
    }

    TreeNode left = null;
    TreeNode right = null;
}

遍历

import java.util.LinkedList;

public class BinaryTreeErgodic {

    /**
     * 层次优先遍历
     */
    public static void lavelOrderTraverse(TreeNode root) {
        if (root == null)
            return;

        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        TreeNode current = null;
        queue.offer(root);
        while (!queue.isEmpty()) {
            current = queue.poll();
            System.out.print(current.value + " ");
            if (current.left != null)
                queue.offer(current.left);
            if (current.right != null)
                queue.offer(current.right);
        }
    }

    /**
     * 先序遍历
     */
    public static void preOrderTraverse(TreeNode node) {
        if (node == null)
            return;
        System.out.print(node.value + " ");
        preOrderTraverse(node.left);
        preOrderTraverse(node.right);
    }

    /**
     * 中序遍历
     */
    public static void inOrderTraverse(TreeNode node) {
        if (node == null)
            return;
        inOrderTraverse(node.left);
        System.out.print(node.value + " ");
        inOrderTraverse(node.right);
    }

    /**
     * 后序遍历
     */
    public static void postOrderTraverse(TreeNode node) {
        if (node == null)
            return;
        postOrderTraverse(node.left);
        postOrderTraverse(node.right);
        System.out.print(node.value + " ");
    }
}

上述代码分别实现了二叉树的 - **层次优先、前序（先序）、中序、后序 - **遍历，具体原理代码很清晰