当前位置：首页 > JavaScript

js 实现二叉树

2026-01-30 16:52:02JavaScript

实现二叉树的基本结构

在 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);

二叉树的遍历方法

常见的遍历方式包括前序、中序和后序遍历，递归实现如下：

前序遍历（根-左-右）

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) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}

二叉树的插入与搜索

插入节点
根据二叉搜索树（BST）规则插入节点（左子树值小于根，右子树值大于根）：

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) return false;
  if (root.value === value) return true;
  if (value < root.value) {
    return searchNode(root.left, value);
  } else {
    return searchNode(root.right, value);
  }
}

二叉树的高度计算

递归计算树的最大深度：

function getHeight(node) {
  if (node === null) return 0;
  const leftHeight = getHeight(node.left);
  const rightHeight = getHeight(node.right);
  return Math.max(leftHeight, rightHeight) + 1;
}

示例：构建二叉搜索树

以下代码演示如何构建并操作二叉搜索树：

js 实现二叉树

let bstRoot = null;
bstRoot = insertNode(bstRoot, 10);
insertNode(bstRoot, 5);
insertNode(bstRoot, 15);
insertNode(bstRoot, 3);
console.log(searchNode(bstRoot, 5)); // 输出: true