树介绍

【学习 JavaScript 数据结构与算法（第 3 版）】第 10 章

概念

根节点，树顶部的节点

内部节点，至少有一个子节点的节点

外部节点/叶节点，没有子元素的节点

子树，由节点和它的后代构成

二叉树，节点最多只能有两个子节点，一个是左侧子节点，另一个是右侧子节点

二叉搜索树（BST）

• 若它的左子树不为空，左子树上所有节点的值都小于它的根节点。
• 若它的右子树不为空，右子树上所有的节点的值都大于它的根节点。

遍历

中序遍历，左根右
94.二叉树的中序遍历

前序遍历，根左右
144.二叉树的前序遍历

后序遍历，左右根
145.二叉树的后序遍历

• 深度优先（DFS）

const dfs = tree => {
  tree.children.forEach(dfs)
}

• 广度优先（BFS）

const bfs = tree => {
  const q = [tree]

  while (q.length > 0) {
    const n = q.shift()
    n.children.forEach(c => q.push(c))
  }
}

代码实现

书的官方代码库

• 二叉搜索树

为 lt 刷题，自己写的代码

export class TreeNode {
  val?: number | string
  left?: TreeNode | null
  right?: TreeNode | null
  constructor(
    val?: number | string,
    left?: TreeNode | null,
    right?: TreeNode | null,
  ) {
    this.val = val || 0
    this.left = left === undefined ? null : left
    this.right = right === undefined ? null : right
  }
}

export class TreeNodeWithChildren {
  val: number
  children?: TreeNodeWithChildren[]
  constructor(val?: number, children?: TreeNodeWithChildren[]) {
    this.val = val === undefined ? 0 : val
    this.children = children || []
  }
}

export class Tree {
  root: TreeNode
  constructor(array: (number | null)[]) {
    this.creat(array)
  }
  creat(array: (number | null)[]) {
    if (array.length === 0) {
      return null
    }

    const root = new TreeNode(array.shift())
    this.root = root

    const nodeQueue = [root]

    while (array.length > 0) {
      const node = nodeQueue.shift()
      //左子节点
      let val = array.shift()
      if (val !== null) {
        const left = new TreeNode(val)
        node.left = left
        nodeQueue.push(left)
      }
      //右子节点
      val = array.shift() //可能已经没有元素了，undefined
      //不为 null，不为undefined，0可以
      if (val != null) {
        const right = new TreeNode(val)
        node.right = right
        nodeQueue.push(right)
      }
    }
  }
}