iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 12
1
Software Development

使用JavaScript學習資料結構與演算法系列 第 12

Day12-資料結構-樹(Tree)的一些操作方法

  • 分享至 

  • xImage
  •  

今天將會把昨天實作的樹,加上幾個函式:

  • sum(): 所有節點值的總和
  • contain(): 查詢是否樹裡有指定要找的值
  • size(): 計算樹裡共有幾個節點
  • leaves(): 計算樹裡共有幾個葉節點
  • min(): 找出值最小的節點
  • max(): 找出值最大的節點
  • height(): 計算樹的高度

昨天實作的程式碼網址:
https://github.com/a90100/javascript-data-structure/blob/master/day11-tree.js

那我們廢話不多說,直接開始吧!

完成 sum() 函式:

首先將節點的左右子節點的值加起來,其左右子節點透過遞迴又會取得它們子節點的總和,不斷累加得到總和。

sum(node = this.root) {
  if (node === null) {
    return 0
  }
  return node.data +
    this.sum(node.left) +
    this.sum(node.right)
}

完成 contain() 函式:

透過另一個函式_contains(),帶著兩個參數進行判斷,當節點值和查找值相同就回傳true,不然就透過遞迴繼續往左右子節點查找。

contains(value) {
  return this._contains(this.root, value)
}

_contains(node, value) {
  if (node === null) {
    return false
  } else if (node.data === value) { // 當節點值和查找值相同就回傳true
    return true
  }
  return this._contains(node.left, value) ||
    this._contains(node.right, value)
}

完成 size() 函式:

size(node = this.root) {
  if (node === null) {
    return 0
  }
  return 1 + this.size(node.left) + this.size(node.right)
}

完成 leaves() 函式:

leaves(node = this.root) {
  if (node === null) {
    return 0
  }
  // 只有根節點的狀況
  if (node.left === null && node.right === null) {
    return 1
  }
  return this.leaves(node.left) + this.leaves(node.right)
}

完成 max() 函式:

max(node = this.root) {
  if (node === null) {
    return 0
  }
  let leftMax = this.max(node.left)
  let rightMax = this.max(node.right)
  // 父節點比左右子節點大的情況
  if (node.data > leftMax && node.data > rightMax) {
    return node.data
  } else if (leftMax > rightMax) { // 左節點最大
    return leftMax
  } else {
    // 右節點最大
    return rightMax
  }
}

完成 min() 函式:

min(node = this.root) {
  if (node === null) {
    // 預設節點值為樹的最大值
    return tree.max()
  }
  let leftMin = this.min(node.left)
  let rightMin = this.min(node.right)
  // 父節點比左右子節點小的情況
  if (node.data < leftMin && node.data < rightMin) {
    return node.data
  } else if (leftMin < rightMin) {
    return leftMin
  } else {
    return rightMin
  }
}

完成 height() 函式:

透過不斷遞迴,最後一次遞迴的 leftHeight 值為根節點的左子節點高度,rightHeight 值為根節點的右子節點高度,將兩者作比較,大者加1(根節點那層)便是一個樹的高度

height(node = this.root) {
  if (node === null) {
    return 0
  }
  let leftHeight = this.height(node.left)
  let rightHeight = this.height(node.right)
  if (leftHeight > rightHeight) {
    return 1 + leftHeight
  } else {
    return 1 + rightHeight
  }
}

本次文章的完整程式碼在此:
https://github.com/a90100/javascript-data-structure/blob/master/day12-tree-functions.js

下次我們來學習集合 Set,一起加油吧!


上一篇
Day11-來介紹資料結構-樹(Tree)吧!
下一篇
Day13-來了解 Set 並實作它吧!
系列文
使用JavaScript學習資料結構與演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言