二分搜索树的遍历

其实这里就是二叉树的遍历，只是因为二分搜索树因为是依靠它的特定规则而排列的，所以再经过不同方法遍历之后，它的顺序会有很多特点。

我们是依靠根节点顺序来命名的，记住！是根结点。

前序遍历就是先遍历根结点，然后遍历左结点，最后遍历右结点。

中序遍历就是先遍历左结点，然后遍历根结点，最后遍历右结点。

后序遍历就是先遍历左结点，然后遍历右结点，最后遍历根结点。

最后要注意，这个提示可能不是适合所有人，对于我来说，我书写一个二叉树的前中后序遍历的时候都告诫自己要等待一个结点能遍历的时候才能遍历，什么意思呢？就是要遍历一个结点的时候需要把它的子节点先遍历了（子节点优先遍历），其实这个前中后序遍历另一个名字就是深度优先遍历，跟这个有关。

慕课网中有另一种快速书写三种遍历方式遍历后的顺序结果的方法，如图:

三种深度优先遍历

它是在每个结点上画上三个点，然后不管什么遍历方式都从根节点到左节点到右节点的方式遍历(比较图中)，每个结点其实都会经过三次，当中序遍历就去中间的点作为顺序参照，前序遍历就取左边的点作为顺序参照，后序遍历就取右边的点作为顺序参照。

如果中序和后序的图看不懂，那么就将前序遍历那些顺序线放入中序和后序的图中，然后根据那个顺序线依次找蓝色的点，最后这些点连接成的就是遍历顺序了。

深度优先遍历的递归代码实现

前面说了，前中后序遍历都可以称为深度优先遍历。

//前序遍历
public void preOrder(){
  preOrder(root);
}
//前序遍历
private void preOrder(Node node){
  if (node!=null){
    //先打印根节点
    System.out.println(node.e);
    //然后遍历左节点
    preOrder(node.left);
    //遍历右结点
    preOrder(node.right);
  }
}
  public void inOrder(){
  inOrder(root);
}

private void inOrder(Node node){
  if (node!=null){
    //优先遍历左节点
    inOrder(node.left);
    System.out.println(node.e);
    inOrder(node.right);
  }
}

public void postOrder(){
  postOrder(root);
}

private void postOrder(Node node){
  if (node!=null){
    //先遍历左节点
    postOrder(node.left);
    //然后遍历右结点
    postOrder(node.right);
    //最后遍历根结点
    System.out.println(node.e);
  }
}

使用递归实现深度优先遍历很简单，只需要记住顺序就行了。

非递归实现前序遍历

其实非递归实现前序遍历就是模拟系统方法栈，这时候我们不通过递归，我们就要自己使用栈来实现前序遍历。

比如说我们需要将一个树前序遍历，这时候我们先将根结点放入我们new的一个栈中，然后我们把栈中这个结点元素取出来，对它进行打印(或者其他操作)，然后我们将它的右孩子，左孩子依次放入栈中(因为栈是先进后出)。然后我们再次取出栈中的一个元素，这时候我们取的是根结点的左孩子，然后我们对这个节点进行打印，然后把这个结点的右左孩子依次放入栈中，继续进行出栈操作。。。

非递归实现前序遍历

代码实现：

  /**
 * 非递归实现前序遍历
 */
public void perOrderWithoutRecurrence(){
  Stack<Node> stack=new Stack<>();
  stack.push(root);
  while (!stack.isEmpty()){
    //栈中元素不为空那么就出栈操作
    Node currentNode=stack.pop();
    System.out.println(currentNode.e);
    //依次将右左孩子放入栈中
    if (currentNode.right!=null){
      stack.push(currentNode.right);
    }
    if (currentNode.left!=null){
      stack.push(currentNode.left);
    }
  }
}

二叉树的层序遍历

层序遍历又是广度优先遍历，它是将树一层一层地进行遍历的。

广度优先遍历

比如上图，我们广度优先遍历（层序遍历）的顺序就是28,16,30,13,22,29,42.

我们如何实现呢？其实我们这时候需要一个队列，这个队列里将根结点放入，然后把根结点取出来进行操作（同时也要将队列里的根节点删除，后面的结点被取出来的时候也要删除），然后把根节点的左孩子，右孩子依次进行入队，这时候我们再取出队列里的第一个元素（根节点的左孩子结点），然后我们对它进行操作并删除队列里它的元素，然后将他的左右孩子依次入队，之后我们再取出来队列的第一个元素（根节点的右孩子），后面依次同上操作，如图所示。

代码实现：

  /**
 * 层序遍历(广度优先遍历)
 */
public void levelOrder(){
  if (root!=null){
    Queue<Node> queue=new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()){
      Node currentNode=queue.remove();
      System.out.println(currentNode.e);
      if (currentNode.left!=null){
        queue.add(currentNode.left);
      }
      if (currentNode.right!=null){
        queue.add(currentNode.right);
      }
    }
  }
}