二叉树的层序遍历算法实现

一，问题描述

实现二叉树的层序遍历--从根开始，依次向下，对于每一层从左向右遍历。

二，算法分析

层序遍历与先序、中序、后序遍历不同。层序遍历用到了队列，而先、中、后序需要用到栈。

因此，先、中、后序遍历 可以 采用递归方式来实现，而层序遍历则没有递归方式。

算法步骤：

初始时，根结点入队列

然后，while循环判断队列不空时，弹出一个结点，访问它，并把它的所有孩子结点入队列。

三，代码实现

public void levelTraverse(BinarySearchTree<T> tree){

        levelTraverse(tree.root);

    }

    private void levelTraverse(BinaryNode<T> root){

        if(root == null)

            return;

        Queue<BinaryNode<T>> queue = new LinkedList<>();//层序遍历时保存结点的队列

        queue.offer(root);//初始化

        while(!queue.isEmpty()){

            BinaryNode<T> node = queue.poll();

            System.out.print(node.element + " ");//访问节点

            if(node.left != null)

                queue.offer(node.left);

            if(node.right != null)

                queue.offer(node.right);

        }

    }