白褶的博客

外观

树节点查找树的路径 ​

const arr = [
  {
    id: '1',
    children: [
      {
        id: '1.1',
        children: [
          { id: '1.1.1', children: [] },
          { id: '1.1.2', children: [] },
        ]
      },
      { id: '1.1', children: [] },
    ]
  },
  {
    id: '1',
    children: [
      { id: '1.3', children: [] },
      { id: '1.2', children: [] },
      { id: '1.2', children: [] },
    ]
  },
  {
    id: '2',
    children: [
      {
        id: '2.1',
        children: [
          { id: '2.1.1', children: [] },
          { id: '2.1.2', children: [] },
        ]
      },
      { id: '2.2', children: [] },
      { id: '2.2', children: [] },
    ]
  }
]
/**
 * 通过树节点查找树的路径
 * @param findCode
 * @return {*[]}
 */

const findTreeArr = (findCode, treeList, callback) => {
  let resultList = []
  const recursive = (findCode, path, data) => {
    if (data.length === 0) {
      return
    }
    for (const item of data) {
      path.push(item)
      if (item.id === findCode) {
        resultList = JSON.parse(JSON.stringify(path))
        return resultList
      }
      const children = Array.isArray(item.children) ? item.children : []
      const result = recursive(findCode, path, children)
      if (result) return result
      path.pop()
    }
    return null
  }
  recursive(findCode, [], treeList)
  return callback(resultList)
}
const x = findTreeArr('1.1.1', arr, (data) => (data.map(item => item.id)))
console.log(x)

数组队列组装成树 ​

const arr = [
  { id: 1, name: '1' },
  { id: 2, name: '2' },
	{ id: 3, name: '3' }
]
// 变为
const result = [
  {
    id: 1,
    name: '1'
    children: [
  		{
      	id: 2,
      	name: '2',
        children: [
      		{
          	id: 3,
          	name: '3'
          }
    		]
      }
    ]
	}
]
/**
 * 将数组队列组装成树
 * @param list
 * @return {*}
 */
const arrayToTree = (list) => {
  const obj = []
  let cur = obj
  const recursive = (path, data) => {
    path.children = [{ ...data, children: [] }]
    return path.children[0]
  }
  for (let i = 0; i < list.length; i++) {
    cur = recursive(cur, list[i])
  }
  return obj['children']
}

树形结构合并相同节点 ​

const arr = [
  {
    name: '1',
    children: [
      {
        name: '1.1',
        children: [
          { name: '1.1.1', children: [] },
          { name: '1.1.1', children: [] },
        ]
      },
      { name: '1.1', children: [] },
    ]
  },
  {
    name: '1',
    children: [
      { name: '1.3', children: [] },
      { name: '1.2', children: [] },
      { name: '1.2', children: [] },
    ]
  },
  {
    name: '2',
    children: [
      {
        name: '2.1',
        children: [
          { name: '2.1.1', children: [] },
          { name: '2.1.1', children: [] },
        ]
      },
      { name: '2.2', children: [] },
      { name: '2.2', children: [] },
    ]
  }
]
/**
 * 树合并
 * @param tree
 * @return {*[]}
 */
const treeIterator = (tree) => {
  const arr = []
  if (!Array.isArray(tree) || !tree.length) return arr
  tree.forEach((e) => {
    const index = arr.findIndex(i => i.code === e.code)
    if (index > -1) {
      arr[index].children = treeIterator([...arr[index].children, ...e.children])
    } else {
      arr.push({ ...e, children: treeIterator(e.children) })
    }
  })
  return arr
}

树形数组添加层级 ​

/**
 * 给树添加层级
 * @param array
 * @param levelName
 * @param childrenName
 * @return {*[]|*}
 */
export const arrayTreeAddLevel = (array, levelName = 'level', childrenName = 'child') => {
  if (!Array.isArray(array)) return []
  const recursive = (array, level = 0) => {
    level++
    return array.map(item => {
      item[levelName] = level
      const child = item[childrenName]
      if (child && child.length) recursive(child, level)
      return item
    })
  }
  return recursive(array)
}

根据内容过滤树形数组 ​

  /**
   * @description 根据内容过滤树形数组
   * @param tree {[*]} tree的数组
   * @param query {string} 搜索内容
   * @param key {string} 对应树节点过滤的字段
   * @param childrenName {string} 对应树节点children字段
   * @return {[*]} 返回过滤后的树形数据
   */
  export function filterTree(tree, query, key, childrenName = 'children') {
    return tree
      .map(node => {
        const matchLabel = node[key].toLowerCase();
        const queryLabel = query.toLowerCase()
        const isMatch = matchLabel.includes(queryLabel);
        const children = node[childrenName] ? filterTree(node[childrenName], queryLabel, key, childrenName) : [];
        return isMatch || children.length > 0 ? { ...node, children } : null;
      })
      .filter(node => node !== null);
  }

扁平数据结构转树结构 ​

let arr = [
    {id: 1, name: '部门1', pid: 0},
    {id: 2, name: '部门2', pid: 1},
    {id: 3, name: '部门3', pid: 1},
    {id: 4, name: '部门4', pid: 3},
    {id: 5, name: '部门5', pid: 4},
]

// 需要变成如下结构

[
  {
    "id": 1,
    "name": "部门1",
    "pid": 0,
    "children": [
      {
        "id": 2,
        "name": "部门2",
        "pid": 1,
        "children": []
      },
      {
        "id": 3,
        "name": "部门3",
        "pid": 1,
        "children": [
            // 结果 ,,,
        ]
      }
    ]
  }
]

常规递归方法（时间复杂度为O(2^n)）：

interface TreeNode {
  id: number;
  name: string;
  pid: number;
  children: TreeNode[];
}
type Tree = TreeNode[]

let arr: Omit<TreeNode, 'children'> = [
  {id: 1, name: '部门1', pid: 0},
  {id: 2, name: '部门2', pid: 1},
  {id: 3, name: '部门3', pid: 1},
  {id: 4, name: '部门4', pid: 3},
  {id: 5, name: '部门5', pid: 4},
]

function getChildren(data: Tree, result: Tree, pid: number): void {
  for (const item of data) {
    if (pid === item.pid) {
      const newTreeNode = { ...item, children: [] }
      result.push(newTreeNode)
      getChildren(data, newTreeNode.children, item.id)
    }
  }
}

Map存储借助遍历对象引用，从Map中查找对应数据（时间复杂度为O(2n)，空间复杂度为O(n)）：

function arrayToTreeMap(items: Tree, rootPid: number) {
  const result = [];   // 存放结果集
  const itemMap: Record<string | number | symbol, TreeNode> = {};

  // 先转成map存储
  for (const item of items) {
    itemMap[item.id] = { ...item, children: [] }
  }

  for (const item of items) {
    const id = item.id;
    const pid = item.pid;
    const treeItem =  itemMap[id];
    if (pid === rootPid) {
      result.push(treeItem);
    } else {
      if (!itemMap[pid]) {
        itemMap[pid]['children'] = []
      }
      itemMap[pid].children.push(treeItem)
    }
  }
  return result;
}

最佳解决方法（时间复杂度为O(n)，空间复杂度为O(n)）：

function arrayToTree(items) {
  const result = [];   // 存放结果集
  const itemMap = {};  //
  for (const item of items) {
    const id = item.id;
    const pid = item.pid;

    if (!itemMap[id]) {
      itemMap[id] = {
        children: [],
      }
    }

    itemMap[id] = {
      ...item,
      children: itemMap[id]['children'] // 直接存储引用地址
    }

    const treeItem =  itemMap[id];

    if (pid === 0) {
      result.push(treeItem);
    } else {
      if (!itemMap[pid]) {
        itemMap[pid] = {
          children: [],
        }
      }
      itemMap[pid].children.push(treeItem)
    }
  }

  return result;
}