SorryToPerson logo
返回
算法2026-04-15·8 分钟

算法知识库：二叉树实现

二叉树节点结构与常见遍历算法的 JavaScript/TypeScript 实现。

二叉树实现

1. 二叉树节点定义

时间复杂度: O(1) (节点创建) 空间复杂度: O(1) (单个节点)

  • 二叉树节点通常包含 value、left、right。
  • JavaScript/TypeScript 可用类或接口增强可读性。
ts
class TreeNode<T = number> {
  value: T;
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;

  constructor(value: T) {
    this.value = value;
  }
}

2. 递归遍历实现

时间复杂度: O(n) (访问每个节点一次) 空间复杂度: O(h) (递归栈空间，h为树的高度)

ts
function preorder<T>(root: TreeNode<T> | null): T[] {
  if (!root) return [];
  return [root.value, ...preorder(root.left), ...preorder(root.right)];
}

function inorder<T>(root: TreeNode<T> | null): T[] {
  if (!root) return [];
  return [...inorder(root.left), root.value, ...inorder(root.right)];
}

function postorder<T>(root: TreeNode<T> | null): T[] {
  if (!root) return [];
  return [...postorder(root.left), ...postorder(root.right), root.value];
}

3. 迭代遍历实现

ts
function preorderIterative<T>(root: TreeNode<T> | null): T[] {
  if (!root) return [];
  const stack = [root];
  const result: T[] = [];
  while (stack.length) {
    const node = stack.pop()!;
    result.push(node.value);
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return result;
}

function inorderIterative<T>(root: TreeNode<T> | null): T[] {
  const result: T[] = [];
  const stack: TreeNode<T>[] = [];
  let current = root;

  while (current || stack.length) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop()!;
    result.push(current.value);
    current = current.right;
  }

  return result;
}

4. 层序遍历（BFS）

ts
function levelOrder<T>(root: TreeNode<T> | null): T[] {
  if (!root) return [];
  const queue = [root];
  const result: T[] = [];

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

5. 插入与构建

ts
function insertBST(root: TreeNode<number> | null, value: number): TreeNode<number> {
  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;
}

6. 实现要点

  • 递归遍历适合代码简洁，但可能受栈深度限制。
  • 迭代遍历适合大树与生产环境。
  • TypeScript 可用泛型提高复用性和类型安全。
算法二叉树JavaScript