树

2024-11-17 13:26:33

数组转树

build-tree.ts

test.ts

test-result.json

          type DeepTreeNode<T> = T & { children: Array<DeepTreeNode<T>> }

interface BuildTreeOptions<T> {
  key: keyof T
  parentKey: keyof T
}

function buildTree<T extends object>(array: T[], options: BuildTreeOptions<T>) {
  const { key, parentKey } = options
  const tree: Array<DeepTreeNode<T>> = []
  const lookup = new Map<T[keyof T], DeepTreeNode<T>>()

  for (const item of array) {
    lookup.set(item[key], { ...item, children: [] })
  }

  for (const item of array) {
    if (item[parentKey]) {
      const parent = lookup.get(item[parentKey])
      if (parent) {
        parent.children.push(lookup.get(item[key]) as DeepTreeNode<T>)
      }
    } else {
      tree.push(lookup.get(item[key]) as DeepTreeNode<T>)
    }
  }

  return tree
}

浅层树

只构建一层父子关系，子孙节点全部扁平化

build-shallow-tree.ts

test.ts

test-result.json

          type TreeNode<T, C = any> = T & { children: C[] }
type ShallowTreeNode<T> = TreeNode<T, T>

interface BuildTreeOptions<T> {
    key: keyof T
    parentKey: keyof T
}

function buildShallowTree<T extends object>(array: T[], options: BuildTreeOptions<T>) {
  const { key, parentKey } = options

  const lookup = new Map<keyof T, ShallowTreeNode<T>>()

  for (const item of array) {
    lookup.set(item[key] as keyof T, { ...item, children: [] })
  }

  function* ancestry(id: keyof T): Generator<keyof T> {
    if (id && lookup.has(id)) {
      yield id
      yield* ancestry(lookup.get(id)![parentKey] as keyof T)
    }
  }

  array.forEach(node => {
    const [ancestor] = [...ancestry(node[parentKey] as keyof T)].reverse()
    if (ancestor && lookup.has(ancestor)) {
      lookup.get(ancestor)!.children.push(lookup.get(node[key] as keyof T)!)
    }
  })

  return Array.from(lookup.values()).filter(node => node[parentKey] === null)
}

统计树节点数量

count-tree-nodes.ts

tree-data.ts

test.ts

          function countTreeNodes<T>(nodes: Array<TreeNode<T>>): number {
  let count = 0

  const traverse = (node: TreeNode<T>) => {
    count++
    for (const child of node.children) {
      traverse(child)
    }
  }

  for (const node of nodes) {
    traverse(node)
  }

  return count
}

树扁平化

flatten-tree.ts

tree-data.ts

test.ts

          function flattenTree<T>(tree: T[], childrenKey: keyof T) {
  const result: Array<Omit<T, keyof T>> = [];

  function recurse(nodes: T[] | undefined) {
    if (!nodes) return;

    for (const node of nodes) {
      const { [childrenKey]: children, ...rest } = node;
      result.push(rest);
      recurse(children as T[]);
    }
  }

  recurse(tree);
  return result;
}

数组转树浅层树统计树节点数量树扁平化