5.2遍历二叉搜索树（前，中，后，层次，广度优先遍历）

前言: 在上一节中，我们了解了该树及其相关知识二叉排序树中序遍历，并对二进制搜索树进行了基本实现. 下面我们继续改进我们的二进制搜索树.

对于二叉树，有深度遍历和宽度遍历. 深度遍历具有三种前，中，后三种遍历方法. 广度遍历就是我们通常所说的层次遍历，如图所示:

二叉树traversal.png

因为树的定义是一个递归定义，所以我们对前，中，后三个遍历使用递归方法，对于广度优先遍历，我们需要选择其他数据结构. 在此示例中，我们使用Queue来实现广度优先遍历.

四个基本遍历思想是:

遍历顺序: 根节点--->左子树--->右子树

按顺序遍历: 左子树--->根节点--->右子树

后遍历: 左子树->右子树->根节点

层遍历: 从上到下二叉排序树中序遍历，从左到右.

例如，以下二进制树的各种遍历:

Example.png

遍历顺序: 5-3-2-4-6-8

序列遍历: 2-3-4-5-6-8

后遍历: 2-4-3-8-6-5

遍历水平: 5-3-6-2-4-8

根据上述遍历思想: 根节点--->左子树--->右子树，代码实现如下:

 //二分搜索树的前序遍历(前序遍历：根结点 ---> 左子树 ---> 右子树)
    public void preOrder() {
        preOrder(root);
    }
    //前序遍历以node为根的二分搜索树,递归算法
    private void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }

根据上面提到的遍历思想: 左子树--->根节点--->右子树，代码实现如下:

   //二分搜索树的中序遍历(中序遍历：左子树---> 根结点 ---> 右子树)
    public void inOrder() {
        inOrder(root);
    }
    //中序遍历以node为根的二分搜索树,递归算法
    private void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

根据上面提到的遍历思想: 左子树--->右子树->根节点，代码实现如下:

    //二分搜索树的后序遍历(后序遍历：左子树 ---> 右子树 ---> 根结点)
    public void postOrder() {
        postOrder(root);
    }
    //后序遍历以node为根的二分搜索树,递归算法
    private void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }

对于分层遍历，我们基于队列来实现，其思想如下:

（1）首先将根节点添加到队列中

（2）对于任何其他随机节点，请在它们离开队列时访问（假设左右子节点不为空，请输入队列）

代码实现如下:

  //层次遍历--(基于队列实现)
    public void levelOrder() {
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            Node cur = q.remove();
            System.out.println(cur.e);
            if (cur.left != null) {
                q.add(cur.left);
            }
            if (cur.right!=null){
                q.add(cur.right);
            }
        }
    }

源代码地址

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-167732-1.html