DIV CSS 佈局教程網

二叉樹是由根節點，左子樹，右子樹組成，左子樹和友子樹分別是一個二叉樹。
這篇文章主要在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
  }
 }
}

廣度優先遍歷
廣度優先遍歷是從二叉樹的第一層（根結點）開始，自上至下逐層遍歷；在同一層中，按照從左到右的順序對結點逐一訪問。
實現：
<!--more-->
使用數組模擬隊列。首先將根節點歸入隊列。當隊列不為空的時候，執行循環：取出隊列的一個節點，如果該結點的左子樹為非空，則將該結點的左子樹入隊列；如果該結點的右子樹為非空，則將該結點的右子樹入隊列。
（描述有點不清楚，直接看代碼吧。）

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

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

剛剛在廣度優先遍歷中使用的是隊列，相應的，在這種不遞歸的深度優先遍歷中我們使用棧。在JS中還是使用一個數組來模擬它。
這裡只說先序的：
額，我嘗試了描述這個算法，然而並描述不清楚，按照代碼走一邊你就懂了。

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)（這個概念我也不是特別清楚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) { 

以上就是本文的全部內容，希望對大家的學習有所幫助。