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 [];
  return [
    node.value,
    ...preorderTraversal(node.left),
    ...preorderTraversal(node.right),
  ];
}
console.log(preorderTraversal(root)); // [1, 2, 4, 5, 3]

中序遍历（左 -> 根 -> 右）

递归实现：

function inorderTraversal(node) {
  if (!node) return [];
  return [
    ...inorderTraversal(node.left),
    node.value,
    ...inorderTraversal(node.right),
  ];
}
console.log(inorderTraversal(root)); // [4, 2, 5, 1, 3]

后序遍历（左 -> 右 -> 根）

递归实现：

function postorderTraversal(node) {
  if (!node) return [];
  return [
    ...postorderTraversal(node.left),
    ...postorderTraversal(node.right),
    node.value,
  ];
}
console.log(postorderTraversal(root)); // [4, 5, 2, 3, 1]

层序遍历（广度优先）

使用队列实现按层级遍历：

function levelOrderTraversal(root) {
  if (!root) return [];
  const queue = [root];
  const result = [];
  while (queue.length) {
    const node = queue.shift();
    result.push(node.value);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return result;
}
console.log(levelOrderTraversal(root)); // [1, 2, 3, 4, 5]

二叉树插入节点

根据特定规则（如二叉搜索树的有序性）插入新节点：

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) return null;
  if (root.value === value) return root;
  if (value < root.value) return searchBST(root.left, value);
  return searchBST(root.right, value);
}