二叉樹的非遞歸后序遍歷

BlackMass 發布于2019-08-21 17:08 / 3595人閱讀

摘要：后序遍歷概念后序遍歷指先遍歷節點的左子樹，再遍歷節點的右子樹，最后訪問節點，按照這種規則不重復地訪問樹中所有節點的過程。第一次在到達該節點時被使用，第二次在左子樹遍歷結束后被使用，第三次在右子樹遍歷結束后使用。

后序遍歷 概念

「后序遍歷」指先遍歷節點的左子樹，再遍歷節點的右子樹，最后訪問節點，按照這種規則不重復地訪問樹中所有節點的過程。

思路

樹的結構如下，以變量root保存

// 節點的數據結構
function Node(value) {
  this.value = value
  this.left = null
  this.right = null
}

root {
  value: "A",
  left: {
      value: "B",
      left: {
          value: "D",
          left: {
              value: "H",
              left: null,
              right: {
                  value: "K",
                  left: null,
                  right: null
              }
          },
          right: null
      },
      right: {
          value: "E",
          left: null,
          right: null
      }
  },
  right: {
      value: "C",
      left: {
          value: "F",
          left: {
              value: "I",
              left: null,
              right: null
          },
          right: null
      },
      right: {
          value: "G",
          left: null,
          right: {
              value: "J",
              left: null,
              right: null
          }
      }
  }
}

先遍歷節點的左子樹，再遍歷節點的右子樹，最后訪問節點。其中一個節點會被使用三次，第一次被用于遍歷其左子樹，第二次被用于遍歷其右子樹，第三次被用于訪問節點。第一次在到達該節點時被使用，第二次在左子樹遍歷結束后被使用，第三次在右子樹遍歷結束后使用。第一次到達該節點可以直接使用該節點，與此同時，需要將節點存入棧中，方便第二次、第三次使用。

代碼

const postOrderTraverse = root => {
  let current = root,
    stack = []
  while (current || stack.length !== 0) {
    if (current) {
      stack.push(current) // 存入棧中用于從節點去遍歷其右子樹
      stack.push(current) // 存入棧中用于訪問節點值
      current = current.left // 遍歷左子樹
    } else {
      current = stack.pop()
      if (current === stack[stack.length - 1]) { // 若棧頂節點和緊隨的節點一樣，說明是第二次使用該節點
        current = current ? current.right : null // 從節點去遍歷其右子樹
      } else { // 若棧頂節點和緊隨的節點一樣，說明是第三次使用該節點
        console.log(current.value) // 訪問節點值
        current = null // 使下一次循環進入current不存在的代碼片段中，好處理棧頂節點
        // current = stack.pop() 若寫成這樣，會進入current存在的代碼片段，棧頂節點會再次重復入棧
      }
    }
  }
}
postOrderTraverse(binaryTree.root)
// K H D E B I F J G C A

云服務器 GPU云服務器二叉樹的遍歷非遞歸二叉樹遍歷二叉樹的存儲二叉樹的存儲結構

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/89170.html

【從蛋殼到滿天飛】JAVA 數據結構解析和算法實現-二分搜索樹

摘要：在數據結構領域對應樹結構來說二叉樹是最常用的一種樹結構，二叉樹具有一個唯一的根節點，也就是最上面的節點。二叉樹每個節點最多有兩個孩子，一個孩子都沒有的節點通常稱之為葉子節點，二叉樹每個節點最多有一個父親，根節點是沒有父親節點的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...

ghnor 2019-08-23 16:19 評論0 收藏0
【從蛋殼到滿天飛】JAVA 數據結構解析和算法實現-二分搜索樹

摘要：在數據結構領域對應樹結構來說二叉樹是最常用的一種樹結構，二叉樹具有一個唯一的根節點，也就是最上面的節點。二叉樹每個節點最多有兩個孩子，一個孩子都沒有的節點通常稱之為葉子節點，二叉樹每個節點最多有一個父親，根節點是沒有父親節點的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...

FuisonDesign 2019-08-16 16:04 評論0 收藏0
二叉樹的遞歸遍歷（JS實現）

摘要：本文討論二叉樹的遍歷，對節點的訪問通過打印節點的值體現出來。從二叉樹的根節點出發，遍歷可分為三個環節訪問節點打印節點的值遍歷節點的左子樹遍歷節點的右子樹不同環節執行的先后順序產生了不同的遍歷方式。至于二叉樹的非遞歸遍歷，且聽下回分解。相關概念「樹的遍歷」指按照一定規則不重復地訪問樹中所有節點的過程。「訪問」指針對節點的操作，如打印節點的值，更新節點的值等。本文討論二叉樹的遍歷，...

ethernet 2019-08-21 17:07 評論0 收藏0
樹和樹的算法

摘要：樹和樹的算法一樹樹的概念樹英語是一種抽象數據類型或是實作這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。一種時間復雜度額外空間復雜度的二叉樹的遍歷方式，為二叉樹的節點個數。樹和樹的算法一、樹 1.1 樹的概念樹（英語：tree）是一種抽象數據類型（ADT）或是實作這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。它是由n（n>=1）個有限節點組成一個...

RaoMeng 2019-08-19 11:08 評論0 收藏0