棧、隊列、鏈表等數(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)。
- 有且僅有一個特定的稱為根（Root）的結(jié)點；
- 當(dāng)n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限集T1,T2,T3,...Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹（Subtree）。
二叉樹
二叉樹（Binary Tree）是另一種樹型結(jié)構(gòu)，它的特點是每個結(jié)點至多只有兩棵子樹（即二叉樹中不存在度大于2的結(jié)點），并且，二叉樹的子樹有左右之分（其次序不能任意顛倒。）
二叉樹的性質(zhì)
- 在二叉樹的第 i 層上至多有
個結(jié)點(i>=1)。
- 深度為k的二叉樹至多有
- 1 個結(jié)點，(k>=1)。
- 對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0 = n2 + 1。
- 一棵深度為k且有
- 深度為k的，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱之為完全二叉樹。
完全二叉樹的兩個特性
- 具有n個結(jié)點的完全二叉樹的深度為
+ 1。
- 如果對一棵有n個結(jié)點的完全二叉樹（其深度為
如果 i = 1，則結(jié)點 i 是二叉樹的根，無雙親；如果i > 1，則其雙親parent(i)是結(jié)點 Math.floor(i/2)。
如果 2i > n，則結(jié)點 i 無左孩子（結(jié)點i為葉子結(jié)點）；否則其左孩子LChild(i) 是結(jié)點 2i。
如果 2i + 1 > n，則結(jié)點 i 無右孩子；否則其右孩子 RChild(i) 是結(jié)點 2i + 1。
二叉樹的遍歷
遍歷二叉樹(Traversing Binary Tree)：是指按指定的規(guī)律對二叉樹中的每個結(jié)點訪問一次且僅訪問一次。
二叉樹有深度遍歷和廣度遍歷， 深度遍歷有前序、 中序和后序三種遍歷方法。二叉樹的前序遍歷可以用來顯示目錄結(jié)構(gòu)等；中序遍歷可以實現(xiàn)表達(dá)式樹，在編譯器底層很有用；后序遍歷可以用來實現(xiàn)計算目錄內(nèi)的文件及其信息等。
前序遍歷：訪問根–>遍歷左子樹–>遍歷右子樹。
中序遍歷：遍歷左子樹–>訪問根–>遍歷右子樹。
后序遍歷：遍歷左子樹–>遍歷右子樹–>訪問根。
廣度遍歷：按照層次一層層遍歷。
例如(a+b*c)-d/e，該表達(dá)式用二叉樹表示如圖：
js中的二叉樹
上述二叉樹(a+b*c)-d/e在js中可以用對象的形式表示出來：
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é)點，將值存入數(shù)組，然后遞歸遍歷：先左節(jié)點，將值存入數(shù)組，繼續(xù)向下遍歷，直到二叉樹為空，則遍歷結(jié)束；
- 然后再回溯遍歷右節(jié)點，將值存入數(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é)點放入棧中，然后再取出來，將值放入結(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() // 這其實樹或者節(jié)點
result.push(node.value) // 取到現(xiàn)在的節(jié)點的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"]
- 遞歸版本
先遞歸遍歷左子樹，從最左的一個左子樹存入數(shù)組；然后回溯遍歷雙親結(jié)點，再是右子樹，這樣遞歸循環(huán)。
let result = []
let dfs = function (node) {
if (node) {
dfs(node.left)
result.push(node.value)
dfs(node.right)
}
}
- 非遞歸遍歷
將當(dāng)前結(jié)點壓入棧，然后將左子樹當(dāng)做當(dāng)前結(jié)點，如果當(dāng)前結(jié)點為空，將雙親結(jié)點取出來，將值保存進(jìn)數(shù)組，然后將右子樹當(dāng)做當(dāng)前結(jié)點，進(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é)點時，將此結(jié)點的值放入數(shù)組中，然后回溯遍歷雙親結(jié)點的右結(jié)點，遞歸遍歷。
let result = []
function dfs (node) {
if(node) {
dfs(node.left)
dfs(node.right)
result.push(node.value)
}
}
-
非遞歸版本
- 初始化一個棧，將根節(jié)點壓入棧中，并標(biāo)記為當(dāng)前節(jié)點(node)；
- 當(dāng)棧為非空時，執(zhí)行步驟3，否則執(zhí)行結(jié)束；
- 如果當(dāng)前節(jié)點(node)有左子樹且沒有被 touched，則執(zhí)行4；如果當(dāng)前結(jié)點有右子樹，被 touched left 但沒有被 touched right 則執(zhí)行5 否則執(zhí)行6；
- 對當(dāng)前節(jié)點(node)標(biāo)記 touched left，將當(dāng)前節(jié)點的左子樹賦值給當(dāng)前節(jié)點(node=node.left) 并將當(dāng)前節(jié)點(node)壓入棧中，回到3；
- 對當(dāng)前節(jié)點(node)標(biāo)記 touched right，將當(dāng)前節(jié)點的右子樹賦值給當(dāng)前節(jié)點(node=node.right) 并將當(dāng)前節(jié)點(node)壓入棧中，回到3；
- 清理當(dāng)前節(jié)點(node)的 touched 標(biāo)記，彈出棧中的一個節(jié)點并訪問，然后再將棧頂節(jié)點標(biāo)記為當(dāng)前節(jié)點(item)，回到3。
function dfs(node) {
let result = []
let stack = []
stack.push(node)
while(stack.length) {
// 不能用node.touched !== 'left' 標(biāo)記‘left’做判斷，
// 因為回溯到該結(jié)點時，遍歷右子樹已經(jīng)完成，該結(jié)點標(biāo)記被更改為‘right’ 若用標(biāo)記‘left’判斷該if語句會一直生效導(dǎo)致死循環(huán)
if(node.left && !node.touched) { // 不要寫成if(node.left && node.touched !== 'left')
// 遍歷結(jié)點左子樹時，對該結(jié)點做 ‘left’標(biāo)記；為了子結(jié)點回溯到該（雙親）結(jié)點時，便不再訪問左子樹
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é)點無左右子樹時，從棧中取出一個結(jié)點，訪問(并清理標(biāo)記)
node.touched && delete node.touched // 可以不清理不影響結(jié)果 只是第二次對同一顆樹再執(zhí)行該后序遍歷方法時，結(jié)果就會出錯啦因為你對這棵樹做的標(biāo)記還留在這棵樹上
result.push(node.value)
node = stack.length ? stack[stack.length - 1] : null
//node = stack.pop() 這時當(dāng)前結(jié)點不再從棧中?。◤棾觯遣桓淖儣?shù)據(jù)直接訪問棧中最后一個結(jié)點
//如果這時當(dāng)前結(jié)點去棧中?。◤棾觯?dǎo)致回溯時當(dāng)該結(jié)點左右子樹都被標(biāo)記過時 當(dāng)前結(jié)點又變成從棧中取會漏掉對結(jié)點的訪問（存入結(jié)果數(shù)組中）
}
return result // 返回值
}
js中二叉樹的廣度遍歷
- 遞歸版本
廣度優(yōu)先遍歷二叉樹(層序遍歷)是用隊列來實現(xiàn)的，廣度遍歷是從二叉樹的根結(jié)點開始，自上而下逐層遍歷；在同一層中，按照從左到右的順序?qū)Y(jié)點逐一訪問。
// 廣度優(yōu)先遍歷
let result = []
let stack = [tree]
let count = 0
let bfs = function() {
let node = stack[count] // 當(dāng)前節(jié)點
result.push(node.value)
if(node.left) stack.push(node.left)
if(node.right) stack.push(node.right)
count++ // 取到下一個節(jié)點
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
}
