iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 11
1
Software Development

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

Day11-來介紹資料結構-樹(Tree)吧!

今天要介紹的是樹,大致的樣子如下圖,其中樹的每個元素都稱為節點,樹最上方的節點稱為根節點,而節點之間上層節點為下層節點的父節點,下層節點為上層節點的子節點,如果一個節點底下沒有任何的子節點,我們稱為葉節點

節點和其子節點可以構成子樹,如圖中的紅框部分。
一個節點的深度可由它祖先節點的數量推算出,例如14節點有25和34兩個祖先節點,其深度為2。
樹的高度則取決於所有節點深度的最大值,此圖高度為3。

二元樹(Binary tree) 和 二元搜尋樹(Binary Search Tree)

這兩種樹在資料結構中相當常見,因此來稍微介紹它們:

二元樹每個節點最多只有兩個分支(即不存在分支度大於2的節點)的樹結構。通常分支被稱作「左子樹」或「右子樹」。

二元搜尋樹是指一棵空樹或者具有下列性質的二元樹:

  • 若任意節點的左子樹不空,則左子樹上所有節點的值均小於它的根節點的值
  • 若任意節點的右子樹不空,則右子樹上所有節點的值均大於它的根節點的值
  • 任意節點的左、右子樹也分別為二元搜尋樹
  • 沒有鍵值相等的節點

二元搜尋樹的範例圖:

在看完樹的介紹之後,我們來用 JavaScript 實作 樹吧!

先建立出節點和樹的類別出來:

class TreeNode {
  constructor(data, left = null, right = null) {
    this.data = data
    this.left = left
    this.right = right
  }
}

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

之後透過新增節點,然後將節點加到節各節點的分支,便完成了

let n1 = new TreeNode(32);
let n2 = new TreeNode(92);
let n3 = new TreeNode(13);
let n4 = new TreeNode(44);
let n5 = new TreeNode(87);

let tree = new Tree();
tree.root = n1
n1.left = n2
n1.right = n3
n3.right = n4
n4.left = n5

產生的樹如下圖所示:

樹到這邊就完成實作,不過我們來試試多加一個 collect() 函式,將所有節點整理成陣列輸出

我們預設一開始的節點是root,然後節點陣列為空陣列,然後將目前找到的節點推入陣列,並將該節點的左右子節點作為參數,再次呼叫 collect() 函式進行遞迴。

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

  // 使用遞迴去遍歷樹節點
  // 一開始的節點是root,然後節點陣列為空陣列
  collect(current = this.root, nodes = []) {
    if (current === null) {
      return nodes
    }
    nodes.push(current.data)

    this.collect(current.left, nodes)
    this.collect(current.right, nodes)
    return nodes
  }
}

用文字解說遞迴順序:

  1. current = this.root,也就是根節點50,推入陣列 nodes
  2. 找到根節點50的左節點43,推入陣列 nodes
  3. 節點43再找左節點,但為 null,無新增任何東西,右節點也一樣為 null
  4. 找到根節點50的右節點67,推入陣列 nodes
  5. 節點67再找左節點,但為 null,無新增任何東西,不過找到有右節點,為節點81,推入陣列 nodes
  6. 節點81找到左節點75,推入陣列 nodes,節點75左右子節點都是 null,便回傳最終的 nodes 陣列

這次實作的程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day11-tree.js

以上就是這次的樹 (Tree) 介紹,明天將會介紹樹的一些相關操作函式!


上一篇
Day10-來介紹遞迴(Recursion)吧!
下一篇
Day12-資料結構-樹(Tree)的一些操作方法
系列文
使用JavaScript學習資料結構與演算法30

尚未有邦友留言

立即登入留言