二叉樹的周遊是指不重複地通路二叉樹中所有結點，主要指非空二叉樹，對于空二叉樹則結束傳回。
二叉樹的周遊分為
- 深度優先周遊
- 先序周遊：根節點->左子樹->右子樹（根左右），有的叫：前序周遊
- 中序周遊：左子樹->根節點->右子樹（左根右）
- 後序周遊：左子樹->右子樹->根節點（左右根）
- 廣度優先周遊
- 層次周遊：
二叉樹-深度的優先周遊-圖解
深度優先，前、中、後周遊順序，就是組合[根左右]，移動根的位置，根左右、左根右、左右根，但是我即使代碼會寫了，還是搞不明白這個根左右與周遊的關系毛線頭在哪裡，特别是中序周遊的左根右，
部落客YuXi_0520的圖解，應該是我看過最易懂的。這裡盜圖貼一下
先序周遊（DLR）
先序周遊可以想象成，小人從樹根開始繞着整棵樹的外圍轉一圈，經過結點的順序就是先序周遊的順序
讓我們來看下動畫，和小人兒一起跑兩遍就記住啦，記住是繞着外圍跑哦
先序周遊結果：ABDHIEJCFKG
二叉樹先序周遊-js代碼實作
遞歸實作—二叉樹先序周遊
根 - 左 - 右遞歸
判斷根結點是否為空，為空則傳回null；否則取結點的值，然後去左、右結點的值
/**
* @description 前序周遊 =>1.通路根節點； 2.通路左子樹； 3.通路右子樹
* @param node {Node} 周遊的樹
*/
preOrderTraverse (node = this.tree) {
// 數組存儲數周遊值
let backs = []
// 遞歸，
function tempFunction (node) {
if (node.data !== null) {
// 先取根結點
backs.push(node.data)
// 如果存在左結點，取左節點的值
node.leftChild && tempFunction(node.leftChild)
// 如果存在右結點，取右結點值
node.rightChild && tempFunction(node.rightChild)
}
}
tempFunction(node)
return backs
} 非遞歸-二叉樹先序周遊
取結點的值，然後将左、右結點壓如棧
preOrderTraverse2 (node = this.tree) {
let backs = []
if (!node) {
return backs
}
let queue = [node]
while (queue.length) {
// 取出最後一個結點，對這個結點進行周遊
let root = queue.pop()
backs.push(root.data)
// 因為queue.pop，是以先存入右結點
root.rightChild && queue.push(root.rightChild)
root.leftChild && queue.push(root.leftChild)
}
return backs
} 下面代碼應該更容易了解
如果結點存在左結點，取值，然後存入棧中，直至沒有左結點是葉子，再取右邊
preOrderTraverse3 (node = this.tree) {
let backs = []
if (!node) {
return backs
}
let currentNode = node
let queue = [node]
while (queue.length) {
if(currentNode){
backs.push(currentNode.data)
queue.push(currentNode)
currentNode=currentNode.leftChild
}else {
currentNode = queue.pop()
currentNode = currentNode.rightChild
}
}
return backs
} 中序周遊（LDR）
中序周遊可以想象成，按樹畫好的左右位置投影下來就可以了
下面看下投影的過程動畫，其實就是按左右順序寫下來就行了
中序周遊結果：HDIBEJAFKCG
二叉樹中序周遊-JavaScript代碼實作
遞歸實作-二叉樹中序周遊
/**
* @description 中周遊 =>左右根
* @param node {Node} 周遊的樹
*/
inOrderTraverse (node = this.tree) {
// 數組存儲數周遊值
let backs = []
// 遞歸，
function tempFunction (node) {
if (node.data !== null) {
// 如果存在左結點，取左節點的值
node.leftChild && tempFunction(node.leftChild)
// 取根結點
backs.push(node.data)
// 如果存在右結點，取右結點值
node.rightChild && tempFunction(node.rightChild)
}
}
tempFunction(node)
return backs
} 非遞歸實作-二叉樹中序周遊
inOrderTraverse2(node){
let backs = []
if(!node){
return backs
}
let stack = [node]
let currentNode = node
while(stack.length){
if(currentNode){
stack.push(currentNode)
currentNode = currentNode.leftChild
}else {
currentNode = stack.pop()
backs.push(currentNode.data)
currentNode = currentNode.rightChild
}
}
} 後序周遊（LRD）
後序周遊就像是剪葡萄，我們要把一串葡萄剪成一顆一顆的（從左到右，剪最底下的葉子結點）。
就是圍着樹的外圍繞一圈，如果發現一剪刀就能剪下的葡萄（必須是一顆葡萄），就把它剪下來，組成的就是後序周遊了。
跟之前先序周遊繞圈的路線是一樣的(先序周遊，是遇到結點，就push到數組），但是後續周遊是：遞歸：先取左葉結點（沒有就跳過），再取右葉子結點
後序周遊結果：HIDJEBKFGCA
二叉樹後續周遊-JavaScript代碼實作
遞歸實作—二叉樹後續周遊
/**
* @description 後序周遊 =>左根右
* 1.通路左子樹。（先通路左子樹中的左子樹，再通路左子樹中的右子樹）
* 2.通路右子樹。（先通路右子樹中的左子樹，再通路右子樹中的右子樹）
* 3.通路根
* @param node {Node} 周遊的樹
*/
postOrderTraverse (node) {
// 數組存儲數周遊值
let backs = []
// 遞歸，
function tempFunction (node) {
if (node.data !== null) {
// 如果存在左結點，取左節點的值
node.leftChild && tempFunction(node.leftChild)
// 如果存在右結點，取右結點值
node.rightChild && tempFunction(node.rightChild)
// 最後取根結點
backs.push(node.data)
}
}
tempFunction(node)
return backs
} 非遞歸實作—二叉樹後續周遊
postOrderTraverse2 (node){
let backs = []
if(!node){
return backs
}
let stack = [node]
while(stack.length){
let currentNode = stack.pop()
backs.push(currentNode.data)
currentNode.leftChild&&stack.push(currentNode.leftChild)
currentNode.rightChild&&stack.push(currentNode.rightChild)
}
return backs
} 非遞歸實作2—二叉樹後續周遊
postOrderTraverse2 (node) {
let backs = []
if (!node) {
return backs
}
let stack = []
let currentNode = node
while (stack.length||currentNode) {
if (currentNode) {
stack.push(currentNode)
backs .unshift(currentNode.data)
currentNode = currentNode.rightChild
} else {
let temp = stack.pop()
currentNode = temp.leftChild
}
}
return backs
} 非遞歸實作3—二叉樹後續周遊
postOrderTraverse3 (node) {
let backs = []
if (!node) {
return backs
}
let stack = [node]
while (stack.length) {
let currentNode = stack.pop()
backs.unshift(currentNode.data)
currentNode.leftChild && stack.push(currentNode.leftChild)
currentNode.rightChild && stack.push(currentNode.rightChild)
}
return backs
} 非遞歸實作4—二叉樹後續周遊
postOrderTraverse4 (node) {
let backs = []
if (!node) {
return backs
}
let stack = [node]
let currentNode = node
let visitedNode = null
while (stack.length) {
if (currentNode) {
stack.push(currentNode)
currentNode = currentNode.leftChild
} else {
currentNode = stack[stack.length - 1]
if (currentNode.rightChild && currentNode.rightChild !== visitedNode) {
currentNode = currentNode.rightChild
} else {
backs.push(currentNode.data)
visitedNode = currentNode
stack.pop()
currentNode = null
}
}
}
return backs
} 二叉樹-廣度優先周遊-圖解
這個隻有層序周遊
層序周遊
層序周遊太簡單了，就是按照一層一層的順序，從左到右寫下來就行了。
層序周遊結果：ABCDEFGHIJK
二叉序層序周遊-JavaScript代碼實作
/**
* @description 中周遊 =>左右根
* @param node {Node} 周遊的樹
*/
inOrderTraverse (node = this.tree) {
// 數組存儲數周遊值
let backs = []
// 遞歸，
function tempFunction (node) {
if (node.data !== null) {
// 如果存在左結點，取左節點的值
node.leftChild && tempFunction(node.leftChild)
// 取根結點
backs.push(node.data)
// 如果存在右結點，取右結點值
node.rightChild && tempFunction(node.rightChild)
}
}
tempFunction(node)
return backs
} 不知道通過這種方式，有沒有覺得閉着眼睛都能寫出前序、中序、後序 、層序了呀，不過這隻是為了大家好了解，我想出的一種形象思維，為了用代碼實作，我們還需要具體了解一下前序、中序、後序周遊。
真正了解三種周遊
還記得我們先序和後序周遊時候跑的順序麼？按照這個順序再跑一次，就是圍着樹的外圍跑一整圈。
讓我們來了解一下繞着外圍跑一整圈的真正含義是：周遊所有結點時，都先往左孩子走，再往右孩子走。
觀察一下，你有什麼發現？
有沒有發現，除了根結點和空結點，其他所有結點都有三個箭頭指向它。
- 一個是從它的父節點指向它，
- 一個是從它的左孩子指向它
- 一個是從它的右孩子指向它。
一個結點有三個箭頭指向它，說明每個結點都被經過了三遍。
- 一遍是從它的父節點來的時候，
- 一遍是從它的左孩子傳回時，
- 一遍是從它的右孩子傳回時。
其實我們在用遞歸算法實作二叉樹的周遊的時候，不管是先序中序還是後序，程式都是按照上面那個順序跑遍所有結點的。
先序中序和後序唯一的不同就是，在經過結點的三次中，哪次通路（輸出或者列印或者做其他操作）了這個結點。有點像大禹治水三過家門，他會選擇一次進去。
- 先序周遊顧名思義，就是在第一次經過這個結點的時候通路了它。就是從父節點來的這個箭頭的時候，通路了它。
- 中序周遊也和名字一樣，就是在第二次經過這個結點的時候通路了它。就是從左孩子傳回的這個箭頭的時候，通路了它。
- 後序周遊，就是在第三次經過這個結點的時候通路了它。就是從右孩子傳回的這個箭頭的時候，通路了它。
怎麼樣，這樣有沒有很好的了解？
其實不管是前序中序還是後序，在程式裡跑的時候都是按照同樣的順序跑的，每個結點經過三遍，第幾遍通路這個結點了，就叫什麼序周遊。
當我們腦子裡有這個概念的時候， 再去看實作代碼就很好了解了，下一篇博文我會貼出和講解具體的實作代碼。
如果遞歸分治來了解前、中、後周遊與根左右、左根右、左右根的關系，就是按照那個跑路圖，對每個最底層的子結點[前、中、後]對應[根左右、左根右、左右根]順序來處理。
二叉樹前序、中序、後序周遊互相求法
已知二叉樹的廣度優先周遊-層序周遊數組，是可以完全還原二叉樹結構，但是
已知二叉樹前序、中序、後序中的一種排序數組，是無法求出二叉樹結構的。但是知道前序、中序、後序中的中序和前序或後序數組兩種也可以還原二叉樹，為何可以推出二叉樹的資料結構。
前序根結點在最前，後續根結點在最後，如果已知前序或者後續，則中序中根結點兩邊的元素分布為根結點的左邊結點和右邊結點元素。具體操作如下：
已知前序、中序周遊，求後序周遊
- 前序周遊=ABGDECFH
- 中序周遊=GBEDAFCH
建構二叉樹步驟：
- 根據前序周遊的特點，我們知道根結點root為A；
- 觀察中序周遊GBEDAFCH。其中root節點A的左側GBED必然是root的左子樹，右側FCH必然是root的右子樹。同時，這個也分别是左子樹和右子樹的中序周遊的序列；
- 在前序周遊周遊完根節點後，接着執行前序周遊左子樹，注意，是前序周遊，什麼意思？就是把左子樹當成一棵獨立的樹，執行前序周遊，同樣先通路左子樹的根，第2步我們已經知道左子樹是BGDE（前序周遊序列）了，由此可以得到，左子樹的根是B，那麼在這一步得到左子樹的根是B；
- 從第2步得到的中序周遊的節點序列中，找到B，發現B左邊隻有一個G，說明B的左子樹隻有一個葉子節點，B的右邊呢？我們可以得到B的右子樹有ED，再看前序周遊的序列，發現D在前，也就是說，D是先前序周遊通路的，則得到E是D的左子樹，隻有一個葉子節點。到這裡，我們可以得到這棵樹的根結點和左子樹的結構了，如下圖一
- 接着看右子樹，在第2步的時候已經知道右子樹是FCH這三個節點，那麼先看前序周遊的序列，先出現的是C，那麼C就是右子樹的根結點，看右子樹的中序周遊為FCH，是以F和H就分别是它的左子樹和右子樹，是以，右子樹的結構就出來了，如下圖二
已知中序、後序周遊，求前序周遊
- 中序周遊：GBEDAFCH
- 後序周遊：GEDBFHCA
同理，步驟和上面的類似，還是得先找出根結點，由後序周遊的特點，根結點root在最後，是以根結點為A，再由中序周遊可以知道左子樹和右子樹分别為GBED、FCH；再按照上面的步驟遞歸分别求出左右子樹即可得解。
已知前序、後序周遊，求中序周遊
已知前序、中序或者中序、後序都可以唯一确定一棵二叉樹，但是已知前序、後序是無法唯一确定一棵二叉樹的，解不唯一。
關于算法相關的詳細代碼，檢視https://github.com/zhoulujun/algorithm
參考文章：
了解二叉樹的三種周遊--前序、中序、後序 +層序（簡明易懂）https://blog.csdn.net/weixin_44032878/article/details/88070556
js資料結構-二叉樹（二叉堆） https://segmentfault.com/a/1190000017761929 （推薦閱讀-了解堆排序-堆化操作）
二叉樹前序、中序、後序周遊互相求法 https://blog.csdn.net/qq_34154570/article/details/82700094
JavaScript 二叉樹周遊專題：算法描述與實作 https://zhuanlan.zhihu.com/p/27307626
JS - 二叉樹算法實作與周遊 (更新中...) https://www.cnblogs.com/padding1015/p/7729988.html
二叉樹的周遊（前序、中序、後序、已知前中序求後序、已知中後序求前序） https://www.cnblogs.com/lanhaicode/p/10390147.html