JavaScript数据结构与算法(二叉搜索树)

树是一种分层数据的抽象模型。二叉树中的节点最多只能有两个子节点:一个是左侧子节点，另一个是右侧子节点。

二叉搜索树

二叉搜索树(BST)是二叉树的一种，但是只允许在左侧节点存储(比父节点)小的值，在右侧节点存储(比父节点)大的值。

插入

const COMPARE = {
  less: -1,
  more: 1,
  equal: 0,
}

class Node {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null
  }
}

class BST {
  constructor(key) {
    this.root = null
  }

  // 插入
  insert(key) {
    if (this.root == null) {
      this.root = new Node(key)
    } else {
      this.insertNode(this.root, key)
    }
  }

  compareFn(a, b) {
    if (a === b) {
      return COMPARE.equal
    }

    return a < b ? COMPARE.less : COMPARE.more
  }

  insertNode(node, key) {
    if (this.compareFn(key, node.key) === COMPARE.less) {
      if (node.left == null) {
        node.left = new Node(key)
      } else {
        this.insertNode(node.left, key)
      }
    } else {
      if (node.right == null) {
        node.right = new Node(key)
      } else {
        this.insertNode(node.right, key)
      }
    }
  }
}

const mytree = new BST()

mytree.insert(100)
mytree.insert(90)
mytree.insert(110)
mytree.insert(60)
mytree.insert(80)

console.log(mytree)

遍历

中序遍历是一种以上行顺序访问BST所有节点的遍历方式，也就是以从最小到最大的顺序访问所有节点。中序遍历的一种应用就是对树进行排序操作。

// 中序遍历
inOrderMap(cb) {
  this.inOrderMapNode(this.root, cb)
}

inOrderMapNode(node, cb) {
  if (node != null) {
    this.inOrderMapNode(node.left, cb)
    cb(node.key)
    this.inOrderMapNode(node.right, cb)
  }
}

mytree.inOrderMap((value) => {
  console.log(value)
})

先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。

// 先序遍历
preOrderMap(cb) {
  this.preOrderMapNode(this.root, cb)
}

preOrderMapNode(node, cb) {
  if (node != null) {
    cb(node.key)
    this.preOrderMapNode(node.left, cb)
    this.preOrderMapNode(node.right, cb)
  }
}

mytree.preOrderMap((value) => {
  console.log(value)
})

后序遍历则是先访问节点的后代节点，再访问节点本身。后序遍历的一种应用是计算一个目录及其子目录中所有文件所占空间的大小。

// 后序遍历
postOrderMap(cb) {
  this.postOrderMapNode(this.root, cb)
}

postOrderMapNode(node, cb) {
  if (node != null) {
    this.postOrderMapNode(node.left, cb)
    this.postOrderMapNode(node.right, cb)
    cb(node.key)
  }
}

mytree.postOrderMap((value) => {
  console.log(value)
})

查询

// 最小值
min() {
  return this.minNode(this.root)
}

minNode(node) {
  let current = node
  while (current != null && current.left != null) {
    current = current.left
  }
  return current
}

// 最大值
max() {
  return this.maxNode(this.root)
}

maxNode(node) {
  let current = node
  while (current != null && current.right != null) {
    current = current.right
  }
  return current
}

// 搜索某个值
search(key) {
  return this.searchNode(this.root, key)
}

searchNode(node, key) {
  if (node == null) {
    return false
  }
  if (this.compareFn(key, node.key) === COMPARE.less) {
    return this.searchNode(node.left, key)
  } else if (this.compareFn(key, node.key) === COMPARE.more) {
    return this.searchNode(node.right, key)
  } else {
    return true
  }
}

移除

remove(key) {
  this.root = this.removeNode(this.root, key)
}

removeNode(node, key) {
  if (node == null) {
    return null
  }
  if (this.compareFn(key, node.key) === COMPARE.less) {
    node.left = this.removeNode(node.left, key)
    return node
  } else if (this.compareFn(key, node.key) === COMPARE.more) {
    node.right = this.removeNode(node.right, key)
    return node
  } else {
    // 第一种情况：叶节点
    if (node.left == null && node.right == null) {
      node = null
      return node
    }
    // 第二种情况：移除有一个左侧或右侧子节点的节点
    if (node.left == null) {
      node = node.right
      return node
    } else if (node.right == null) {
      node = node.left
      return node
    }
    // 第三种情况：移除有两个子节点的节点
    const target = this.minNode(node.right) //找到最小
    node.key = target.key
    node.right = this.removeNode(node.right, target.key)
    return node
  }
}