当前位置：首页 > JavaScript

js实现二叉树

2026-04-03 19:38:51JavaScript

实现二叉树的基本结构

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

二叉树的遍历方法

二叉树的遍历分为深度优先（DFS）和广度优先（BFS）。以下是常见实现方式：

1. 深度优先遍历（DFS）

前序遍历（根 → 左 → 右）：

function preorderTraversal(node) {
  if (!node) return [];
  return [node.value, ...preorderTraversal(node.left), ...preorderTraversal(node.right)];
}

中序遍历（左 → 根 → 右）：

function inorderTraversal(node) {
  if (!node) return [];
  return [...inorderTraversal(node.left), node.value, ...inorderTraversal(node.right)];
}

后序遍历（左 → 右 → 根）：

function postorderTraversal(node) {
  if (!node) return [];
  return [...postorderTraversal(node.left), ...postorderTraversal(node.right), node.value];
}

2. 广度优先遍历（BFS）
使用队列实现层级遍历：

function breadthFirstTraversal(root) {
  const result = [];
  const queue = [root];
  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;
}

插入节点的方法

根据二叉搜索树（BST）规则（左子树值 < 根值 < 右子树值），插入逻辑如下：

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new TreeNode(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          break;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          break;
        }
        current = current.right;
      }
    }
  }
}

查找节点

在BST中查找特定值：

js实现二叉树

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