js 实现二叉树

实现二叉树的基本结构

在JavaScript中，二叉树可以通过对象或类来实现。每个节点包含一个值和两个子节点（左子节点和右子节点）。

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

创建二叉树实例

通过实例化节点并连接子节点来构建二叉树。

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

二叉树的遍历方法

二叉树的遍历分为前序、中序和后序三种方式。

前序遍历（根-左-右）

function preorderTraversal(node) {
  if (node === null) return;
  console.log(node.value);
  preorderTraversal(node.left);
  preorderTraversal(node.right);
}

中序遍历（左-根-右）

function inorderTraversal(node) {
  if (node === null) return;
  inorderTraversal(node.left);
  console.log(node.value);
  inorderTraversal(node.right);
}

后序遍历（左-右-根）

function postorderTraversal(node) {
  if (node === null) return;
  postorderTraversal(node.left);
  postorderTraversal(node.right);
  console.log(node.value);
}

层序遍历（广度优先）

使用队列实现层序遍历，逐层访问节点。

function levelOrderTraversal(root) {
  if (root === null) return;
  const queue = [root];
  while (queue.length > 0) {
    const node = queue.shift();
    console.log(node.value);
    if (node.left !== null) queue.push(node.left);
    if (node.right !== null) queue.push(node.right);
  }
}

插入节点

根据二叉搜索树的特性插入节点（左子节点小于父节点，右子节点大于父节点）。

function insertNode(root, value) {
  if (root === null) return new TreeNode(value);
  if (value < root.value) {
    root.left = insertNode(root.left, value);
  } else {
    root.right = insertNode(root.right, value);
  }
  return root;
}

查找节点

在二叉搜索树中查找特定值的节点。

function searchNode(root, value) {
  if (root === null || root.value === value) return root;
  if (value < root.value) return searchNode(root.left, value);
  return searchNode(root.right, value);
}

删除节点

删除二叉搜索树中的节点，需处理三种情况：无子节点、一个子节点、两个子节点。

function deleteNode(root, value) {
  if (root === null) return null;
  if (value < root.value) {
    root.left = deleteNode(root.left, value);
  } else if (value > root.value) {
    root.right = deleteNode(root.right, value);
  } else {
    if (root.left === null) return root.right;
    if (root.right === null) return root.left;
    const minNode = findMinNode(root.right);
    root.value = minNode.value;
    root.right = deleteNode(root.right, minNode.value);
  }
  return root;
}

function findMinNode(node) {
  while (node.left !== null) node = node.left;
  return node;
}

验证二叉搜索树

检查二叉树是否符合二叉搜索树的定义。

function isValidBST(root, min = null, max = null) {
  if (root === null) return true;
  if ((min !== null && root.value <= min) || (max !== null && root.value >= max)) return false;
  return isValidBST(root.left, min, root.value) && isValidBST(root.right, root.value, max);
}