JS中的二叉樹(shù)遍歷

ghnor 發(fā)布于2019-08-19 17:52 / 1694人閱讀

摘要：一個(gè)二叉樹(shù)的例子廣度優(yōu)先遍歷廣度優(yōu)先遍歷是從二叉樹(shù)的第一層根結(jié)點(diǎn)開(kāi)始，自上至下逐層遍歷在同一層中，按照從左到右的順序?qū)Y(jié)點(diǎn)逐一訪問(wèn)。有的書(shū)里將二叉樹(shù)的遍歷只講了上面三種遞歸遍歷。

二叉樹(shù)是由根節(jié)點(diǎn)，左子樹(shù)，右子樹(shù)組成，左子樹(shù)和友子樹(shù)分別是一個(gè)二叉樹(shù)。
這篇文章主要在JS中實(shí)現(xiàn)二叉樹(shù)的遍歷。

一個(gè)二叉樹(shù)的例子

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)先遍歷是從二叉樹(shù)的第一層（根結(jié)點(diǎn)）開(kāi)始，自上至下逐層遍歷；在同一層中，按照從左到右的順序?qū)Y(jié)點(diǎn)逐一訪問(wèn)。
實(shí)現(xiàn)：

使用數(shù)組模擬隊(duì)列。首先將根節(jié)點(diǎn)歸入隊(duì)列。當(dāng)隊(duì)列不為空的時(shí)候，執(zhí)行循環(huán)：取出隊(duì)列的一個(gè)節(jié)點(diǎn)，如果該結(jié)點(diǎn)的左子樹(shù)為非空，則將該結(jié)點(diǎn)的左子樹(shù)入隊(duì)列；如果該結(jié)點(diǎn)的右子樹(shù)為非空，則將該結(jié)點(diǎn)的右子樹(shù)入隊(duì)列。
（描述有點(diǎn)不清楚，直接看代碼吧。）

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

遞歸遍歷

覺(jué)得用這幾個(gè)字母表示遞歸遍歷的三種方法不錯(cuò)：
D：訪問(wèn)根結(jié)點(diǎn)，L：遍歷根結(jié)點(diǎn)的左子樹(shù)，R：遍歷根結(jié)點(diǎn)的右子樹(shù)。
先序遍歷：DLR
中序遍歷：LDR
后序遍歷：LRD
順著字母表示的意思念下來(lái)就是遍歷的順序了 ^ ^

這3種遍歷都屬于遞歸遍歷，或者說(shuō)深度優(yōu)先遍歷（Depth-First Search，DFS），因?yàn)樗?br>是優(yōu)先往深處訪問(wèn)。

先序遍歷的遞歸算法：

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

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

剛剛在廣度優(yōu)先遍歷中使用的是隊(duì)列，相應(yīng)的，在這種不遞歸的深度優(yōu)先遍歷中我們使用棧。在JS中還是使用一個(gè)數(shù)組來(lái)模擬它。
這里只說(shuō)先序的：
額，我嘗試了描述這個(gè)算法，然而并描述不清楚。按照代碼走一邊你就懂了。（認(rèn)真臉）

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

看了LK的這一篇，找到了非遞歸后序的算法（之前沒(méi)寫(xiě)就是因?yàn)檫@種實(shí)在不會(huì)啊啊啊），所以在這里把非遞歸的遍歷方法補(bǔ)充完整。
非遞歸中序
先把數(shù)的左節(jié)點(diǎn)推入棧，然后取出，再推右節(jié)點(diǎn)。（我能說(shuō)出的描述就如此了～～）

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

非遞歸后序(使用一個(gè)棧)
這里使用了一個(gè)臨時(shí)變量記錄上次入棧/出棧的節(jié)點(diǎn)。思路是先把根節(jié)點(diǎn)和左樹(shù)推入棧，然后取出左樹(shù)，再推入右樹(shù)，取出，最后取跟節(jié)點(diǎn)。

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

非遞歸后序(使用兩個(gè)棧)
這個(gè)算法的思路和上面那個(gè)差不多，s1有點(diǎn)像一個(gè)臨時(shí)變量。

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

這個(gè)方法即不用遞歸也不用棧實(shí)現(xiàn)三種深度遍歷，空間復(fù)雜度為O(1)（這個(gè)概念我也不是特別清楚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) {
  var tail = reverseEdge(head)
  var cur = tail
  while(cur) {
    console.log(cur.value)
    cur = cur.right
  }
  reverseEdge(tail)
}

var reverseEdge = function(head) {
  var pre = null,
      next = null
  while(head) {
    next = head.right
    head.right = pre
    pre = head
    head = next
  }
  return pre
}