前言

成都創(chuàng)新互聯(lián)自2013年起，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目做網(wǎng)站、網(wǎng)站建設(shè)網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元祿勸做網(wǎng)站,已為上家服務(wù),為祿勸各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18982081108

三種遍歷的遞歸寫法都很好寫，所以總結(jié)一下非遞歸寫法。

先貼一張圖復(fù)習(xí)一下三種遍歷方式就進(jìn)入正文啦~

【注：本文所有代碼實(shí)現(xiàn)中樹的結(jié)點(diǎn)定義如下：

public class Node {
  int val;
  Node left;
  Node right;
  Node parent;
  Node() {}
  Node(int val) {
    this.val = val;
  }
}

1.前序遍歷

實(shí)現(xiàn)思路：

前序遍歷的順序是：根結(jié)點(diǎn) -> 左孩子 -> 右孩子

借助一個(gè)棧結(jié)構(gòu)先將根結(jié)點(diǎn)壓入棧，然后循環(huán)每次取出棧頂元素，直到棧為空。如果當(dāng)前結(jié)點(diǎn)有右孩子就先將右孩子壓入棧中，如果當(dāng)前結(jié)點(diǎn)有左孩子就將左孩子壓入棧中，這里注意順序，因?yàn)闂５慕Y(jié)構(gòu)是先進(jìn)后出的，為了保證先遍歷到左孩子就應(yīng)該后壓左孩子~

代碼實(shí)現(xiàn)：

【代碼使用直接輸出的方式打印中序遍歷結(jié)果，也可以放入一個(gè)list中存儲(chǔ)~】

public void preOrder(Node head) {
    System.out.println("pre-order:");
    if(head != null) {
      Stack<Node> stack = new Stack<>();
      stack.push(head);
      while(!stack.isEmpty()) {
        head = stack.pop();
        System.out.print(head.val + " ");
        if (head.right != null)
          stack.push(head.right);
        if (head.left != null)
          stack.push(head.left);
      }
    }
  }

2.中序遍歷

實(shí)現(xiàn)思路：

中序遍歷的順序：左孩子 -> 根結(jié)點(diǎn) -> 右孩子

借助棧結(jié)構(gòu)，將當(dāng)前結(jié)點(diǎn)的左孩子依次入棧直到?jīng)]有左孩子了就彈出棧頂元素并打印，如果彈出的結(jié)點(diǎn)有右孩子就將右孩子的左邊界依次入棧，循環(huán)…

比如文章開始的那個(gè)圖中，先將A，B，D依次入棧，此時(shí)棧頂元素是D，彈出并打印，D結(jié)點(diǎn)有右孩子，將D的右孩子的左邊界依次入棧，壓入結(jié)點(diǎn)G，結(jié)點(diǎn)G沒有左孩子所以彈出并打印G，此時(shí)棧頂元素是B，循環(huán)…直到棧中為空且當(dāng)前結(jié)點(diǎn)為空時(shí)遍歷結(jié)束。

代碼實(shí)現(xiàn)：

public static void inOrderTraverse(Node head) {
    System.out.println("in-order:");
    if(head != null) {
      Stack<Node> stack = new Stack<>();
      while(!stack.isEmpty() || head != null) {
        if(head != null) {
          // 當(dāng)前節(jié)點(diǎn)不為空, 將自己壓進(jìn)棧并將自己的左孩子作為當(dāng)前節(jié)點(diǎn)（壓入左邊界）
          stack.push(head);
          head = head.left;
        }else {
          // 當(dāng)前節(jié)點(diǎn)為空（沒有左孩子了）, 將棧頂元素彈出作為當(dāng)前節(jié)點(diǎn), 并將當(dāng)前節(jié)點(diǎn)的右孩子壓進(jìn)棧
          head = stack.pop();
          System.out.print(head.val + " ");
          head = head.right;
        }
      }
    }
  }

3.后序遍歷

實(shí)現(xiàn)思路：

后序遍歷的順序：左孩子 -> 右孩子 -> 根結(jié)點(diǎn)

仔細(xì)想一下，打印每個(gè)結(jié)點(diǎn)需要訪問根結(jié)點(diǎn)三次，先從根結(jié)點(diǎn)開始找到左孩子，返回再找到右孩子，再返回到根結(jié)點(diǎn)，需要訪問根結(jié)點(diǎn)三次，直接按照當(dāng)前順序進(jìn)行遍歷不知如何下手，那么我們可以換一個(gè)角度去考慮。

棧結(jié)構(gòu)是先進(jìn)后出的，那我們不妨借助一個(gè)棧先存儲(chǔ) 根結(jié)點(diǎn) -> 右孩子 -> 左孩子 的結(jié)果，再將其依次彈出就是后序遍歷的順序了。

那實(shí)現(xiàn) 根結(jié)點(diǎn) -> 右孩子 -> 左孩子 的方法就很簡(jiǎn)單了，回憶一下剛才說的前序遍歷的方式，前序遍歷是先要左孩子，就后壓入左孩子，反之，將前序遍歷的邏輯改寫為：彈出每個(gè)棧頂結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)并存儲(chǔ)到一個(gè)輔助棧中，如果當(dāng)前結(jié)點(diǎn)有左孩子就先壓入左孩子，如果有右孩子就后壓入右孩子，每次取棧頂彈出到輔助棧中。最后將得到的輔助棧中元素依次彈出得到的就是后序遍歷的結(jié)果。

代碼實(shí)現(xiàn)：

public static void posOrderTraverse(Node head) {
    System.out.println("pos-order");
    if(head != null) {
      Stack<Node> stack1 = new Stack<>();
      Stack<Node> stack2 = new Stack<>();   // 輔助棧，存儲(chǔ) 根 -> 右 -> 左 的結(jié)果
      stack1.push(head);
      while(!stack1.isEmpty()) {
        head = stack1.pop();
        stack2.push(head);
        // 有左孩子就先壓入左孩子
        if(head.left != null)
          stack1.push(head.left);
        // 有右孩子就后壓入右孩子
        if(head.right != null)
          stack1.push(head.right);
      }
      // 逆序打印 根 -> 右 -> 左 的結(jié)果，就是后序遍歷的結(jié)果
      while(!stack2.isEmpty())
        System.out.print(stack2.pop().val + " ");
    }
  }

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)創(chuàng)新互聯(lián)的支持。如果你想了解更多相關(guān)內(nèi)容請(qǐng)查看下面相關(guān)鏈接

文章名稱：Java語言實(shí)現(xiàn)非遞歸實(shí)現(xiàn)樹的前中后序遍歷總結(jié)
地址分享：http://chinadenli.net/article42/piooec.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、App開發(fā)、電子商務(wù)、網(wǎng)站改版、網(wǎng)站維護(hù)、ChatGPT

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)