二叉樹由根結點、左子樹和右子樹組成,而左子樹與右子樹本身又是一棵二叉樹。本文主要講解如何在 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
順著字母念下來,就是遍歷的順序了 ^ ^。這三種都屬於遞歸遍歷,也稱深度優先遍歷(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 } } }
非遞歸後序(使用一個棧):這裡用一個臨時變量記錄上次入棧/出棧的結點。思路是先把根結點與左樹推入棧,取出左樹,再推入右樹並取出,最後取根結點。
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 } } }
非遞歸後序(使用兩個棧):這個算法思路與上一個相近,s1 有點像一個臨時變量。
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); } } }
Morris 遍歷:這種方法既不用遞歸也不用棧,就能實現三種深度遍歷,空間複雜度為 O(1)。(這三種算法我先放著,有空再研究。)
Morris 先序:
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 } }
Morris 中序:
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 } }
Morris 後序:
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) {
以上就是本文的全部內容,希望對大家的學習有所幫助。