iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 24
0
Software Development

One Punch 一拳搞定前後端面試系列 第 24

[One Punch 一拳搞定前後端面試] DAY-24 -Tree Depth First Traversal

Tree Depth First Traversal

上篇用了 Breadth First 方法來遍歷(Traversal)整個 Tree,本篇就來用 Depth First 方法

本文同時發布於好讀整理版

說明 Depth First 遍歷方式

Depth First 遍歷方法 : 第一個後往下,若下方還有子 node ,則繼續往下...沒有則繼續回去第二個

例如下圖 (Source from wikipedia)

tree

Depth First 遍歷方式 : 2, 7, 2, 10, 6, 5, 11, 5, 9, 4

想法

Depth First 遍歷方法其實跟上一篇的有一點類似,只是這次是有 children 就往下

JS 解法

class Node {
  constructor(data) {
    this.data = data;
    this.children = [];
  }
}

class Tree {
  constructor() {
    this.root = null;
  }

  traverseDepthFirst(func) {
    const ary = [this.root];
    while (ary.length) {
      const node = ary.shift();

      ary.unshift(...node.children);

      func(node);
    }
  }
}

說明:

有 children 的話用 unshift() 方法加資料到陣列的前面。

如果您有注意到的話,這跟上一篇 Breadth First Traversal 的差別只有把資料往前塞,或往後塞而已。

也就是 Depth First 是先找 children 放入 ; Breadth First 則是 children 後放入。

Tree 的遍歷(Traversal) 就先到這邊,明天我們來研究進一步的 Tree 吧!

本文同時發布於好讀整理版


上一篇
[One Punch 一拳搞定前後端面試] DAY-23 - Tree Breadth First Traversal
下一篇
[One Punch 一拳搞定前後端面試] DAY-25 -Binary Search Tree
系列文
One Punch 一拳搞定前後端面試30

尚未有邦友留言

立即登入留言