数据结构 — 二叉树.md

数据结构 — 二叉树

二叉树（Binary tree）是由一组表示层次树结构的链接节点组成的数据结构。每个节点通过父子关系链接到其他节点。任何给定节点最多可以有两个子节点（左和右）。二叉树中的第一个节点是根，而没有任何子节点的节点是叶。

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

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

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

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

JavaScript 实现

class BinaryTreeNode {
  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 BinaryTree {
  constructor(key, value = key) {
    this.root = new BinaryTreeNode(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(
    parentNodeKey,
    key,
    value = key,
    { left, right } = { left: true, right: true }
  ) {
    for (const node of this.preOrderTraversal()) {
      if (node.key === parentNodeKey) {
        const canInsertLeft = left && node.left === null
        const canInsertRight = right && node.right === null
        if (!canInsertLeft && !canInsertRight) return false
        if (canInsertLeft) {
          node.left = new BinaryTreeNode(key, value, node)
          return true
        }
        if (canInsertRight) {
          node.right = new BinaryTreeNode(key, value, node)
          return true
        }
      }
    }
    return false
  }

  remove(key) {
    for (const node of this.preOrderTraversal()) {
      if (node.left.key === key) {
        node.left = null
        return true
      }
      if (node.right.key === key) {
        node.right = null
        return true
      }
    }
    return false
  }

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

• 创建一个具有 constructor 的 BinaryTreeNode 类（class），为每个实例初始化 key、value、parent、left 和 right 属性。
• 定义一个 isLeaf getter，使用 Array.prototype.length 检查 left 和 right 是否为空。
• 定义一个 hasChildren getter，它与 isLeaf getter 相反。
• 创建一个具有 constructor 的 BinaryTree 类（class），初始化二叉树的 root。
• 定义一个 preOrderTraversal() 按预先顺序遍历二叉树生成器方法，使用 yield* 语法递归地将遍历委托给自身。
• 定义一个 postOrderTraversal() 以后序遍历二叉树的生成器方法，使用 yield* 语法递归地将遍历委托给自身。
• 定义一个 inOrderTraversal() 按顺序遍历二叉树的生成器方法，使用 yield* 语法递归地将遍历委托给自身。
• 定义一个 insert() 方法，使用 preOrderTraversal() 方法查找给定的父节点，并根据传递的选项对象插入一个新的子 BinaryTreeNode 作为 left 或 right 子节点。
• 定义一个 remove() 方法，使用 preOrderTraversal() 方法和 Array.prototype.filter() 从二叉树中删除二进制树节点。
• 定义一个 find() 方法，使用 preOrderTraversal() 方法检索二叉树中的给定节点。

const tree = new BinaryTree(1, 'AB')

tree.insert(1, 11, 'AC')
tree.insert(1, 12, 'BC')
tree.insert(12, 121, 'BG', { right: true })
;[...tree.preOrderTraversal()].map((x) => x.value) // ['AB', 'AC', 'BC', 'BCG']
;[...tree.inOrderTraversal()].map((x) => x.value) // ['AC', 'AB', 'BC', 'BG']

tree.root.value // 'AB'
tree.root.hasChildren // true

tree.find(12).isLeaf // false
tree.find(121).isLeaf // true
tree.find(121).parent.value // 'BC'
tree.find(12).left // null
tree.find(12).right.value // 'BG'

tree.remove(12)
;[...tree.postOrderTraversal()].map((x) => x.value) // ['AC', 'AB']

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

LeetCode 相关的链表题目

• 二叉树的中序遍历
• 对称二叉树
• 二叉树的层序遍历
• 二叉树的最大深度
• 二叉树展开为链表
• 二叉树中的最大路径和
• 翻转二叉树
• 二叉树的最近公共祖先
• 二叉树的序列化与反序列化
• 合并二叉树
• 二叉树的直径

更多资料

Binary Tree Traversal 可视化二叉树遍历