快捷導(dǎo)航

Java二叉搜索樹遍歷操作詳解【前序、中序、后序、層次、廣度優(yōu)先遍歷】

更新時(shí)間：2020年03月19日 14:27:17 作者：WFaceBoss

這篇文章主要介紹了Java二叉搜索樹遍歷操作,結(jié)合實(shí)例形式詳細(xì)分析了Java二叉搜索樹前序、中序、后序、層次、廣度優(yōu)先遍歷等相關(guān)原理與操作技巧,需要的朋友可以參考下

本文實(shí)例講述了Java二叉搜索樹遍歷操作。分享給大家供大家參考，具體如下：

前言：在上一節(jié)Java二叉搜索樹基礎(chǔ)中，我們對(duì)樹及其相關(guān)知識(shí)做了了解，對(duì)二叉搜索樹做了基本的實(shí)現(xiàn)，下面我們繼續(xù)完善我們的二叉搜索樹。

對(duì)于二叉樹，有深度遍歷和廣度遍歷，深度遍歷有前序、中序以及后序三種遍歷方法，廣度遍歷即我們尋常所說的層次遍歷，如圖：

因?yàn)闃涞亩x本身就是遞歸定義，所以對(duì)于前序、中序以及后序這三種遍歷我們使用遞歸的方法實(shí)現(xiàn)，而對(duì)于廣度優(yōu)先遍歷需要選擇其他數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，本例中我們使用隊(duì)列來實(shí)現(xiàn)廣度優(yōu)先遍歷。

四種基本的遍歷思想為：

前序遍歷：根結(jié)點(diǎn) ---> 左子樹 ---> 右子樹
中序遍歷：左子樹---> 根結(jié)點(diǎn) ---> 右子樹
后序遍歷：左子樹 ---> 右子樹 ---> 根結(jié)點(diǎn)
層次遍歷：從上到下，從左到右。

比如，以下二叉樹的各種遍歷：

前序遍歷:5-3-2-4-6-8
中序遍歷:2-3-4-5-6-8
后序遍歷:2-4-3-8-6-5
層次遍歷：5-3-6-2-4-8

一、前序遍歷

依據(jù)上文提到的遍歷思路：根結(jié)點(diǎn) ---> 左子樹 ---> 右子樹，代碼實(shí)現(xiàn)如下：

 //二分搜索樹的前序遍歷(前序遍歷：根結(jié)點(diǎn) ---> 左子樹 ---> 右子樹)
  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);
  }

二、中序遍歷

依據(jù)上文提到的遍歷思路：左子樹 ---> 根結(jié)點(diǎn) ---> 右子樹，代碼實(shí)現(xiàn)如下：

  //二分搜索樹的中序遍歷(中序遍歷：左子樹---> 根結(jié)點(diǎn) ---> 右子樹)
  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);
  }

三、后序遍歷

依據(jù)上文提到的遍歷思路：左子樹 ---> 右子樹 ---> 根結(jié)點(diǎn),代碼實(shí)現(xiàn)如下：

  //二分搜索樹的后序遍歷(后序遍歷：左子樹 ---> 右子樹 ---> 根結(jié)點(diǎn))
  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);
  }

四、層次遍歷

對(duì)于層次遍歷，我們基于隊(duì)列來實(shí)現(xiàn)，思路如下：
（1）先在隊(duì)列中增加根結(jié)點(diǎn)
（2）對(duì)于隨意其余任意節(jié)點(diǎn)，在其出隊(duì)列的時(shí)候訪問（假設(shè)左孩子和右孩子有不為空的情況，入隊(duì)列）
代碼實(shí)現(xiàn)如下：

//層次遍歷--(基于隊(duì)列實(shí)現(xiàn))
  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);
      }
    }
  }

源代碼地址 https://github.com/FelixBin/dataStructure/blob/master/src/BST/BST.java

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: