iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 23
0
Software Development

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

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

  • 分享至 

  • xImage
  •  

Tree - Breadth First Traversal

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

上一篇我們提到有 2 種遍歷 Tree 的方式,Breadth First 與 Depth First。

註: 遍歷 (Traversal) - 走訪每個元素

  1. Breadth First 遍歷方法 : 一層一層走訪,先第一層,然後第二層,然後第三層....

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

例如下圖 (Source from wikipedia)

tree

  1. Breadth First 遍歷方式 : 2, 7, 5, 2, 10, 6, 9, 5, 11, 4

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

差別

有一個重要的問題 : 這兩種方式有甚麼不一樣呢 ?

會根據不同的需求有所選擇,

例如一間公司有一個老闆,老闆下面有 A, B, C 經理分別處理不同業務,而 ABC 下方有自己的團隊員工。

情境:

  1. 如果今天要找所有的經理開會,那使用 Breadth First 方法是比較快的也比較合理的。

  2. 如果今天要找某專案的所有參與人開會,比如 A 經理及其下屬,那用 Depth First 方法是比較合理的。

實作 Breadth First Traversal

JavaScript 實作

先補上前兩篇實作的 Tree & Node ,然後來實作 Breadth First Traversal

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

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


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

    // ary.push(node.children)
    // for(let child of node.children) {
    //   ary.push(child);
    // }
    // // simplify
    ary.push(...node.children);

    func(node);
    }
  }
}

說明 :

ary.shift() 是拿掉自己(ary 第一個元素),然後塞進子陣列: ary.push(...node.children),避免重複。

下篇我們介紹 Depth First 遍歷方式,敬請期待...

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


上一篇
[One Punch 一拳搞定前後端面試] DAY-22 - Tree 之 Node
下一篇
[One Punch 一拳搞定前後端面試] DAY-24 -Tree Depth First Traversal
系列文
One Punch 一拳搞定前後端面試30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言