棧、隊(duì)列、鏈表等數(shù)據(jù)結(jié)構(gòu)地回，都是順序數(shù)據(jù)結(jié)構(gòu)。而樹是非順序數(shù)據(jù)結(jié)構(gòu)官辽。樹型結(jié)構(gòu)是一類非常重要的非線性結(jié)構(gòu)。直觀地粟瞬，樹型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)構(gòu)同仆。
- 有且僅有一個(gè)特定的稱為根（Root）的結(jié)點(diǎn)；
- 當(dāng)n>1時(shí)裙品，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,T3,...Tm俗批，其中每一個(gè)集合本身又是一棵樹，并且稱為根的子樹（Subtree）市怎。
二叉樹
二叉樹（Binary Tree）是另一種樹型結(jié)構(gòu)岁忘，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹（即二叉樹中不存在度大于2的結(jié)點(diǎn)），并且区匠，二叉樹的子樹有左右之分（其次序不能任意顛倒干像。）
二叉樹的性質(zhì)
- 在二叉樹的第 i 層上至多有
個(gè)結(jié)點(diǎn)(i>=1)。
- 深度為k的二叉樹至多有
- 1 個(gè)結(jié)點(diǎn)辱志，(k>=1)蝠筑。
- 對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0揩懒，度為2的結(jié)點(diǎn)數(shù)為n2，則n0 = n2 + 1挽封。
- 一棵深度為k且有
- 深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹辅愿，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)智亮，稱之為完全二叉樹。
完全二叉樹的兩個(gè)特性
- 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為
+ 1点待。
- 如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹（其深度為
如果 i = 1癞埠，則結(jié)點(diǎn) i 是二叉樹的根状原，無雙親聋呢；如果i > 1，則其雙親parent(i)是結(jié)點(diǎn) Math.floor(i/2)颠区。
如果 2i > n削锰，則結(jié)點(diǎn) i 無左孩子（結(jié)點(diǎn)i為葉子結(jié)點(diǎn)）；否則其左孩子LChild(i) 是結(jié)點(diǎn) 2i毕莱。
如果 2i + 1 > n器贩，則結(jié)點(diǎn) i 無右孩子；否則其右孩子 RChild(i) 是結(jié)點(diǎn) 2i + 1朋截。
二叉樹的遍歷
遍歷二叉樹(Traversing Binary Tree)：是指按指定的規(guī)律對(duì)二叉樹中的每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次蛹稍。
二叉樹有深度遍歷和廣度遍歷， 深度遍歷有前序部服、 中序和后序三種遍歷方法稳摄。二叉樹的前序遍歷可以用來顯示目錄結(jié)構(gòu)等；中序遍歷可以實(shí)現(xiàn)表達(dá)式樹饲宿，在編譯器底層很有用厦酬；后序遍歷可以用來實(shí)現(xiàn)計(jì)算目錄內(nèi)的文件及其信息等。
前序遍歷：訪問根–>遍歷左子樹–>遍歷右子樹瘫想。
中序遍歷：遍歷左子樹–>訪問根–>遍歷右子樹仗阅。
后序遍歷：遍歷左子樹–>遍歷右子樹–>訪問根。
廣度遍歷：按照層次一層層遍歷国夜。
例如(a+b*c)-d/e减噪，該表達(dá)式用二叉樹表示如圖：
js中的二叉樹
上述二叉樹(a+b*c)-d/e在js中可以用對(duì)象的形式表示出來：
const tree = {
value: "-",
left: {
value: '+',
left: {
value: 'a',
},
right: {
value: '*',
left: {
value: 'b',
},
right: {
value: 'c',
}
}
},
right: {
value: '/',
left: {
value: 'd',
},
right: {
value: 'e',
}
}
}
先序遍歷： ["-", "+", "a", "*", "b", "c", "/", "d", "e"]
- 遞歸版本
- 先遍歷根節(jié)點(diǎn)，將值存入數(shù)組车吹，然后遞歸遍歷：先左節(jié)點(diǎn)筹裕，將值存入數(shù)組，繼續(xù)向下遍歷窄驹，直到二叉樹為空朝卒，則遍歷結(jié)束；
- 然后再回溯遍歷右節(jié)點(diǎn)乐埠，將值存入數(shù)組抗斤，這樣遞歸循環(huán)，直到子樹為空丈咐，則遍歷結(jié)束瑞眼。
let result = []
let dfs = function (node) {
if (node) {
result.push(node.value)
dfs(node.left)
dfs(node.right)
}
return result
}
console.log(dfs(tree))
- 非遞歸版本
- 先序非遞歸遍歷是利用了棧，將根結(jié)點(diǎn)放入棧中棵逊，然后再取出來伤疙，將值放入結(jié)果數(shù)組；
- 然后如果存在右子樹辆影，將右子樹壓入棧徒像；
- 如果存在左子樹黍特，將左子樹壓入棧；
- 然后循環(huán)判斷棧是否為空厨姚，重復(fù)上述步驟衅澈。
let dfs = function (nodes) {
let result = []
let stack = []
stack.push(nodes)
while (stack.length) { // 等同于 while(stack.length !== 0) 直到棧中的數(shù)據(jù)為空
let node = stack.pop() // 這其實(shí)樹或者節(jié)點(diǎn)
result.push(node.value) // 取到現(xiàn)在的節(jié)點(diǎn)的value值
if (node.right) stack.push(node.right) // 先壓入右子樹
if (node.left) stack.push(node.left) // 后壓入左子樹，這樣push()先出
}
return result
}
console.log(dfs(tree)) // ["-", "+", "a", "*", "b", "c", "/", "d", "e"]
中序遍歷：["a", "+", "b", "*", "c", "-", "d", "/", "e"]
- 遞歸版本
先遞歸遍歷左子樹谬墙，從最左的一個(gè)左子樹存入數(shù)組今布；然后回溯遍歷雙親結(jié)點(diǎn)，再是右子樹拭抬，這樣遞歸循環(huán)部默。
let result = []
let dfs = function (node) {
if (node) {
dfs(node.left)
result.push(node.value)
dfs(node.right)
}
}
- 非遞歸遍歷
將當(dāng)前結(jié)點(diǎn)壓入棧，然后將左子樹當(dāng)做當(dāng)前結(jié)點(diǎn)造虎，如果當(dāng)前結(jié)點(diǎn)為空傅蹂，將雙親結(jié)點(diǎn)取出來，將值保存進(jìn)數(shù)組算凿，然后將右子樹當(dāng)做當(dāng)前結(jié)點(diǎn)份蝴，進(jìn)行循環(huán)。
let dfs = function (node) {
let result = []
let stack = []
while (stack.length || node) {
if(node) {
stack.push(node)
node = node.left
} else {
node = stack.pop()
result.push(node.value)
node = node.right
}
}
return result
}
console.log(dfs(tree))
后序遍歷：["a", "b", "c", "*", "+", "d", "e", "/", "-"]
- 遞歸遍歷
先走左子樹氓轰，當(dāng)左子樹沒有孩子結(jié)點(diǎn)時(shí)婚夫，將此結(jié)點(diǎn)的值放入數(shù)組中，然后回溯遍歷雙親結(jié)點(diǎn)的右結(jié)點(diǎn)署鸡，遞歸遍歷案糙。
let result = []
function dfs (node) {
if(node) {
dfs(node.left)
dfs(node.right)
result.push(node.value)
}
}
-
非遞歸版本
- 初始化一個(gè)棧，將根節(jié)點(diǎn)壓入棧中靴庆，并標(biāo)記為當(dāng)前節(jié)點(diǎn)(node)时捌；
- 當(dāng)棧為非空時(shí)，執(zhí)行步驟3炉抒，否則執(zhí)行結(jié)束奢讨；
- 如果當(dāng)前節(jié)點(diǎn)(node)有左子樹且沒有被 touched，則執(zhí)行4端礼；如果當(dāng)前結(jié)點(diǎn)有右子樹禽笑，被 touched left 但沒有被 touched right 則執(zhí)行5 否則執(zhí)行6；
- 對(duì)當(dāng)前節(jié)點(diǎn)(node)標(biāo)記 touched left蛤奥，將當(dāng)前節(jié)點(diǎn)的左子樹賦值給當(dāng)前節(jié)點(diǎn)(node=node.left) 并將當(dāng)前節(jié)點(diǎn)(node)壓入棧中，回到3僚稿；
- 對(duì)當(dāng)前節(jié)點(diǎn)(node)標(biāo)記 touched right凡桥，將當(dāng)前節(jié)點(diǎn)的右子樹賦值給當(dāng)前節(jié)點(diǎn)(node=node.right) 并將當(dāng)前節(jié)點(diǎn)(node)壓入棧中，回到3蚀同；
- 清理當(dāng)前節(jié)點(diǎn)(node)的 touched 標(biāo)記缅刽，彈出棧中的一個(gè)節(jié)點(diǎn)并訪問啊掏，然后再將棧頂節(jié)點(diǎn)標(biāo)記為當(dāng)前節(jié)點(diǎn)(item)，回到3衰猛。
function dfs(node) {
let result = []
let stack = []
stack.push(node)
while(stack.length) {
// 不能用node.touched !== 'left' 標(biāo)記‘left’做判斷迟蜜，
// 因?yàn)榛厮莸皆摻Y(jié)點(diǎn)時(shí)，遍歷右子樹已經(jīng)完成啡省，該結(jié)點(diǎn)標(biāo)記被更改為‘right’ 若用標(biāo)記‘left’判斷該if語句會(huì)一直生效導(dǎo)致死循環(huán)
if(node.left && !node.touched) { // 不要寫成if(node.left && node.touched !== 'left')
// 遍歷結(jié)點(diǎn)左子樹時(shí)娜睛，對(duì)該結(jié)點(diǎn)做 ‘left’標(biāo)記；為了子結(jié)點(diǎn)回溯到該（雙親）結(jié)點(diǎn)時(shí)卦睹，便不再訪問左子樹
node.touched = 'left'
node = node.left
stack.push(node)
continue
}
if(node.right && node.touched !== 'right') { // 右子樹同上
node.touched = 'right'
node = node.right
stack.push(node)
continue
}
node = stack.pop() // 該結(jié)點(diǎn)無左右子樹時(shí)畦戒，從棧中取出一個(gè)結(jié)點(diǎn)，訪問(并清理標(biāo)記)
node.touched && delete node.touched // 可以不清理不影響結(jié)果 只是第二次對(duì)同一顆樹再執(zhí)行該后序遍歷方法時(shí)结序，結(jié)果就會(huì)出錯(cuò)啦因?yàn)槟銓?duì)這棵樹做的標(biāo)記還留在這棵樹上
result.push(node.value)
node = stack.length ? stack[stack.length - 1] : null
//node = stack.pop() 這時(shí)當(dāng)前結(jié)點(diǎn)不再從棧中日险（彈出），而是不改變棧數(shù)據(jù)直接訪問棧中最后一個(gè)結(jié)點(diǎn)
//如果這時(shí)當(dāng)前結(jié)點(diǎn)去棧中刃旌住（彈出）會(huì)導(dǎo)致回溯時(shí)當(dāng)該結(jié)點(diǎn)左右子樹都被標(biāo)記過時(shí) 當(dāng)前結(jié)點(diǎn)又變成從棧中取會(huì)漏掉對(duì)結(jié)點(diǎn)的訪問（存入結(jié)果數(shù)組中）
}
return result // 返回值
}
js中二叉樹的廣度遍歷
- 遞歸版本
廣度優(yōu)先遍歷二叉樹(層序遍歷)是用隊(duì)列來實(shí)現(xiàn)的垃环，廣度遍歷是從二叉樹的根結(jié)點(diǎn)開始，自上而下逐層遍歷返敬；在同一層中遂庄，按照從左到右的順序?qū)Y(jié)點(diǎn)逐一訪問。
// 廣度優(yōu)先遍歷
let result = []
let stack = [tree]
let count = 0
let bfs = function() {
let node = stack[count] // 當(dāng)前節(jié)點(diǎn)
result.push(node.value)
if(node.left) stack.push(node.left)
if(node.right) stack.push(node.right)
count++ // 取到下一個(gè)節(jié)點(diǎn)
bfs()
}
- 非遞歸版本
function bfs(node) {
let result = []
let queue = []
queue.push(node)
let pointer = 0
while (pointer < queue.length) {
let node = queue[pointer++]
result.push(node.value)
if(node.left) queue.push(node.left)
if(node.right) queue.push(node.right)
}
return result
}
參考文章
js 中二叉樹的深度遍歷與廣度遍歷(遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn))
二叉樹與JavaScript
