這篇文章主要為大家詳細介紹了JS中的二叉樹遍歷，何為二叉樹，什么是二叉樹的遍歷，感興趣的小伙伴們可以參考一下

二叉樹是由根節(jié)點，左子樹，右子樹組成，左子樹和友子樹分別是一個二叉樹。

這篇文章主要在JS中實現(xiàn)二叉樹的遍歷。

一個二叉樹的例子

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

  }

 }

}

廣度優(yōu)先遍歷

廣度優(yōu)先遍歷是從二叉樹的第一層（根結(jié)點）開始，自上至下逐層遍歷；在同一層中，按照從左到右的順序?qū)Y(jié)點逐一訪問。

實現(xiàn)：

<!--more-->

使用數(shù)組模擬隊列。首先將根節(jié)點歸入隊列。當(dāng)隊列不為空的時候，執(zhí)行循環(huán)：取出隊列的一個節(jié)點，如果該結(jié)點的左子樹為非空，則將該結(jié)點的左子樹入隊列；如果該結(jié)點的右子樹為非空，則將該結(jié)點的右子樹入隊列。

（描述有點不清楚，直接看代碼吧。）

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：訪問根結(jié)點，L：遍歷根結(jié)點的左子樹，R：遍歷根結(jié)點的右子樹。

先序遍歷：DLR

中序遍歷：LDR

后序遍歷：LRD

順著字母表示的意思念下來就是遍歷的順序了 ^ ^

這3種遍歷都屬于遞歸遍歷，或者說深度優(yōu)先遍歷（Depth-First Search，DFS），因為它總

是優(yōu)先往深處訪問。

先序遍歷的遞歸算法：

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);

 }

}

非遞歸深度優(yōu)先遍歷

其實對于這些概念誰是屬于誰的我也搞不太清楚。有的書里將二叉樹的遍歷只講了上面三種遞歸遍歷。有的分廣度優(yōu)先遍歷和深度優(yōu)先遍歷兩種，把遞歸遍歷都分入深度遍歷當(dāng)中;有的分遞歸遍歷和非遞歸遍歷兩種，非遞歸遍歷里包括廣度優(yōu)先遍歷和下面這種遍歷。個人覺得怎么分其實并不重要，掌握方法和用途就好 ：）

剛剛在廣度優(yōu)先遍歷中使用的是隊列，相應(yīng)的，在這種不遞歸的深度優(yōu)先遍歷中我們使用棧。在JS中還是使用一個數(shù)組來模擬它。

這里只說先序的：

額，我嘗試了描述這個算法，然而并描述不清楚，按照代碼走一邊你就懂了。

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)

 }

}

看了這一篇，找到了非遞歸后序的算法，所以在這里把非遞歸的遍歷方法補充完整。

非遞歸中序

先把數(shù)的左節(jié)點推入棧，然后取出，再推右節(jié)點。

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

  }

 }

}

非遞歸后序(使用一個棧)

這里使用了一個臨時變量記錄上次入棧/出棧的節(jié)點。思路是先把根節(jié)點和左樹推入棧，然后取出左樹，再推入右樹，取出，最后取跟節(jié)點。

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遍歷

這個方法即不用遞歸也不用棧實現(xiàn)三種深度遍歷，空間復(fù)雜度為O(1)（這個概念我也不是特別清楚org）

（這三種算法我先放著，有空再研究）

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) { 

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助。