二元樹是由根節點，左子樹，右子樹組成，左子樹和友子樹分別是二元樹。
這篇文章主要在JS實現二元樹的遍歷。
一個二元樹的例子
var tree = {
value: 1,
left: {
value: 2,
left: {
value: 4
}
},
right: {
value: 3,
left: {
value: 5,
left: {
value: 7
},
right: {
value: 8
}
},
right: {
value: 6
}
}
}廣度優先度優先遍歷是從二元樹的第一層（根結點）開始，自上至下逐層遍歷；在同一層中，按照從左到右的順序對結點逐一訪問。
實作：
使用陣列模擬佇列。首先將根節點歸入隊列。當佇列不為空的時候，執行循環：取出佇列的節點，如果該結點的左子樹為非空，則將該結點的左子樹入佇列；如果該結點的右子樹為非空，則將該結點的右子樹入佇列。
（描述有點不清楚，直接看代碼吧。）
var levelOrderTraversal = function(node) {
if(!node) {
throw new Error('Empty Tree')
}
var que = []
que.push(node)
while(que.length !== 0) {
node = que.shift()
console.log(node.value)
if(node.left) que.push(node.left)
if(node.right) que.push(node.right)
}
}覺得用這幾個字母>遞歸遍歷
覺得用這幾個字母表示遞歸遍歷的三種方法不錯：
D：訪問根結點，L：遍歷根結點的左子樹，R：遍歷根結點的右子樹。
先序遍歷：DLR
中序遍歷：LDR
後序遍歷：LRD
順著字母表示的意思下來就是遍歷的順序了^ ^
這3種遍歷都屬於遞歸遍歷，或者說深度優先遍歷（Depth-First Search，DFS），因為它總
是優先往深處訪問。
先序遍歷的遞歸算法：
var preOrder = function (node) {
if (node) {
console.log(node.value);
preOrder(node.left);
preOrder(node.right);
}
}中序遍歷的遞歸算法：
var inOrder = function (node) {
if (node) {
inOrder(node.left);
console.log(node.value);
inOrder(node.right);
}
}後序遍歷的遞迴演算法：
var postOrder = function (node) {
if (node) {
postOrder(node.left);
postOrder(node.right);
console.log(node.value);
}
}非遞歸深度優先遍歷
非遞歸深度優先遍歷
非遞歸深度優先遍歷
var preOrderUnRecur = function(node) {
if(!node) {
throw new Error('Empty Tree')
}
var stack = []
stack.push(node)
while(stack.length !== 0) {
node = stack.pop()
console.log(node.value)
if(node.right) stack.push(node.right)
if(node.left) stack.push(node.left)
}
}非遞歸深度優先遍歷
非遞歸深度優先遍歷
非遞歸深度優先遍歷
var inOrderUnRecur = function(node) {
if(!node) {
throw new Error('Empty Tree')
}
var stack = []
while(stack.length !== 0 || node) {
if(node) {
stack.push(node)
node = node.left
} else {
node = stack.pop()
console.log(node.value)
node = node.right
}
}
}不易這些概念誰是屬於誰的我也搞不太清楚。有的書裡將二元樹的遍歷只講了上面三種遞歸遍歷。有的分廣度優先遍歷和深度優先遍歷兩種，把遞歸遍歷都分入深度遍歷中;有的分遞歸遍歷和非遞歸遍歷兩種，非遞歸遍歷裡包括廣度優先遍歷中;有的分遞歸遍歷和非遞歸遍歷兩種，非遞歸遍歷裡包括廣度優先遍歷和下面這種遍歷。個人覺得怎麼分其實不重要，掌握方法和用途就好：）
剛剛在廣度優先遍歷中使用的是隊列，相應的，在這種不遞歸的深度優先遍歷中我們使用棧。在JS還是使用一個陣列來模擬它。這裡只說先序的：
額，我嘗試了描述這個演算法，然而並描述不清楚，按照程式碼走一邊你就懂了。var posOrderUnRecur = function(node) {
if(!node) {
throw new Error('Empty Tree')
}
var stack = []
stack.push(node)
var tmp = null
while(stack.length !== 0) {
tmp = stack[stack.length - 1]
if(tmp.left && node !== tmp.left && node !== tmp.right) {
stack.push(tmp.left)
} else if(tmp.right && node !== tmp.right) {
stack.push(tmp.right)
} else {
console.log(stack.pop().value)
node = tmp
}
}
}看了這篇，找到了非遞歸後序的演算法，所以在這裡把非遞歸的遍歷方法補充完整。
非遞歸中序
var posOrderUnRecur = function(node) {
if(node) {
var s1 = []
var s2 = []
s1.push(node)
while(s1.length !== 0) {
node = s1.pop()
s2.push(node)
if(node.left) {
s1.push(node.left)
}
if(node.right) {
s1.push(node.right)
}
}
while(s2.length !== 0) {
console.log(s2.pop().value);
}
}
}非遞歸後序(使用一個堆疊)
這裡使用了一個暫時變數記錄上次入棧/出棧的節點。想法是先把根節點和左樹推入棧，然後取出左樹，再推入右樹，取出，最後取跟節點。
var morrisPre = function(head) {
if(!head) {
return
}
var cur1 = head,
cur2 = null
while(cur1) {
cur2 = cur1.left
if(cur2) {
while(cur2.right && cur2.right != cur1) {
cur2 = cur2.right
}
if(!cur2.right) {
cur2.right = cur1
console.log(cur1.value)
cur1 = cur1.left
continue
} else {
cur2.right = null
}
} else {
console.log(cur1.value)
}
cur1 = cur1.right
}
}var morrisIn = function(head) {
if(!head) {
return
}
var cur1 = head,
cur2 = null
while(cur1) {
cur2 = cur1.left
if(cur2) {
while(cur2.right && cur2.right !== cur1) {
cur2 = cur2.right
}
if(!cur2.right) {
cur2.right = cur1
cur1 = cur1.left
continue
} else {
cur2.right = null
}
}
console.log(cur1.value)
cur1 = cur1.right
}
}var morrisPost = function(head) {
if(!head) {
return
}
var cur1 = head,
cur2 = null
while(cur1) {
cur2 = cur1.left
if(cur2) {
while(cur2.right && cur2.right !== cur1) {
cur2 = cur2.right
}
if(!cur2.right) {
cur2.right = cur1
cur1 = cur1.left
continue
} else {
cur2.right = null
printEdge(cur1.left)
}
}
cur1 = cur1.right
}
printEdge(head)
}
var printEdge = function(head) {這個方法即不用遞歸也不用棧實現三種深度遍歷，空間複雜度為O(1 )（這個概念我也不是特別清楚org）（這三種演算法我先放著，有空再研究）
Morris先序:Morris中序:Morris後序:本文的全部內容，希望對大家的學習有所幫助，更多相關教學請訪問JavaScript影片教學！
