JavaScript数据结构和算法之二叉树详解

什么是二叉树？

二叉树是一种树形结构，其中每个节点最多有两个子节点：左子节点和右子节点。每个节点都是一个对象，包括属性和方法。节点的属性可能包括值，左节点和右节点。节点的方法可能包括插入和删除。

二叉树的应用场景

二叉树的常用场景包括：

• 排序算法（二叉排序树）；
• 表达式求值；
• 线段树；
• 图形图像学；
• 数据压缩算法；
• 数据库索引；
• 网络路由表；
• 操作系统中文件目录的存储；
• 以及在各种算法中作为辅助数据结构等。

二叉树基本操作

1. 创建节点

创建一个二叉树节点的方法通常包括三个参数：左节点、右节点和节点的值。

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

2. 插入节点

插入节点的方法需要通过比较来确定节点的位置。如果要插入的值大于节点的值，则插入到右子树中；如果要插入的值小于节点的值，则插入到左子树中。这个操作需要递归处理。

function insertNode(root, newNode) {
  if (newNode.data < root.data) {
    if (root.left === null) {
      root.left = newNode
    } else {
      insertNode(root.left, newNode)
    }
  } else {
    if (root.right === null) {
      root.right = newNode
    } else {
      insertNode(root.right, newNode)
    }
  }
}

3. 搜索节点

搜索节点的方法需要通过比较来确定节点的位置。如果要搜索的值等于节点的值，则返回该节点；如果要搜索的值大于节点的值，则继续在右子树中查找；如果要搜索的值小于节点的值，则继续在左子树中查找。这个操作需要递归处理。

function findNode(root, data) {
  if (root === null) {
    return null
  } else if (data < root.data) {
    return findNode(root.left, data)
  } else if (data > root.data) {
    return findNode(root.right, data)
  } else {
    return root
  }
}

4. 删除节点

删除节点是比较复杂的一个操作，分为三种情况：

• 节点没有子节点；
• 节点仅有一个子节点；
• 节点有两个子节点。

其中第三种情况又可以分为两种情况：

• 在右子树中查找最小的节点，并替换要删除的节点；
• 在左子树中查找最大的节点，并替换要删除的节点。

function removeNode(root, data) {
  function remove(node, data) {
    if (node === null) {
      return null
    }
    if (data === node.data) {
      // 节点没有子节点
      if (node.left === null && node.right === null) {
        return null
      }
      // 节点仅有一个子节点
      if (node.left === null) {
        return node.right
      }
      if (node.right === null) {
        return node.left
      }
      // 节点有两个子节点，在右子树中查找最小的节点，并替换要删除的节点
      let tempNode = node.right
      while (tempNode.left != null) {
        tempNode = tempNode.left
      }
      node.data = tempNode.data
      node.right = remove(node.right, tempNode.data)
      return node
    } else if (data < node.data) {
      node.left = remove(node.left, data)
      return node
    } else {
      node.right = remove(node.right, data)
      return node
    }
  }
  root = remove(root, data)
  return root
}

示例说明

示例一：创建一个二叉树并插入节点

let root = new Node(10)
insertNode(root, new Node(5))
insertNode(root, new Node(15))
insertNode(root, new Node(2))
insertNode(root, new Node(13))
insertNode(root, new Node(17))
console.log(root)

输出结果：

Node {
  data: 10,
  left: Node {
    data: 5,
    left: Node { data: 2, left: null, right: null },
    right: null
  },
  right: Node {
    data: 15,
    left: Node { data: 13, left: null, right: null },
    right: Node { data: 17, left: null, right: null }
  }
}

示例二：删除二叉树中的一个节点

let root = new Node(10)
insertNode(root, new Node(5))
insertNode(root, new Node(15))
insertNode(root, new Node(2))
insertNode(root, new Node(13))
insertNode(root, new Node(17))
root = removeNode(root, 15)
console.log(root)

输出结果：

Node {
  data: 10,
  left: Node {
    data: 5,
    left: Node { data: 2, left: null, right: null },
    right: null
  },
  right: Node {
    data: 17,
    left: Node { data: 13, left: null, right: null },
    right: null
  }
}