bst.js

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

class BST {
  insert (string) {
    if (typeof string !== 'string') return

    // 因为 JS 没有 call by reference 只有 call by sharing
    // 所以实现和 find 不同, 略繁琐一些
    function _insert (current, node) {
      if (current.data > node.data) {
        if (current.left) return _insert(current.left, node)
        current.left = node
      } else if (current.data < node.data) {
        if (current.right) return _insert(current.right, node)
        current.right = node
      } // 如果相等，不做任何事情, 默认不允许重复元素。
    }

    let node = new _Node(string)
    if (!this.root) this.root = node
    else _insert(this.root, node)
  }

  find (string) {
    if (typeof string !== 'string') return false

    function _find (current, string) {
      if (!current) return false
      if (current.data > string) return _find(current.left, string)
      if (current.data < string) return _find(current.right, string)
      return true
    }

    return _find(this.root, string)
  }

  print () {
    let array = []

    function toArray (node) { // 中序遍历
      if (!node) return

      toArray(node.left)
      array.push(node.data)
      toArray(node.right)
    }

    toArray(this.root)

    console.log(array.toString())
  }
}