---
tags: DSA in JavaScript
---
# Ch.22 Binary Search Tree

> 現在要開始提高難度了，樹狀結構~

樹狀結構可說是資料結構的固定班底之一，也普遍應用在不少地方

- HTML 的 DOM 架構
- 網路的 Routing
- 程式語言根基 -- 抽象語法樹（Abstract Syntax Tree，AST）
- 決策樹
- 作業系統內的檔案管理系統
- JSON、YAML、XML 等標記語言

樹狀結構的定義大致如下

- 父節點只會單向指向子節點
- 同一層的節點不會互指
- 除了根節點外，每個節點只會有一個父節點

在樹狀結構發展至今也出現了許多種類，其中一類是二元樹，代表每個節點最多只會有 2 個子節點。而二元搜尋樹除了二元樹的特點之外，以下特點也讓它提高搜尋的效率。

- 若一節點小於父節點，則該節點會在父節點的左側
- 若一節點大於父節點，則該節點會在父節點的右側

在下方的程式碼中會介紹二元搜尋樹的節點與兩個常用方法

class Node {
  constructor (value) {
    // 節點除了紀載本身的 value 之外，也會記載左側與右側的節點
    this.value = value
    this.left = null
    this.right = null
  }
}

class BinarySearchTree {
  constructor () {
    // 二元搜尋樹的一切存取、操作都是從根節點開始
    this.root = null
  }
}

以下分享的兩個方法是比較基本的插入與尋找，使用前請將方法放回 class 裡面

### `insert (value)`

在二元搜尋樹下新增一個節點，新增成功時會回傳搜尋樹本身。

insert (value) {
  // 1. 如果沒有根節點的話，就直接將新節點作為根節點
  if (!this.root) {
    this.root = new Node(value)
    return this
  }
  // 2. 以根節點為始，開始尋找新節點的位置
  let curr = this.root
  while (curr) {
  // 3. 如果輸入值已經存在，則離開方法
    if (value === curr.value) return
  // 4. 若輸入值比當前節點大...
    else if (value > curr.value) {
    // 4-1. ...且右側子節點為 null，則在該處新增節點，
      if (!curr.right) {
        curr.right = new Node(value)
        return this
      }
    // 4-2. 若存在右側子節點，指定該子節點為當前節點，進入下一層
      curr = curr.right
  // 5. 若輸入值比當前節點小...
    } else {
    // 5-1. ...且左側子節點為 null，則在該處新增節點
      if (!curr.left) {
        curr.left = new Node(value)
        return this
      }
    // 5-2. 若存在子節點的話，則將當前節點設定為該節點，進入下一層
      curr = curr.left
    }
  }
}

### `contains(value)`

在二元搜尋樹內尋找 value，回傳 true / false，代表搜尋樹下是否含有這個值。

contains (value) {
  // 1. 沒有節點的搜尋樹沒有比對的必要，直接回傳 false
  if (!this.root) return false
  let curr = this.root
  while (curr) {
  // 2. 若輸入值小於當前節點，則查找左側子節點
    if (value < curr.value) {
      curr = curr.left
  // 3. 若輸入值大於當前節點，則查找右側子節點
    } else if (value > curr.value) {
      curr = curr.right
  // 4. 若輸入值為當前節點的值，代表找到節點，回傳 true
    } else {
      return true
    }
  }
  // 5. 跳脫迴圈時，代表沒有節點符合輸入值，就是不再搜尋樹裡面，回傳 false
  return false
}