js实现二叉树

实现二叉树的基本结构

在 JavaScript 中，二叉树可以通过对象或类实现。每个节点包含 value、left（左子树）和 right（右子树）属性。

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) return;
  console.log(node.value);
  preorderTraversal(node.left);
  preorderTraversal(node.right);
}

中序遍历（左-根-右）

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

后序遍历（左-右-根）

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

层序遍历（广度优先）

使用队列实现按层级遍历二叉树。

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

插入节点

根据特定规则（如二叉搜索树的条件）插入新节点。

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

查找节点

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

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

删除节点

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

function deleteNode(root, value) {
  if (!root) 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) return root.right;
    if (!root.right) return root.left;
    const minNode = findMin(root.right);
    root.value = minNode.value;
    root.right = deleteNode(root.right, minNode.value);
  }
  return root;
}

function findMin(node) {
  while (node.left) node = node.left;
  return node;
}

二叉树的高度

计算二叉树的深度（高度）。

function getHeight(root) {
  if (!root) return 0;
  return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}