二叉树遍历

二叉树的遍历，分为深度优先遍历和广度优先遍历，其中深度优先遍历又分为有前序、中序、后序遍历，广度优先遍历就是按层遍历

一、中序遍历

    public void inOrder(BSNode bsTreeNode) {
        if (bsTreeNode != null) {
            // 遍历左子树
            inOrder(bsTreeNode.left);
            // 输出节点数据
            System.out.print(bsTreeNode.data + " ");
            // 遍历右子树
            inOrder(bsTreeNode.right);
        }
    }

二、前序遍历

    public void preOrder(BSNode bsTreeNode) {
        if (bsTreeNode != null) {
            System.out.print(bsTreeNode.data + " ");
            preOrder(bsTreeNode.left);
            preOrder(bsTreeNode.right);
        }
    }

三、后序遍历

    public void postOrder(BSNode bsTreeNode) {
        if (bsTreeNode != null) {
            postOrder(bsTreeNode.left);
            postOrder(bsTreeNode.right);
            System.out.print(bsTreeNode.data + " ");
        }
    }

四、按层级遍历

    public void levelOrder(BSNode bsTreeNode) {
        if (bsTreeNode == null) {
            return;
        }
        LinkedList<BSNode> queue = new LinkedList<>();
        queue.offer(bsTreeNode);
        while (!queue.isEmpty()) {
            BSNode node = queue.poll();
            System.out.print(node.data + " ");
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }