Java二进制搜索树遍历操作的详细描述[前，中，后，层次，广度优先遍历]

本文介绍了Java二进制搜索树遍历操作. 与您分享以供参考，如下:

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

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

由于树本身的定义是递归定义，因此我们使用递归方法来实现前顺序，中顺序和后顺序的三个遍历. 对于广度优先遍历二叉排序树 遍历，我们需要选择其他数据结构. 排队以实现广度优先遍历.

四个基本遍历思想是:

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

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

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

层遍历: 从上到下，从左到右.

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

遍历顺序: 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);
      }
    }
  }

源代码地址

更多对Java算法相关内容感兴趣的读者可以查看该站点的主题: “ Java数据结构和算法教程”，“在Java中操作DOM节点的技术摘要”，“用于操作Java文件和技术的技术摘要”. 目录”和“ Java Cache操作技巧摘要”

我希望本文对Java编程的每个人都有帮助.

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