4.1 树形数据处理 - 深度剖析

负责树形组件开发,支持组织架构、文件目录等场景
- 实现树形数据的增删改查,支持节点拖拽排序,用户操作流畅
- 开发树形搜索功能,支持关键词高亮和父节点展开,搜索响应 < 100ms
- 支持懒加载,按需加载子节点,降低首屏加载时间 60%

设计并实现高性能树形数据处理方案,支撑核心业务模块
- 创新性地采用扁平化存储 + 索引结构,树节点查询从 O(n) 优化到 O(1)
- 实现虚拟树渲染,10万节点树展开时间从 5s 降至 200ms,内存占用减少 80%
- 开发树形搜索算法,支持模糊匹配、祖先路径展示,搜索准确率 95%+
- 优化懒加载策略,通过预加载和缓存,减少 70% 的网络请求

主导树形数据架构设计,建立企业级树形解决方案
- 抽象树形数据模型,支持多种数据源(嵌套/扁平/异步),统一对外接口
- 设计树形状态管理机制,支持多选、半选、级联、禁用等复杂交互
- 建立树形性能监控体系,识别并优化关键路径,大树操作耗时降低 70%
- 制定树形组件规范,支撑 20+ 业务场景,代码复用率 85%

{
  id: '1',
  name: '根节点',
  children: [
    {
      id: '1-1',
      name: '子节点1',
      children: []
    }
  ]
}

[
  { id: '1', name: '根节点', parentId: null },
  { id: '1-1', name: '子节点1', parentId: '1' },
  { id: '1-2', name: '子节点2', parentId: '1' }
]

function flattenTree(tree, parentId = null) {
  const result = []

  function traverse(nodes, pid) {
    nodes.forEach(node => {
      const { children, ...rest } = node
      result.push({ ...rest, parentId: pid })

      if (children && children.length > 0) {
        traverse(children, node.id)
      }
    })
  }

  traverse(Array.isArray(tree) ? tree : [tree], parentId)
  return result
}

function unflattenTree(flatArray) {
  const map = new Map()
  const roots = []

  // 第一遍遍历,建立 id -> node 的映射
  flatArray.forEach(item => {
    map.set(item.id, { ...item, children: [] })
  })

  // 第二遍遍历,建立父子关系
  flatArray.forEach(item => {
    const node = map.get(item.id)

    if (item.parentId === null || item.parentId === undefined) {
      roots.push(node)
    } else {
      const parent = map.get(item.parentId)
      if (parent) {
        parent.children.push(node)
      }
    }
  })

  return roots
}

const nodeMap = new Map([
  ['1', { id: '1', name: '根节点', parentId: null }],
  ['1-1', { id: '1-1', name: '子节点', parentId: '1' }]
])

const childrenMap = new Map([
  ['1', ['1-1', '1-2']],
  ['1-1', ['1-1-1']]
])

function getNode(id) {
  return nodeMap.get(id)
}

function getChildren(id) {
  const childIds = childrenMap.get(id) || []
  return childIds.map(childId => nodeMap.get(childId))
}

function getParent(id) {
  const node = nodeMap.get(id)
  return node?.parentId ? nodeMap.get(node.parentId) : null
}

function getAncestors(id) {
  const ancestors = []
  let current = getNode(id)

  while (current?.parentId) {
    current = getParent(current.id)
    if (current) {
      ancestors.unshift(current)
    }
  }

  return ancestors
}

function addNode(node, parentId) {
  // 添加到 nodeMap
  nodeMap.set(node.id, { ...node, parentId })

  // 更新 childrenMap
  if (!childrenMap.has(parentId)) {
    childrenMap.set(parentId, [])
  }
  childrenMap.get(parentId).push(node.id)
}

function deleteNode(id) {
  const node = nodeMap.get(id)
  if (!node) return

  // 递归删除所有子节点
  const childIds = childrenMap.get(id) || []
  childIds.forEach(childId => deleteNode(childId))

  // 从父节点的子列表中移除
  if (node.parentId) {
    const siblings = childrenMap.get(node.parentId)
    const index = siblings.indexOf(id)
    if (index > -1) {
      siblings.splice(index, 1)
    }
  }

  // 删除节点本身
  nodeMap.delete(id)
  childrenMap.delete(id)
}

function moveNode(nodeId, newParentId) {
  const node = nodeMap.get(nodeId)
  if (!node) return

  // 检查是否形成循环(不能移动到自己的子孙节点下)
  if (isDescendant(newParentId, nodeId)) {
    throw new Error('不能移动到子孙节点下')
  }

  // 从原父节点移除
  if (node.parentId) {
    const oldSiblings = childrenMap.get(node.parentId)
    const index = oldSiblings.indexOf(nodeId)
    oldSiblings.splice(index, 1)
  }

  // 添加到新父节点
  node.parentId = newParentId
  if (!childrenMap.has(newParentId)) {
    childrenMap.set(newParentId, [])
  }
  childrenMap.get(newParentId).push(nodeId)
}

{
  id: '1',
  name: '部门A',
  isLeaf: false,  // 不是叶子节点
  children: null   // 子节点未加载
}

async function loadChildren(node) {
  // 如果已经加载过,直接返回
  if (node.children && node.children.length > 0) {
    return node.children
  }

  // 如果是叶子节点,不需要加载
  if (node.isLeaf) {
    return []
  }

  // 调用接口加载
  const response = await api.getChildren(node.id)
  const children = response.data

  // 更新节点的 children
  node.children = children

  // 更新索引
  children.forEach(child => {
    nodeMap.set(child.id, child)
  })
  childrenMap.set(node.id, children.map(c => c.id))

  return children
}

<template>
  <div class="tree-node">
    <div @click="handleToggle">
      <span v-if="!node.isLeaf">
        {{ node.expanded ? '▼' : '▶' }}
      </span>
      {{ node.name }}
      <span v-if="loading">加载中...</span>
    </div>

    <div v-if="node.expanded && node.children">
      <TreeNode
        v-for="child in node.children"
        :key="child.id"
        :node="child"
      />
    </div>
  </div>
</template>

<script setup>
import { ref } from 'vue'

const props = defineProps(['node'])

const loading = ref(false)

async function handleToggle() {
  if (props.node.isLeaf) return

  // 展开/折叠
  props.node.expanded = !props.node.expanded

  // 如果是展开,且子节点未加载,则加载
  if (props.node.expanded && !props.node.children) {
    loading.value = true
    try {
      await loadChildren(props.node)
    } finally {
      loading.value = false
    }
  }
}
</script>

let preloadTimer = null

function handleMouseEnter(node) {
  preloadTimer = setTimeout(() => {
    if (!node.children) {
      loadChildren(node)
    }
  }, 1000)
}

function handleMouseLeave() {
  clearTimeout(preloadTimer)
}

async function loadMultipleLevels(node, levels = 2) {
  const queue = [{ node, level: 0 }]

  while (queue.length > 0) {
    const { node, level } = queue.shift()

    if (level >= levels) continue

    const children = await loadChildren(node)
    children.forEach(child => {
      queue.push({ node: child, level: level + 1 })
    })
  }
}

function searchTree(keyword) {
  const matchedIds = new Set()
  const expandedIds = new Set()

  // 遍历所有节点,找出匹配的
  nodeMap.forEach((node, id) => {
    if (node.name.includes(keyword)) {
      matchedIds.add(id)

      // 把所有祖先节点也标记为需要展开
      let current = node
      while (current.parentId) {
        expandedIds.add(current.parentId)
        current = nodeMap.get(current.parentId)
      }
    }
  })

  return { matchedIds, expandedIds }
}

<TreeNode
  v-for="node in visibleNodes"
  :key="node.id"
  :node="node"
  :highlighted="matchedIds.has(node.id)"
/>

function searchTreeWithSiblings(keyword) {
  const matchedIds = new Set()
  const visibleIds = new Set()

  nodeMap.forEach((node, id) => {
    if (node.name.includes(keyword)) {
      matchedIds.add(id)

      // 添加节点本身
      visibleIds.add(id)

      // 添加所有祖先
      let current = node
      while (current.parentId) {
        const parent = nodeMap.get(current.parentId)
        visibleIds.add(parent.id)

        // 添加父节点的所有子节点(兄弟节点)
        const siblings = childrenMap.get(parent.id) || []
        siblings.forEach(siblingId => {
          visibleIds.add(siblingId)
        })

        current = parent
      }
    }
  })

  return { matchedIds, visibleIds }
}

function highlightMatches(keyword) {
  const matchedIds = new Set()

  nodeMap.forEach((node, id) => {
    if (node.name.includes(keyword)) {
      matchedIds.add(id)
    }
  })

  return matchedIds
}

<template>
  <span v-html="highlightText(node.name, keyword)"></span>
</template>

<script setup>
function highlightText(text, keyword) {
  if (!keyword) return text

  const regex = new RegExp(`(${escapeRegex(keyword)})`, 'gi')
  return text.replace(regex, '<mark>$1</mark>')
}

function escapeRegex(str) {
  return str.replace(/[.*+?^${}()|[\]\\]/g, '\\$&')
}
</script>

<style>
mark {
  background-color: yellow;
  padding: 0 2px;
}
</style>

const searchCache = new Map()
let lastKeyword = ''
let lastResults = null

function optimizedSearch(keyword) {
  // 检查缓存
  if (searchCache.has(keyword)) {
    return searchCache.get(keyword)
  }

  // 增量搜索
  if (lastKeyword && keyword.startsWith(lastKeyword) && lastResults) {
    const filtered = filterResults(lastResults, keyword)
    searchCache.set(keyword, filtered)
    return filtered
  }

  // 完整搜索
  const results = searchTree(keyword)
  searchCache.set(keyword, results)
  lastKeyword = keyword
  lastResults = results

  return results
}

function flattenVisibleNodes(tree) {
  const result = []

  function traverse(nodes, level = 0) {
    nodes.forEach(node => {
      result.push({ ...node, level })

      // 只添加展开的节点的子节点
      if (node.expanded && node.children) {
        traverse(node.children, level + 1)
      }
    })
  }

  traverse(tree)
  return result
}

<template>
  <div
    ref="containerRef"
    class="virtual-tree"
    @scroll="handleScroll"
  >
    <div :style="{ height: totalHeight + 'px' }">
      <div :style="{ transform: `translateY(${offsetY}px)` }">
        <TreeNode
          v-for="node in visibleNodes"
          :key="node.id"
          :node="node"
          :style="{ paddingLeft: (node.level * 20) + 'px' }"
          @toggle="handleToggle"
        />
      </div>
    </div>
  </div>
</template>

<script setup>
import { ref, computed } from 'vue'

const props = defineProps(['tree'])

const containerRef = ref(null)
const scrollTop = ref(0)

const NODE_HEIGHT = 32
const VISIBLE_COUNT = 20
const BUFFER_COUNT = 5

// 扁平化的可见节点
const flatNodes = computed(() => {
  return flattenVisibleNodes(props.tree)
})

// 总高度
const totalHeight = computed(() => {
  return flatNodes.value.length * NODE_HEIGHT
})

// 可视区域的起始索引
const startIndex = computed(() => {
  return Math.max(0, Math.floor(scrollTop.value / NODE_HEIGHT) - BUFFER_COUNT)
})

// 可视区域的结束索引
const endIndex = computed(() => {
  return Math.min(
    flatNodes.value.length,
    startIndex.value + VISIBLE_COUNT + BUFFER_COUNT * 2
  )
})

// 可视区域的节点
const visibleNodes = computed(() => {
  return flatNodes.value.slice(startIndex.value, endIndex.value)
})

// 偏移量
const offsetY = computed(() => {
  return startIndex.value * NODE_HEIGHT
})

// 滚动处理
function handleScroll(e) {
  scrollTop.value = e.target.scrollTop
}

// 展开/折叠处理
function handleToggle(node) {
  node.expanded = !node.expanded
  // flatNodes 会自动重新计算
}
</script>

const flatCache = new Map()

function cachedFlatten(node) {
  if (flatCache.has(node.id)) {
    return flatCache.get(node.id)
  }

  const result = flattenNode(node)
  flatCache.set(node.id, result)
  return result
}

function checkNode(nodeId, checked) {
  const node = nodeMap.get(nodeId)
  node.checked = checked
  node.indeterminate = false

  // 递归更新所有子孙
  const children = getDescendants(nodeId)
  children.forEach(child => {
    child.checked = checked
    child.indeterminate = false
  })

  // 向上更新祖先状态
  updateAncestors(node.parentId)
}

function updateAncestors(nodeId) {
  if (!nodeId) return

  const node = nodeMap.get(nodeId)
  const children = getChildren(nodeId)

  if (children.length === 0) return

  // 统计子节点状态
  const checkedCount = children.filter(c => c.checked).length
  const indeterminateCount = children.filter(c => c.indeterminate).length

  if (checkedCount === children.length) {
    // 所有子节点都选中
    node.checked = true
    node.indeterminate = false
  } else if (checkedCount > 0 || indeterminateCount > 0) {
    // 部分子节点选中
    node.checked = false
    node.indeterminate = true
  } else {
    // 所有子节点都未选中
    node.checked = false
    node.indeterminate = false
  }

  // 继续向上更新
  updateAncestors(node.parentId)
}

// 只返回叶子节点(避免重复)
function getCheckedLeaves() {
  const result = []

  nodeMap.forEach(node => {
    if (node.checked && (!node.children || node.children.length === 0)) {
      result.push(node)
    }
  })

  return result
}

// 返回所有选中的节点(包括父节点)
function getAllChecked() {
  const result = []

  nodeMap.forEach(node => {
    if (node.checked) {
      result.push(node)
    }
  })

  return result
}

// 优化后的获取选中节点
function getCheckedNodes() {
  const result = []

  function traverse(nodeId) {
    const node = nodeMap.get(nodeId)

    if (node.checked) {
      // 如果节点全选,直接返回,不遍历子节点
      result.push(node)
    } else if (node.indeterminate) {
      // 如果节点半选,递归遍历子节点
      const children = getChildren(nodeId)
      children.forEach(child => traverse(child.id))
    }
  }

  // 从根节点开始遍历
  getRoots().forEach(root => traverse(root.id))

  return result
}

class TreeStore {
  constructor() {
    this.nodeMap = new Map()      // id -> node
    this.childrenMap = new Map()  // parentId -> [childIds]
    this.flatNodes = []            // 扁平化的可见节点(用于虚拟滚动)
  }

  // 添加节点 O(1)
  addNode(node) {
    this.nodeMap.set(node.id, node)

    if (!this.childrenMap.has(node.parentId)) {
      this.childrenMap.set(node.parentId, [])
    }
    this.childrenMap.get(node.parentId).push(node.id)
  }

  // 查找节点 O(1)
  getNode(id) {
    return this.nodeMap.get(id)
  }

  // 获取子节点 O(1)
  getChildren(id) {
    const childIds = this.childrenMap.get(id) || []
    return childIds.map(cid => this.nodeMap.get(cid))
  }

  // 获取祖先 O(h) h为树高
  getAncestors(id) {
    const ancestors = []
    let current = this.getNode(id)

    while (current?.parentId) {
      current = this.getNode(current.parentId)
      if (current) ancestors.unshift(current)
    }

    return ancestors
  }

  // 获取后代 O(n) n为子树节点数,但有剪枝优化
  getDescendants(id, maxDepth = Infinity) {
    const descendants = []
    const queue = [{ id, depth: 0 }]

    while (queue.length > 0) {
      const { id, depth } = queue.shift()

      if (depth >= maxDepth) continue

      const children = this.getChildren(id)
      children.forEach(child => {
        descendants.push(child)
        queue.push({ id: child.id, depth: depth + 1 })
      })
    }

    return descendants
  }
}

// 只渲染展开的节点
function getVisibleNodes() {
  const visible = []

  function traverse(nodeId, level = 0) {
    const node = store.getNode(nodeId)
    visible.push({ ...node, level })

    if (node.expanded) {
      const children = store.getChildren(nodeId)
      children.forEach(child => traverse(child.id, level + 1))
    }
  }

  getRootIds().forEach(id => traverse(id))
  return visible
}

// 虚拟滚动,只渲染可视区域
const visibleNodes = computed(() => {
  const all = getVisibleNodes()
  const start = Math.floor(scrollTop.value / nodeHeight)
  const end = start + visibleCount
  return all.slice(start, end)
})

const treeState = {
  expandedKeys: new Set(),  // 展开的节点
  checkedKeys: new Set(),   // 选中的节点
  scrollTop: 0,             // 滚动位置
  activeKey: null,          // 当前激活的节点
}

function compressState(state) {
  const compressed = {
    expanded: [],
    checked: [],
    scroll: state.scrollTop,
    active: state.activeKey
  }

  // 压缩展开状态
  // 如果父节点展开,子节点的状态可以推导,不需要存储
  state.expandedKeys.forEach(id => {
    const node = store.getNode(id)
    const parent = store.getNode(node.parentId)

    // 只存储父节点未展开的节点
    if (!parent || !state.expandedKeys.has(parent.id)) {
      compressed.expanded.push(id)
    }
  })

  // 压缩选中状态
  // 如果父节点全选,子节点的状态可以推导
  state.checkedKeys.forEach(id => {
    const node = store.getNode(id)
    const parent = store.getNode(node.parentId)

    if (!parent || !isAllChildrenChecked(parent.id)) {
      compressed.checked.push(id)
    }
  })

  return compressed
}

function saveState() {
  const compressed = compressState(treeState)
  const json = JSON.stringify(compressed)

  // 如果很大,用 LZ-String 压缩
  if (json.length > 10000) {
    const lzString = LZString.compress(json)
    localStorage.setItem('tree-state', lzString)
  } else {
    localStorage.setItem('tree-state', json)
  }
}

function loadState() {
  const stored = localStorage.getItem('tree-state')
  if (!stored) return

  let compressed
  try {
    // 尝试解压
    const decompressed = LZString.decompress(stored)
    compressed = JSON.parse(decompressed || stored)
  } catch {
    return
  }

  // 恢复展开状态
  compressed.expanded.forEach(id => {
    expandNode(id) // 会自动展开祖先节点
  })

  // 恢复选中状态
  compressed.checked.forEach(id => {
    checkNode(id, true)
  })

  // 恢复滚动位置
  nextTick(() => {
    containerRef.value.scrollTop = compressed.scroll
  })

  // 恢复激活节点
  treeState.activeKey = compressed.active
}

const debouncedSave = debounce(saveState, 1000)

// 状态变化时,延迟保存
watch(() => treeState, debouncedSave, { deep: true })

// 页面关闭时,立即保存
window.addEventListener('beforeunload', saveState)

// 拖拽前检查
function canDrop(dragNode, dropNode, position) {
  const errors = []

  // 1. 检查循环
  if (isDescendant(dropNode.id, dragNode.id)) {
    errors.push('不能拖动到自己的子节点下')
    return { valid: false, errors }
  }

  // 2. 检查层级
  const dragDepth = getTreeDepth(dragNode.id)
  const dropDepth = getNodeLevel(dropNode.id)

  if (position === 'inside') {
    if (dropDepth + dragDepth > MAX_DEPTH) {
      errors.push(`层级不能超过 ${MAX_DEPTH} 层`)
      return { valid: false, errors }
    }
  }

  // 3. 检查节点类型
  if (position === 'inside' && !canAcceptChild(dropNode, dragNode)) {
    errors.push(`${dropNode.type} 类型节点不能包含 ${dragNode.type} 类型`)
    return { valid: false, errors }
  }

  // 4. 检查权限
  if (!hasPermission(dragNode, 'move')) {
    errors.push('没有移动该节点的权限')
    return { valid: false, errors }
  }

  return { valid: true, errors: [] }
}

// 判断是否是子孙节点
function isDescendant(ancestorId, descendantId) {
  if (ancestorId === descendantId) return true

  let current = store.getNode(descendantId)

  while (current?.parentId) {
    if (current.parentId === ancestorId) return true
    current = store.getNode(current.parentId)
  }

  return false
}

// 获取树的深度
function getTreeDepth(nodeId) {
  let maxDepth = 0

  function traverse(id, depth) {
    maxDepth = Math.max(maxDepth, depth)

    const children = store.getChildren(id)
    children.forEach(child => traverse(child.id, depth + 1))
  }

  traverse(nodeId, 1)
  return maxDepth
}

// 获取节点层级
function getNodeLevel(nodeId) {
  let level = 0
  let current = store.getNode(nodeId)

  while (current?.parentId) {
    level++
    current = store.getNode(current.parentId)
  }

  return level
}

// 检查是否可以接受子节点
function canAcceptChild(parent, child) {
  const rules = {
    folder: ['folder', 'file'],
    file: [],  // 文件不能包含子节点
    root: ['folder'],
  }

  return rules[parent.type]?.includes(child.type) || false
}

<div
  class="tree-node"
  :class="{
    'can-drop': canDrop(dragNode, node, dropPosition).valid,
    'cannot-drop': !canDrop(dragNode, node, dropPosition).valid
  }"
  @dragover="handleDragOver"
  @drop="handleDrop"
>
</div>

<style>
.can-drop {
  border: 2px solid green;
  background: rgba(0, 255, 0, 0.1);
}

.cannot-drop {
  border: 2px solid red;
  background: rgba(255, 0, 0, 0.1);
  cursor: not-allowed;
}
</style>

<div v-if="dropError" class="drop-error">
  {{ dropError }}
</div>

// utils/TreeStore.js
export class TreeStore {
  constructor() {
    this.nodeMap = new Map()
    this.childrenMap = new Map()
    this.roots = []
  }

  // 加载树数据
  loadData(data, isFlat = false) {
    if (isFlat) {
      this.loadFlatData(data)
    } else {
      this.loadNestedData(data)
    }
  }

  // 加载扁平数据
  loadFlatData(flatArray) {
    flatArray.forEach(item => {
      this.nodeMap.set(item.id, { ...item })
    })

    flatArray.forEach(item => {
      if (item.parentId === null || item.parentId === undefined) {
        this.roots.push(item.id)
      } else {
        if (!this.childrenMap.has(item.parentId)) {
          this.childrenMap.set(item.parentId, [])
        }
        this.childrenMap.get(item.parentId).push(item.id)
      }
    })
  }

  // 加载嵌套数据
  loadNestedData(tree) {
    const traverse = (nodes, parentId = null) => {
      nodes.forEach(node => {
        const { children, ...rest } = node
        this.nodeMap.set(node.id, { ...rest, parentId })

        if (parentId === null) {
          this.roots.push(node.id)
        } else {
          if (!this.childrenMap.has(parentId)) {
            this.childrenMap.set(parentId, [])
          }
          this.childrenMap.get(parentId).push(node.id)
        }

        if (children && children.length > 0) {
          traverse(children, node.id)
        }
      })
    }

    traverse(Array.isArray(tree) ? tree : [tree])
  }

  // 获取节点
  getNode(id) {
    return this.nodeMap.get(id)
  }

  // 获取子节点
  getChildren(id) {
    const childIds = this.childrenMap.get(id) || []
    return childIds.map(cid => this.nodeMap.get(cid))
  }

  // 获取父节点
  getParent(id) {
    const node = this.nodeMap.get(id)
    return node?.parentId ? this.nodeMap.get(node.parentId) : null
  }

  // 获取祖先路径
  getAncestors(id) {
    const ancestors = []
    let current = this.getNode(id)

    while (current?.parentId) {
      current = this.getParent(current.id)
      if (current) {
        ancestors.unshift(current)
      }
    }

    return ancestors
  }

  // 获取所有后代
  getDescendants(id) {
    const descendants = []
    const queue = [id]

    while (queue.length > 0) {
      const currentId = queue.shift()
      const children = this.getChildren(currentId)

      children.forEach(child => {
        descendants.push(child)
        queue.push(child.id)
      })
    }

    return descendants
  }

  // 添加节点
  addNode(node, parentId = null) {
    this.nodeMap.set(node.id, { ...node, parentId })

    if (parentId === null) {
      this.roots.push(node.id)
    } else {
      if (!this.childrenMap.has(parentId)) {
        this.childrenMap.set(parentId, [])
      }
      this.childrenMap.get(parentId).push(node.id)
    }
  }

  // 删除节点(级联删除)
  deleteNode(id) {
    const node = this.getNode(id)
    if (!node) return

    // 递归删除子节点
    const descendants = this.getDescendants(id)
    descendants.forEach(child => {
      this.nodeMap.delete(child.id)
      this.childrenMap.delete(child.id)
    })

    // 从父节点移除
    if (node.parentId) {
      const siblings = this.childrenMap.get(node.parentId)
      const index = siblings.indexOf(id)
      if (index > -1) {
        siblings.splice(index, 1)
      }
    } else {
      const index = this.roots.indexOf(id)
      if (index > -1) {
        this.roots.splice(index, 1)
      }
    }

    // 删除自身
    this.nodeMap.delete(id)
    this.childrenMap.delete(id)
  }

  // 移动节点
  moveNode(nodeId, newParentId, index = -1) {
    const node = this.getNode(nodeId)
    if (!node) return

    // 检查循环
    if (this.isDescendant(newParentId, nodeId)) {
      throw new Error('Cannot move to descendant')
    }

    // 从原位置移除
    if (node.parentId) {
      const oldSiblings = this.childrenMap.get(node.parentId)
      const oldIndex = oldSiblings.indexOf(nodeId)
      oldSiblings.splice(oldIndex, 1)
    } else {
      const oldIndex = this.roots.indexOf(nodeId)
      this.roots.splice(oldIndex, 1)
    }

    // 添加到新位置
    node.parentId = newParentId

    if (newParentId === null) {
      if (index === -1) {
        this.roots.push(nodeId)
      } else {
        this.roots.splice(index, 0, nodeId)
      }
    } else {
      if (!this.childrenMap.has(newParentId)) {
        this.childrenMap.set(newParentId, [])
      }
      const newSiblings = this.childrenMap.get(newParentId)
      if (index === -1) {
        newSiblings.push(nodeId)
      } else {
        newSiblings.splice(index, 0, nodeId)
      }
    }
  }

  // 判断是否是子孙节点
  isDescendant(ancestorId, descendantId) {
    if (ancestorId === descendantId) return true

    let current = this.getNode(descendantId)

    while (current?.parentId) {
      if (current.parentId === ancestorId) return true
      current = this.getNode(current.parentId)
    }

    return false
  }

  // 搜索节点
  search(keyword, options = {}) {
    const {
      fields = ['name'],
      caseSensitive = false,
    } = options

    const matchedIds = []
    const expandedIds = new Set()

    const searchText = caseSensitive ? keyword : keyword.toLowerCase()

    this.nodeMap.forEach((node, id) => {
      const matched = fields.some(field => {
        const value = node[field]
        if (!value) return false

        const compareValue = caseSensitive ? value : value.toLowerCase()
        return compareValue.includes(searchText)
      })

      if (matched) {
        matchedIds.push(id)

        // 添加祖先节点到展开列表
        let current = node
        while (current.parentId) {
          expandedIds.add(current.parentId)
          current = this.getNode(current.parentId)
        }
      }
    })

    return { matchedIds, expandedIds: Array.from(expandedIds) }
  }

  // 导出为嵌套结构
  toNested(rootIds = this.roots) {
    const buildTree = (nodeIds) => {
      return nodeIds.map(id => {
        const node = this.getNode(id)
        const childIds = this.childrenMap.get(id) || []

        return {
          ...node,
          children: childIds.length > 0 ? buildTree(childIds) : []
        }
      })
    }

    return buildTree(rootIds)
  }

  // 导出为扁平结构
  toFlat() {
    return Array.from(this.nodeMap.values())
  }
}

<!-- components/Tree/Tree.vue -->
<template>
  <div class="tree-container">
    <!-- 搜索框 -->
    <div v-if="showSearch" class="tree-search">
      <input
        v-model="searchKeyword"
        placeholder="搜索..."
        @input="handleSearch"
      />
    </div>

    <!-- 树节点 -->
    <div class="tree-nodes">
      <TreeNode
        v-for="rootId in visibleRoots"
        :key="rootId"
        :node-id="rootId"
        :store="store"
        :expanded-keys="expandedKeys"
        :checked-keys="checkedKeys"
        :selected-key="selectedKey"
        :matched-keys="matchedKeys"
        :show-checkbox="showCheckbox"
        @toggle="handleToggle"
        @check="handleCheck"
        @select="handleSelect"
      />
    </div>
  </div>
</template>

<script setup>
import { ref, computed, watch } from 'vue'
import { TreeStore } from './TreeStore'
import TreeNode from './TreeNode.vue'
import { debounce } from 'lodash-es'

const props = defineProps({
  data: {
    type: Array,
    required: true,
  },
  dataType: {
    type: String,
    default: 'nested', // 'nested' or 'flat'
  },
  showCheckbox: {
    type: Boolean,
    default: false,
  },
  showSearch: {
    type: Boolean,
    default: false,
  },
  defaultExpandAll: {
    type: Boolean,
    default: false,
  },
})

const emit = defineEmits(['check', 'select', 'toggle'])

// 初始化存储
const store = new TreeStore()
store.loadData(props.data, props.dataType === 'flat')

// 状态
const expandedKeys = ref(new Set())
const checkedKeys = ref(new Set())
const selectedKey = ref(null)
const searchKeyword = ref('')
const matchedKeys = ref(new Set())

// 默认全部展开
if (props.defaultExpandAll) {
  store.nodeMap.forEach((node, id) => {
    expandedKeys.value.add(id)
  })
}

// 可见的根节点
const visibleRoots = computed(() => {
  if (searchKeyword.value) {
    // 搜索模式:只显示匹配的节点
    return Array.from(matchedKeys.value)
      .map(id => store.getNode(id))
      .filter(node => !node.parentId || !matchedKeys.value.has(node.parentId))
      .map(node => node.id)
  }
  return store.roots
})

// 展开/折叠
function handleToggle(nodeId) {
  if (expandedKeys.value.has(nodeId)) {
    expandedKeys.value.delete(nodeId)
  } else {
    expandedKeys.value.add(nodeId)
  }
  emit('toggle', nodeId, expandedKeys.value.has(nodeId))
}

// 选中
function handleCheck(nodeId, checked) {
  const node = store.getNode(nodeId)

  // 更新自身
  if (checked) {
    checkedKeys.value.add(nodeId)
  } else {
    checkedKeys.value.delete(nodeId)
  }

  // 向下级联
  const descendants = store.getDescendants(nodeId)
  descendants.forEach(child => {
    if (checked) {
      checkedKeys.value.add(child.id)
    } else {
      checkedKeys.value.delete(child.id)
    }
  })

  // 向上更新
  updateAncestorCheckState(node.parentId)

  emit('check', Array.from(checkedKeys.value))
}

// 更新祖先的选中状态
function updateAncestorCheckState(nodeId) {
  if (!nodeId) return

  const node = store.getNode(nodeId)
  const children = store.getChildren(nodeId)

  if (children.length === 0) return

  const checkedCount = children.filter(c => checkedKeys.value.has(c.id)).length

  if (checkedCount === children.length) {
    checkedKeys.value.add(nodeId)
  } else if (checkedCount > 0) {
    // 半选状态,这里简化处理,直接取消选中
    checkedKeys.value.delete(nodeId)
  } else {
    checkedKeys.value.delete(nodeId)
  }

  updateAncestorCheckState(node.parentId)
}

// 选择
function handleSelect(nodeId) {
  selectedKey.value = nodeId
  emit('select', nodeId)
}

// 搜索
const handleSearch = debounce(() => {
  if (!searchKeyword.value) {
    matchedKeys.value.clear()
    return
  }

  const result = store.search(searchKeyword.value)
  matchedKeys.value = new Set(result.matchedIds)

  // 自动展开匹配节点的祖先
  result.expandedIds.forEach(id => {
    expandedKeys.value.add(id)
  })
}, 300)

// 监听数据变化
watch(() => props.data, (newData) => {
  store.loadData(newData, props.dataType === 'flat')
}, { deep: true })
</script>

<style scoped>
.tree-container {
  padding: 8px;
}

.tree-search {
  margin-bottom: 12px;
}

.tree-search input {
  width: 100%;
  padding: 8px 12px;
  border: 1px solid #d9d9d9;
  border-radius: 4px;
  font-size: 14px;
}

.tree-nodes {
  user-select: none;
}
</style>

<!-- components/Tree/TreeNode.vue -->
<template>
  <div class="tree-node">
    <div
      class="node-content"
      :class="{
        'is-selected': selectedKey === nodeId,
        'is-matched': matchedKeys.has(nodeId)
      }"
      :style="{ paddingLeft: (level * 20) + 'px' }"
    >
      <!-- 展开/折叠图标 -->
      <span
        v-if="hasChildren"
        class="node-expand"
        @click="$emit('toggle', nodeId)"
      >
        {{ isExpanded ? '▼' : '▶' }}
      </span>
      <span v-else class="node-expand-placeholder"></span>

      <!-- 复选框 -->
      <input
        v-if="showCheckbox"
        type="checkbox"
        :checked="checkedKeys.has(nodeId)"
        @change="$emit('check', nodeId, $event.target.checked)"
      />

      <!-- 节点内容 -->
      <div
        class="node-label"
        @click="$emit('select', nodeId)"
      >
        <slot :node="node">
          <span v-html="highlightText(node.name)"></span>
        </slot>
      </div>
    </div>

    <!-- 子节点 -->
    <div v-if="isExpanded && hasChildren" class="node-children">
      <TreeNode
        v-for="childId in childrenIds"
        :key="childId"
        :node-id="childId"
        :store="store"
        :level="level + 1"
        :expanded-keys="expandedKeys"
        :checked-keys="checkedKeys"
        :selected-key="selectedKey"
        :matched-keys="matchedKeys"
        :show-checkbox="showCheckbox"
        @toggle="$emit('toggle', $event)"
        @check="$emit('check', $event, $event)"
        @select="$emit('select', $event)"
      >
        <template #default="{ node: childNode }">
          <slot :node="childNode"></slot>
        </template>
      </TreeNode>
    </div>
  </div>
</template>

<script setup>
import { computed } from 'vue'

const props = defineProps({
  nodeId: {
    type: String,
    required: true,
  },
  store: {
    type: Object,
    required: true,
  },
  level: {
    type: Number,
    default: 0,
  },
  expandedKeys: {
    type: Set,
    required: true,
  },
  checkedKeys: {
    type: Set,
    required: true,
  },
  selectedKey: {
    type: String,
    default: null,
  },
  matchedKeys: {
    type: Set,
    default: () => new Set(),
  },
  showCheckbox: {
    type: Boolean,
    default: false,
  },
})

defineEmits(['toggle', 'check', 'select'])

const node = computed(() => props.store.getNode(props.nodeId))

const childrenIds = computed(() => {
  return (props.store.childrenMap.get(props.nodeId) || [])
})

const hasChildren = computed(() => childrenIds.value.length > 0)

const isExpanded = computed(() => props.expandedKeys.has(props.nodeId))

function highlightText(text) {
  // 如果有搜索关键词,高亮显示
  // 这里简化处理,实际应该从父组件传入
  return text
}
</script>

<style scoped>
.tree-node {
  font-size: 14px;
}

.node-content {
  display: flex;
  align-items: center;
  padding: 4px 8px;
  cursor: pointer;
  border-radius: 4px;
  transition: background 0.2s;
}

.node-content:hover {
  background: #f5f5f5;
}

.node-content.is-selected {
  background: #e6f7ff;
}

.node-content.is-matched {
  background: #fffbe6;
}

.node-expand {
  width: 16px;
  text-align: center;
  cursor: pointer;
  user-select: none;
}

.node-expand-placeholder {
  width: 16px;
  display: inline-block;
}

.node-label {
  flex: 1;
  padding: 0 8px;
}

.node-children {
  /* 子节点容器 */
}
</style>

<!-- views/TreeExample.vue -->
<template>
  <div class="tree-example">
    <h2>树形组件示例</h2>

    <Tree
      :data="treeData"
      data-type="nested"
      show-checkbox
      show-search
      @check="handleCheck"
      @select="handleSelect"
    >
      <template #default="{ node }">
        <span :class="'node-' + node.type">
          {{ node.name }}
        </span>
      </template>
    </Tree>
  </div>
</template>

<script setup>
import { ref } from 'vue'
import Tree from '@/components/Tree/Tree.vue'

const treeData = ref([
  {
    id: '1',
    name: '根节点1',
    type: 'folder',
    children: [
      {
        id: '1-1',
        name: '子节点1-1',
        type: 'folder',
        children: [
          { id: '1-1-1', name: '叶子节点1-1-1', type: 'file' },
          { id: '1-1-2', name: '叶子节点1-1-2', type: 'file' }
        ]
      },
      {
        id: '1-2',
        name: '子节点1-2',
        type: 'file'
      }
    ]
  },
  {
    id: '2',
    name: '根节点2',
    type: 'folder',
    children: [
      { id: '2-1', name: '子节点2-1', type: 'file' }
    ]
  }
])

function handleCheck(checkedKeys) {
  console.log('已选中:', checkedKeys)
}

function handleSelect(nodeId) {
  console.log('已选择:', nodeId)
}
</script>

<style scoped>
.node-folder {
  font-weight: 500;
  color: #1890ff;
}

.node-file {
  color: #666;
}
</style>

function expandAll(nodeIds, maxLevel = Infinity) {
  const queue = nodeIds.map(id => ({ id, level: 0 }))

  while (queue.length > 0) {
    const { id, level } = queue.shift()

    if (level >= maxLevel) continue

    expandedKeys.add(id)

    const children = store.getChildren(id)
    children.forEach(child => {
      queue.push({ id: child.id, level: level + 1 })
    })
  }
}

function checkAll(nodeIds) {
  nodeIds.forEach(id => {
    checkedKeys.add(id)
    const descendants = store.getDescendants(id)
    descendants.forEach(d => checkedKeys.add(d.id))
  })

  // 更新祖先状态
  nodeIds.forEach(id => {
    const node = store.getNode(id)
    updateAncestorCheckState(node.parentId)
  })
}
```"

### Q: 树形数据如何做权限控制?

"我在节点数据里加了 permissions 字段:
```javascript
{
  id: '1',
  name: '敏感文件',
  permissions: {
    read: true,
    write: false,
    delete: false
  }
}

<template>
  <div class="tree-node">
    <span>{{ node.name }}</span>

    <div class="node-actions">
      <button v-if="node.permissions.write" @click="edit">编辑</button>
      <button v-if="node.permissions.delete" @click="del">删除</button>
    </div>
  </div>
</template>

function canDrop(dragNode, dropNode) {
  if (!dragNode.permissions.write) {
    return { valid: false, message: '没有移动权限' }
  }

  if (!dropNode.permissions.write) {
    return { valid: false, message: '目标位置没有写入权限' }
  }

  return { valid: true }
}
```"

### Q: 如何实现树的撤销重做?

"用命令模式,每个操作是一个命令:
```javascript
class AddNodeCommand {
  constructor(node, parentId) {
    this.node = node
    this.parentId = parentId
  }

  execute() {
    store.addNode(this.node, this.parentId)
  }

  undo() {
    store.deleteNode(this.node.id)
  }
}

class DeleteNodeCommand {
  constructor(nodeId) {
    this.nodeId = nodeId
    this.node = null
    this.children = null
  }

  execute() {
    // 保存节点信息用于撤销
    this.node = store.getNode(this.nodeId)
    this.children = store.getDescendants(this.nodeId)

    store.deleteNode(this.nodeId)
  }

  undo() {
    store.addNode(this.node, this.node.parentId)
    this.children.forEach(child => {
      store.addNode(child, child.parentId)
    })
  }
}

// 命令管理器
const commandManager = {
  undoStack: [],
  redoStack: [],

  execute(command) {
    command.execute()
    this.undoStack.push(command)
    this.redoStack = []
  },

  undo() {
    const command = this.undoStack.pop()
    if (command) {
      command.undo()
      this.redoStack.push(command)
    }
  },

  redo() {
    const command = this.redoStack.pop()
    if (command) {
      command.execute()
      this.undoStack.push(command)
    }
  }
}
```"

### Q: 大树的内存占用如何优化?

"主要三个方向:

1. **按需加载** - 懒加载,只加载展开的节点

2. **数据精简** - 只存必要的字段,其他字段按需请求:
```javascript
// 列表只存 id、name、type
{
  id: '1',
  name: '文件',
  type: 'file'
}

// 详情才加载完整信息
async function getNodeDetail(id) {
  const response = await api.getNode(id)
  return response.data // 包含 content、metadata 等
}