資訊專欄INFORMATION COLUMN
摘要：后序遍歷概念后序遍歷指先遍歷節(jié)點的左子樹，再遍歷節(jié)點的右子樹，最后訪問節(jié)點，按照這種規(guī)則不重復(fù)地訪問樹中所有節(jié)點的過程。第一次在到達該節(jié)點時被使用，第二次在左子樹遍歷結(jié)束后被使用，第三次在右子樹遍歷結(jié)束后使用。
后序遍歷 概念
「后序遍歷」指先遍歷節(jié)點的左子樹，再遍歷節(jié)點的右子樹，最后訪問節(jié)點，按照這種規(guī)則不重復(fù)地訪問樹中所有節(jié)點的過程。
思路樹的結(jié)構(gòu)如下，以變量root保存
// 節(jié)點的數(shù)據(jù)結(jié)構(gòu)
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
}
}
}
}
先遍歷節(jié)點的左子樹，再遍歷節(jié)點的右子樹，最后訪問節(jié)點。其中一個節(jié)點會被使用三次，第一次被用于遍歷其左子樹，第二次被用于遍歷其右子樹，第三次被用于訪問節(jié)點。第一次在到達該節(jié)點時被使用，第二次在左子樹遍歷結(jié)束后被使用，第三次在右子樹遍歷結(jié)束后使用。第一次到達該節(jié)點可以直接使用該節(jié)點，與此同時，需要將節(jié)點存入棧中，方便第二次、第三次使用。
代碼const postOrderTraverse = root => {
let current = root,
stack = []
while (current || stack.length !== 0) {
if (current) {
stack.push(current) // 存入棧中用于從節(jié)點去遍歷其右子樹
stack.push(current) // 存入棧中用于訪問節(jié)點值
current = current.left // 遍歷左子樹
} else {
current = stack.pop()
if (current === stack[stack.length - 1]) { // 若棧頂節(jié)點和緊隨的節(jié)點一樣，說明是第二次使用該節(jié)點
current = current ? current.right : null // 從節(jié)點去遍歷其右子樹
} else { // 若棧頂節(jié)點和緊隨的節(jié)點一樣，說明是第三次使用該節(jié)點
console.log(current.value) // 訪問節(jié)點值
current = null // 使下一次循環(huán)進入current不存在的代碼片段中，好處理棧頂節(jié)點
// current = stack.pop() 若寫成這樣，會進入current存在的代碼片段，棧頂節(jié)點會再次重復(fù)入棧
}
}
}
}
postOrderTraverse(binaryTree.root)
// K H D E B I F J G C A
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/89170.html
摘要：在數(shù)據(jù)結(jié)構(gòu)領(lǐng)域?qū)?yīng)樹結(jié)構(gòu)來說二叉樹是最常用的一種樹結(jié)構(gòu)，二叉樹具有一個唯一的根節(jié)點，也就是最上面的節(jié)點。二叉樹每個節(jié)點最多有兩個孩子，一個孩子都沒有的節(jié)點通常稱之為葉子節(jié)點，二叉樹每個節(jié)點最多有一個父親，根節(jié)點是沒有父親節(jié)點的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...
摘要：在數(shù)據(jù)結(jié)構(gòu)領(lǐng)域?qū)?yīng)樹結(jié)構(gòu)來說二叉樹是最常用的一種樹結(jié)構(gòu)，二叉樹具有一個唯一的根節(jié)點，也就是最上面的節(jié)點。二叉樹每個節(jié)點最多有兩個孩子，一個孩子都沒有的節(jié)點通常稱之為葉子節(jié)點，二叉樹每個節(jié)點最多有一個父親，根節(jié)點是沒有父親節(jié)點的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...
摘要：本文討論二叉樹的遍歷，對節(jié)點的訪問通過打印節(jié)點的值體現(xiàn)出來。從二叉樹的根節(jié)點出發(fā)，遍歷可分為三個環(huán)節(jié)訪問節(jié)點打印節(jié)點的值遍歷節(jié)點的左子樹遍歷節(jié)點的右子樹不同環(huán)節(jié)執(zhí)行的先后順序產(chǎn)生了不同的遍歷方式。至于二叉樹的非遞歸遍歷，且聽下回分解。 相關(guān)概念 「樹的遍歷」 指按照一定規(guī)則不重復(fù)地訪問樹中所有節(jié)點的過程。「訪問」指針對節(jié)點的操作，如打印節(jié)點的值，更新節(jié)點的值等。 本文討論二叉樹的遍歷，...
摘要：樹和樹的算法一樹樹的概念樹英語是一種抽象數(shù)據(jù)類型或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時間復(fù)雜度額外空間復(fù)雜度的二叉樹的遍歷方式，為二叉樹的節(jié)點個數(shù)。 樹和樹的算法 一、樹 1.1 樹的概念 樹（英語：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>=1）個有限節(jié)點組成一個...
閱讀 3526·2023-04-25 17:35
閱讀 2599·2021-11-24 09:39
閱讀 2538·2021-10-18 13:32
閱讀 3424·2021-10-11 10:58
閱讀 1643·2021-09-26 09:55
閱讀 6177·2021-09-22 15:47
閱讀 972·2021-08-26 14:15
閱讀 3477·2019-08-30 15:55
