Skip to content

Latest commit

 

History

History
201 lines (170 loc) · 7.83 KB

数据结构 — 二叉搜索树.md

File metadata and controls

201 lines (170 loc) · 7.83 KB
Raw

数据结构 — 二叉搜索树

二叉搜索树（BST，Binary Search Tree）是由一组表示层次树结构的有序链接节点组成的数据结构。每个节点都通过父子关系链接到其他节点。任何给定节点最多可以有两个子节点（左和右）。二叉搜索树中的第一个节点是根，而没有任何子节点的节点是叶。二叉搜索树的组织方式是，对于任何给定的节点，其左子树中的所有节点都有一个小于自身的键，而其右子树中的所有节点都有一个大于自身的键。

JavaScript 二叉搜索树可视化

二叉搜索树数据结构中的每个节点都必须具有以下属性：

  • key：节点的键
  • value：节点的值
  • parent：节点的父节点（如果没有，则为 null）
  • left：指向节点左子级的指针（如果没有，则为 null）
  • right：指向节点右子级的指针（如果没有，则为 null）

二叉搜索树数据结构的主要操作有：

  • insert：将节点作为给定父节点的子节点插入
  • remove：从二叉搜索树中删除节点及其子节点
  • has：检查给定节点是否存在
  • find：检索给定节点
  • preOrderTraversal：通过递归遍历每个节点及其子节点来遍历二叉搜索树
  • postOrderTraversal：通过递归遍历每个节点的子节点，然后遍历该节点，从而遍历二叉搜索树
  • inOrderTraversal：通过递归遍历每个节点的左子节点，然后遍历节点，然后是其右子节点来遍历二叉搜索树

JavaScript 实现

class BinarySearchTreeNode {
  constructor(key, value = key, parent = null) {
    this.key = key
    this.value = value
    this.parent = parent
    this.left = null
    this.right = null
  }

  get isLeaf() {
    return this.left === null && this.right === null
  }

  get hasChildren() {
    return !this.isLeaf
  }
}

class BinarySearchTree {
  constructor(key, value = key) {
    this.root = new BinarySearchTreeNode(key, value)
  }

  *inOrderTraversal(node = this.root) {
    if (node.left) yield* this.inOrderTraversal(node.left)
    yield node
    if (node.right) yield* this.inOrderTraversal(node.right)
  }

  *postOrderTraversal(node = this.root) {
    if (node.left) yield* this.postOrderTraversal(node.left)
    if (node.right) yield* this.postOrderTraversal(node.right)
    yield node
  }

  *preOrderTraversal(node = this.root) {
    yield node
    if (node.left) yield* this.preOrderTraversal(node.left)
    if (node.right) yield* this.preOrderTraversal(node.right)
  }

  insert(key, value = key) {
    let node = this.root
    while (true) {
      if (node.key === key) return false
      if (node.key > key) {
        if (node.left !== null) node = node.left
        else {
          node.left = new BinarySearchTreeNode(key, value, node)
          return true
        }
      } else if (node.key < key) {
        if (node.right !== null) node = node.right
        else {
          node.right = new BinarySearchTreeNode(key, value, node)
          return true
        }
      }
    }
  }

  has(key) {
    for (const node of this.postOrderTraversal()) {
      if (node.key === key) return true
    }
    return false
  }

  find(key) {
    for (const node of this.postOrderTraversal()) {
      if (node.key === key) return node
    }
    return undefined
  }

  remove(key) {
    const node = this.find(key)
    if (!node) return false
    const isRoot = node.parent === null
    const isLeftChild = !isRoot ? node.parent.left === node : false
    const hasBothChildren = node.left !== null && node.right !== null

    if (node.isLeaf) {
      if (!isRoot) {
        if (isLeftChild) node.parent.left = null
        else node.parent.right = null
      } else {
        this.root = null
      }
      return true
    } else if (!hasBothChildren) {
      const child = node.left !== null ? node.left : node.right
      if (!isRoot) {
        if (isLeftChild) node.parent.left = child
        else node.parent.right = child
      } else {
        this.root = child
      }
      child.parent = node.parent
      return true
    } else {
      const rightmostLeft = [...this.inOrderTraversal(node.left)].slice(-1)[0]
      rightmostLeft.parent = node.parent
      if (!isRoot) {
        if (isLeftChild) node.parent.left = rightmostLeft
        else node.parent.right = rightmostLeft
      } else {
        this.root = rightmostLeft
      }
      rightmostLeft.right = node.right
      node.right.parent = rightmostLeft
      return true
    }
  }
}
  • 创建一个具有 constructor 的 BinarySearchTreeNode 类（class），使用 为每个实例初始化 key、value、parent、left 和 right 属性。
  • 定义一个 isLeaf getter，使用 Array.prototype.length 检查 left 和 right 是否为空。
  • 定义一个 hasChildren getter，它与 isLeaf getter 相反。
  • 创建一个具有 constructor 的 BinarySearchTree 类（class），用于初始化二叉搜索树的 root。
  • 定义一个 preOrderTraversal() 按预先顺序遍历二叉搜索树生成器方法，使用 yield* 语法递归地将遍历委托给自身。
  • 定义一个 postOrderTraversal() 以后序遍历二叉搜索树的生成器方法，使用 yield* 语法递归地将遍历委托给自身。
  • 定义一个 inOrderTraversal() 按顺序遍历二叉搜索树的生成器方法，使用 yield* 语法递归地将遍历委托给自身。
  • 定义一个 insert() 方法，它使用 while 循环来搜索二叉搜索树，遍历每个节点的子节点，直到找到合适的位置以插入新的子节点 BinarySearchTreeNode 作为 left 或 right 子节点，具体取决于给定的 key。
  • 定义一个 insert() 方法，使用 preOrderTraversal() 方法查找给定的父节点，并根据传递的选项对象插入一个新的子 BinaryTreeNode 作为 left 或 right 子节点。
  • 定义一个 has() 方法，它使用 preOrderTraversal() 方法濑检查给定的节点是否存在于二叉搜索树中。
  • 定义一个 find() 方法，使用 preOrderTraversal() 方法在二叉搜索树中检索给定节点。
  • 定义一个 remove() 方法，从二叉搜索树中删除给定的 BinarySearchTreeNode，删除指向它的任何链接，并更新二叉搜索树以保持其顺序。
const tree = new BinarySearchTree(30)

tree.insert(10)
tree.insert(15)
tree.insert(12)
tree.insert(40)
tree.insert(35)
tree.insert(50)
;[...tree.preOrderTraversal()].map((x) => x.value) // [30, 10, 15, 12, 40, 35, 50]
;[...tree.inOrderTraversal()].map((x) => x.value) // [10, 12, 15, 30, 35, 40, 50]
;[...tree.postOrderTraversal()].map((x) => x.value) // [12, 15, 10, 35, 50, 40, 30]

tree.root.value // 30
tree.root.hasChildren // true

tree.find(12).isLeaf // true
tree.find(40).isLeaf // false
tree.find(50).parent.value // 40
tree.find(15).left.value // 12
tree.find(12).right // null

tree.remove(12)
;[...tree.preOrderTraversal()].map((x) => x.value) // [30, 10, 15, 40, 35, 50]

tree.remove(10)
;[...tree.preOrderTraversal()].map((v) => ({
  key: v.key,
  parent: v.parent ? v.parent.key : null
})) // [30, 15, 40, 35, 50]

tree.remove(40)
;[...tree.preOrderTraversal()].map((x) => x.value) // [30, 15, 40, 35, 50]

tree.remove(30)
;[...tree.preOrderTraversal()].map((x) => x.value) // [15, 35, 50]

以上内容译自 30 seconds of code 的 JavaScript Data Structures - Binary Search Tree

更多资料