树（Tree）结构

核心特性

层级结构：有根节点、子节点，无环（每个节点仅一个父节点）

核心概念：根节点（顶层节点）、叶子节点（无子节点）、深度（节点到根的路径长度）、高度（节点到叶子的最长路径长度）

常见类型：二叉树（每个节点最多 2 个子节点）、多叉树（每个节点可多个子节点，如 DOM 树、组件树）

代码实现（二叉树）

前序 / 中序 / 后序遍历

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null; // 左子节点
    this.right = null; // 右子节点
  }
}

class BinaryTree {
  constructor() {
    this.root = null; // 根节点
  }

  // 插入节点（简单版：按层次插入，不保证有序）
  insert(value) {
    const newNode = new TreeNode(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    // 用队列实现层次遍历，找到第一个空位插入
    const queue = [this.root];
    while (queue.length) {
      const current = queue.shift();
      if (!current.left) {
        current.left = newNode;
        return;
      }
      if (!current.right) {
        current.right = newNode;
        return;
      }
      queue.push(current.left, current.right);
    }
  }

  // 前序遍历（根→左→右）
  preOrderTraverse(node = this.root, result = []) {
    if (!node) return result;
    result.push(node.value); // 根
    this.preOrderTraverse(node.left, result); // 左
    this.preOrderTraverse(node.right, result); // 右
    return result;
  }

  // 中序遍历（左→根→右）
  inOrderTraverse(node = this.root, result = []) {
    if (!node) return result;
    this.inOrderTraverse(node.left, result); // 左
    result.push(node.value); // 根
    this.inOrderTraverse(node.right, result); // 右
    return result;
  }

  // 后序遍历（左→右→根）
  postOrderTraverse(node = this.root, result = []) {
    if (!node) return result;
    this.postOrderTraverse(node.left, result); // 左
    this.postOrderTraverse(node.right, result); // 右
    result.push(node.value); // 根
    return result;
  }

  // 层次遍历（按层遍历，用队列实现）
  levelOrderTraverse() {
    const result = [];
    if (!this.root) return result;
    const queue = [this.root];
    while (queue.length) {
      const current = queue.shift();
      result.push(current.value);
      if (current.left) queue.push(current.left);
      if (current.right) queue.push(current.right);
    }
    return result;
  }
}

适用场景

DOM 树操作：document.body是根节点，遍历 DOM 树（如查找所有按钮）可用品级遍历或深度遍历

组件树渲染：React/Vue 的组件树，用深度遍历（如递归渲染子组件）

树形菜单 / 表格：如商品分类树（一级分类→二级分类→...），用递归遍历渲染

路由树：Vue Router/React Router 的路由配置是树形结构，匹配路由时用深度遍历