介绍

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。二叉树的遍历分为：前序遍历、中序遍历和后序遍历。
实现

public class BinaryTreeTraversal {
    /**
     * 二叉树结点类
     * @param <T> 二叉树存储的数据对象类型
     */
    private static class TreeNode<T> {
        /** 节点存储的值 */
        private T data;
        /** 左孩子节点 */
        private TreeNode<T> leftChild;
        /** 右孩子节点 */
        private TreeNode<T> rightChild;
        /**
         * 二叉树节点的构造方法
         * @param data 节点存储的值
         */
        TreeNode(T data) {
            this.data = data;
        }
    }
    /**
     * 标记节点类，用于二叉树的后序遍历时作标记使用
     * @param <T> 二叉树存储的数据对象类型
     */
    private static class TagNode<T> {
        /** 需要标记的节点 */
        private TreeNode<T> treeNode;
        /** 是否是第一次访问 */
        private boolean isFirst;
    }
    /**
     * 构建二叉树，用二叉树的前序遍历线性链表构建一颗二叉树
     * @param list 二叉树的前序遍历线性链表
     * @param <T> 二叉树存储的数据对象类型
     * @return 构建后的二叉树根节点
     */
    public static <T> TreeNode<T> createBinaryNode(LinkedList<T> list) {
        if (list == null || list.isEmpty()) {
            return null;
        }
        TreeNode<T> node = null;
        T data = list.removeFirst();
        if (data != null) {
            node = new TreeNode<>(data);
            node.leftChild = createBinaryNode(list);
            node.rightChild = createBinaryNode(list);
        }
        return node;
    }
    /**
     * 二叉树的前序遍历，用递归实现
     * @param node 需要遍历的节点
     * @param <T> 二叉树存储的数据对象类型
     */
    public static <T> void preOrderTraversalByRecursion(TreeNode<T> node) {
        if (node == null) {
            return;
        }
        System.out.print(node.data + " ");
        preOrderTraversalByRecursion(node.leftChild);
        preOrderTraversalByRecursion(node.rightChild);
    }
    /**
     * 二叉树的中序遍历，用递归实现
     * @param node 需要遍历的节点
     * @param <T> 二叉树存储的数据对象类型
     */
    public static <T> void midOrderTraversalByRecursion(TreeNode<T> node) {
        if (node == null) {
            return;
        }
        midOrderTraversalByRecursion(node.leftChild);
        System.out.print(node.data + " ");
        midOrderTraversalByRecursion(node.rightChild);
    }
    /**
     * 二叉树的后序遍历，用递归实现
     * @param node 需要遍历的节点
     * @param <T> 二叉树存储的数据对象类型
     */
    public static <T> void postOrderTraversalByRecursion(TreeNode<T> node) {
        if (node == null) {
            return;
        }
        postOrderTraversalByRecursion(node.leftChild);
        postOrderTraversalByRecursion(node.rightChild);
        System.out.print(node.data + " ");
    }
    /**
     * 二叉树的前序遍历，用栈实现
     *
     * 这种实现类似于图的深度优先遍历（DFS）。维护一个栈，将根节点入栈，然后只要
     * 栈不为空，出栈并访问，接着依次访问节点的右节点、左节点入栈。
     *
     * 这种方式应该是对前序遍历的一种特殊实现（看上去简单明了），但是不具备很好的
     * 扩展性，在中序遍历和后序遍历方式中不适用
     *
     * @param root 需要遍历的根节点
     * @param <T> 二叉树存储的数据对象类型
     */
    public static <T> void preOrderTraversalByStack(TreeNode<T> root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode<T>> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode<T> node = stack.pop();
            System.out.print(node.data + " ");
            if (node.rightChild != null) {
                stack.push(node.rightChild);
            }
            if (node.leftChild != null) {
                stack.push(node.leftChild);
            }
        }
    }
    /**
     * 二叉树的前序遍历，用栈实现
     *
     * 利用栈模拟递归过程实现循环前序遍历二叉树，这种方式具有扩展性，它模拟递归的
     * 过程，将左子树节点不断压入栈，直到 <code>null</code>，然后再处理栈顶节点
     * 的右子树。
     *
     * @param root 需要遍历的根节点
     * @param <T> 二叉树存储的数据对象类型
     */
    public static <T> void preOrderTraversalByStack2(TreeNode<T> root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode<T>> stack = new Stack<>();
        TreeNode<T> node = root;
        while (node != null || !stack.isEmpty()) {
            // 访问节点的的左孩子，并入栈
            while (node != null) {
                System.out.print(node.data + " ");
                stack.push(node);
                node = node.leftChild;
            }
            // 如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
            if (!stack.isEmpty()) {
                node = stack.pop();
                node = node.rightChild;
            }
        }
    }
    /**
     * 二叉树的中序遍历，用栈实现
     *
     * 利用栈模拟递归过程实现循环中序遍历二叉树，思想和上面先序非递归2
     * {@link #preOrderTraversalByStack2(TreeNode)} 相同，只是访问的时间是在
     * 左子树都处理完 <code>null</code> 的时候出栈并访问
     *
     * @param root 需要遍历的根节点
     * @param <T> 二叉树存储的数据对象类型
     */
    public static <T> void midOrderTraversalByStack(TreeNode<T> root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode<T>> stack = new Stack<>();
        TreeNode<T> node = root;
        while (node != null || !stack.isEmpty()) {
            // 访问节点的的左孩子，并入栈
            while (node != null) {
                stack.push(node);
                node = node.leftChild;
            }
            // 如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
            if (!stack.isEmpty()) {
                node = stack.pop();
                System.out.print(node.data + " ");
                node = node.rightChild;
            }
        }
    }
    /**
     * 二叉树的后序遍历，用栈实现，额外借助一个 {@link TagNode} 类来实现标记。
     *
     * 后续遍历不同于先序和中序，它是要先处理完左子树和右子树，然后再处理根节点（回溯）
     *
     * 对于任一节点p，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子出现
     * 的节点，此时该节点还未出现在栈顶，但是此时不能将其出栈并访问，因为其右孩子还
     * 未被访问。
     *
     * 所以接下来按照相同的规则对其右子树进行相同的处理，当访问完右子树时，该节点又
     * 出现在栈顶，此时可以将其出栈并访问，这样就保证了正确的访问顺序。
     *
     * 可以看出，在这个过程中，每个节点都两次出现在栈顶，只有第二次出现在栈顶时，才能
     * 访问它。因此需要多设置一个变量标识该节点是否第一次出现在栈顶，这里是在树结构里
     * 加一个标记，然后合成一个新的 {@link TagNode} 。
     *
     * @param root 需要遍历的根节点
     * @param <T> 二叉树存储的数据对象类型
     */
    public static <T> void postOrderTraversalByStack(TreeNode<T> root) {
        if (root == null) {
            return;
        }
        Stack<TagNode<T>> stack = new Stack<>();
        TreeNode<T> node = root;
        TagNode<T> tagNode;
        while (node != null || !stack.isEmpty()) {
            // 沿着左子树一直往下搜索，直至出现没有左孩子的节点
            while (node != null) {
                tagNode = new TagNode<>();
                tagNode.treeNode = node;
                tagNode.isFirst = true;
                stack.push(tagNode);
                node = node.leftChild;
            }
            if (!stack.isEmpty()) {
                tagNode = stack.pop();
                // 表示第一次出现在栈顶
                if (tagNode.isFirst) {
                    tagNode.isFirst = false;
                    stack.push(tagNode);
                    node = tagNode.treeNode.rightChild;
                } else {
                    //第二次出现在栈顶
                    System.out.print(tagNode.treeNode.data + " ");
                    node = null;
                }
            }
        }
    }
    /**
     * 二叉树的后序遍历，用栈实现，无需额外借助其它类来判断节点是否访问。
     *
     * 要保证根节点在左孩子和右孩子访问之后才能访问，因此对于任一节点p，先将其入栈。
     * 如果p不存在左孩子和右孩子，则可以直接访问它。
     *
     * 或者p存在左孩子和或右孩子，但其左孩子和右孩子都已经被访问过了，则同样可以直接
     * 访问该节点。
     *
     * 若非上述两种情况，则将p的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的
     * 时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根节点前面被访问。
     *
     * @param root 需要遍历的根节点
     * @param <T> 二叉树存储的数据对象类型
     */
    public static <T> void postOrderTraversalByStack2(TreeNode<T> root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode<T>> stack = new Stack<>();
        TreeNode<T> currentNode = null, preNode = null;
        stack.push(root);
        while (!stack.isEmpty()) {
            currentNode = stack.peek();
            // 如果当前节点没有孩子节点或者孩子节点都已经被访问过
            boolean isLeafNode = currentNode.leftChild == null && currentNode.rightChild == null;
            boolean isVisited = (preNode != null && (preNode == currentNode.leftChild
                    || preNode == currentNode.rightChild));
            if (isLeafNode || isVisited) {
                System.out.print(currentNode.data + " ");
                stack.pop();
                preNode = currentNode;
            } else {
                if (currentNode.rightChild != null) {
                    stack.push(currentNode.rightChild);
                }
                if (currentNode.leftChild != null) {
                    stack.push(currentNode.leftChild);
                }
            }
        }
    }
    /**
     * 二叉树的层级遍历，使用队列实现
     * @param root 需要遍历的根节点
     * @param <T> 二叉树存储的数据对象类型
     */
    public static <T> void levelOrderTraversalByQueue(TreeNode<T> root) {
        Queue<TreeNode<T>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode<T> node = queue.poll();
            System.out.print(node.data + " ");
            if (node.leftChild != null) {
                queue.offer(node.leftChild);
            }
            if (node.rightChild != null) {
                queue.offer(node.rightChild);
            }
        }
    }
    /**
     * 二叉树的层级遍历，使用递归实现，对层级相同的节点进行输出
     * @param root 需要遍历的根节点
     * @param <T> 二叉树存储的数据对象类型
     */
    public static <T> void levelOrderTraversalByRecursion(TreeNode<T> root) {
        int depth = depth(root);
        for (int i = 0; i < depth; i++) {
            doLevelOrderTraversalByRecursion(root, 0, i);
        }
    }
    /**
     * 对二叉树相同层级的节点进行递归输出
     * @param node 需要遍历的根节点
     * @param level 遍历层级
     * @param target 目标层级
     * @param <T> 二叉树存储的数据对象类型
     */
    private static <T> void doLevelOrderTraversalByRecursion(TreeNode<T> node, int level, int target) {
        if (node == null) {
            return;
        }
        if (level == target) {
            System.out.print(node.data + " ");
        }
        doLevelOrderTraversalByRecursion(node.leftChild, level + 1, target);
        doLevelOrderTraversalByRecursion(node.rightChild, level + 1, target);
    }
    /**
     * 求二叉树的深度
     * @param root 需要遍历的根节点
     * @return 二叉树的根节点
     */
    private static int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Integer.max(depth(root.leftChild), depth(root.rightChild)) + 1;
    }
    public static void main(String[] args) {
        // 构建二叉树
        LinkedList<Integer> list = new LinkedList<>(Arrays.asList(3, 2, 9, null, null,
                10, null, null, 8, null, 4));
        TreeNode<Integer> root = createBinaryNode(list);
        System.out.print("前序遍历(递归)：");
        preOrderTraversalByRecursion(root);
        System.out.println();
        System.out.print("中序遍历(递归)：");
        midOrderTraversalByRecursion(root);
        System.out.println();
        System.out.print("后序遍历(递归)：");
        postOrderTraversalByRecursion(root);
        System.out.println();
        System.out.print("前序遍历1(栈)：");
        preOrderTraversalByStack(root);
        System.out.println();
        System.out.print("前序遍历2(栈)：");
        preOrderTraversalByStack2(root);
        System.out.println();
        System.out.print("中序遍历(栈)：");
        midOrderTraversalByStack(root);
        System.out.println();
        System.out.print("后序遍历1(栈)：");
        postOrderTraversalByStack(root);
        System.out.println();
        System.out.print("后序遍历2(栈)：");
        postOrderTraversalByStack2(root);
        System.out.println();
        System.out.print("层级遍历(队列)：");
        levelOrderTraversalByQueue(root);
        System.out.println();
        System.out.print("层级遍历(递归)：");
        levelOrderTraversalByRecursion(root);
        System.out.println();
    }
}
二叉树遍历的实现方式

介绍

实现

评论
