可視化講解深度優(yōu)先遍歷(DFT)

打個小廣告：
如果你想獲取更多前端干貨、鵝廠工程師的前端面試指南，
歡迎關(guān)注我的個人微信公眾號：
前端夜談

深度優(yōu)先遍歷, 刷過題的朋友應該都很熟悉了,難是不難,但是理解起來還是要費一些功夫的. 深度優(yōu)先遍歷的實現(xiàn)方法有遞歸和非遞歸兩種, 這里我們用可視化的角度,講解前一種: 遞歸的深度優(yōu)先遍歷.

為什么要以可視化的方式來講解呢? 因為人是視覺的動物, 如果和你說 二叉樹 或 棧 , 相信大家腦中出現(xiàn)的都是下面的圖形:

binary tree

stack

而不是下面的代碼:

// binary tree
class Node {
  constructor(value, leftChild, rightChild) {
    this.value = value
    this.leftChild = leftChild
    this.rightChild = rightChild
  }
}

// stack
const stack = new Array()
stack.push(1)
var topItem = stack.pop()

所以說, 人是視覺動物, 以圖形可視化的方式來講解問題往往能講解的更清楚, 這也就是我寫本文的緣由.

效果展示

為了可視化的講解 深度優(yōu)先遍歷算法, 筆者寫了一個簡單的網(wǎng)頁, 實現(xiàn)的功能有:

用戶可編輯進行深度遍歷的二叉樹
網(wǎng)頁上給出了 JavaScript 版本的實現(xiàn)
點擊 Start DFT 按鈕, 用戶將看到算法中用到的 二叉樹 和棧都將動態(tài) 的展示在頁面中,可以直觀的看到代碼運行過程中數(shù)據(jù)的變化

頁面目前還在繼續(xù)優(yōu)化中攒岛，讓我們看看目前的效果：

在線demo:

https://ssthouse.github.io/visual-explain/#/list/dft

stack

可以看到，網(wǎng)頁模擬了深度搜索時二叉樹和棧的動態(tài)變化過程：

二叉樹中當前遍歷到的節(jié)點會變成紅色;
棧中壓入（push）的節(jié)點為灰色;
棧中彈出（pop) 的節(jié)點會變?yōu)?em>紅色炎疆，然后消失;

其中頁面左上角為初始遍歷的二叉樹數(shù)據(jù)考阱，用戶可以修改二叉樹數(shù)據(jù)后再次啟動可視化深度優(yōu)先遍歷過程.

頁面左下角為深度優(yōu)先遍歷的 javascript 實現(xiàn)版本，作為參考.

深度優(yōu)先遍歷簡介

可視化分析之前粘姜，讓我們先來簡單看看實現(xiàn)深度優(yōu)先搜索的代碼：

export class Dft {
  constructor(rootNode, stepCallback) {
    this.rootNode = rootNode
    this.stepCallback = stepCallback
  }

  start() {
    if (!this.rootNode || !this.stepCallback) {
      return
    }
    const stack = [this.rootNode]
    while (stack.length !== 0) {
      const curNode = stack.pop()
      console.log(`current node: ${curNode.value}`)
      curNode.childrenNodes.forEach(element => {
        stack.push(element)
      })
    }
  }
}

export class Node {
  constructor(value, childrenNodes = []) {
    this.value = value
    this.childrenNodes = childrenNodes
  }
}

代碼不長鬓照，讓我們一步步看.

首先我們創(chuàng)建了一個棧 const stack = [this.rootNode] , 并將根節(jié)點放入棧中.

接下來是一個while語句, 跳出循環(huán)的條件是 棧為空, 也就是代表我們遍歷完了整棵樹.

在循環(huán)中, 我們先將棧頂?shù)墓?jié)點彈出, 并打印出來, 表示我們已經(jīng)遍歷過了該節(jié)點. 然后將該節(jié)點的所有子節(jié)點壓入棧中, 這就保障了我們下一個遍歷到的點就是該節(jié)點的子節(jié)點. 重復該循環(huán), 最后我們就可以看到, 二叉樹的每個節(jié)點都按照深度搜索的順序被打印了出來:

current node: 1
current node: 4
current node: 7
current node: 6
current node: 2
current node: 5
current node: 3

如果是對棧的使用比較熟悉的同學, 可能看到這里就已經(jīng)明白原理了.

但是, 如果是對棧使用不是很熟悉的同學, 估計對代碼的執(zhí)行過程還是沒有一個直觀的認識, 那么讓我們以更直觀的方式看看這段代碼是怎么運行的.