可視化講解深度優先周遊(DFT)

深度優先周遊, 刷過題的朋友應該都很熟悉了,難是不難,但是了解起來還是要費一些功夫的. 深度優先周遊的實作方法有遞歸和非遞歸兩種, 這裡我們用可視化的角度,講解前一種: 遞歸的深度優先周遊.

為什麼要以可視化的方式來講解呢? 因為人是視覺的動物, 如果和你說

二叉樹

或

棧

, 相信大家腦中出現的都是下面的圖形:

而不是下面的代碼:

// 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()

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

效果展示

為了可視化的講解

深度優先周遊算法

, 筆者寫了一個簡單的網頁, 實作的功能有:

使用者可編輯進行深度周遊的二叉樹
網頁上給出了 JavaScript 版本的實作
點選 Start DFT 按鈕, 使用者将看到算法中用到的二叉樹和棧都将動态的展示在頁面中,可以直覺的看到代碼運作過程中資料的變化

頁面目前還在繼續優化中，讓我們看看目前的效果：

可以看到，網頁模拟了深度搜尋時二叉樹和棧的動态變化過程：

二叉樹中目前周遊到的節點會變成紅色;
棧中壓入（push）的節點為灰色;
棧中彈出（pop) 的節點會變為紅色，然後消失;

其中頁面左上角為初始周遊的二叉樹資料，使用者可以修改二叉樹資料後再次啟動可視化深度優先周遊過程.

頁面左下角為深度優先周遊的 javascript 實作版本，作為參考.

深度優先周遊簡介

可視化分析之前，讓我們先來簡單看看實作深度優先搜尋的代碼：

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

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

首先我們建立了一個棧

const stack = [this.rootNode]

, 并将根節點放入棧中.

接下來是一個while語句, 跳出循環的條件是棧為空, 也就是代表我們周遊完了整棵樹.

在循環中, 我們先将棧頂的節點彈出, 并列印出來, 表示我們已經周遊過了該節點. 然後将該節點的所有子節點壓入棧中, 這就保障了我們下一個周遊到的點就是該節點的子節點. 重複該循環, 最後我們就可以看到, 二叉樹的每個節點都按照深度搜尋的順序被列印了出來:

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

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

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