扁平化数组转换成树形?

Question

背景：

需要将扁平化数组转换成树形数组。

比如原始数组如下：

const arr = [  
  {id: 4, pid: 3},  
  {id: 'aa',pid:'a'},
  {id: 1, pid: null},  
  {id: 3, pid: 2},
  {id: 'a',pid: 'a0'},
  {id: 2, pid: 1},
  {id: 'a0',pid: null}  
];  

期望转换后的数据

[
    {
        "id": 1,
        "pid": null,
        "children": [
            {
                "id": 2,
                "pid": 1,
                "children": [
                    {
                        "id": 3,
                        "pid": 2,
                        "children": [
                            {
                                "id": 4,
                                "pid": 3
                            }
                        ]
                    }
                ]
            }
        ]
    },
    {
        "id": "a0",
        "pid": null,
        "children": [
            {
                "id": "a",
                "pid": "a0",
                "children": [
                    {
                        "id": "aa",
                        "pid": "a"
                    }
                ]
            }
        ]
    }
]

Answer 1

js 代码

arr.reduce((o, i) => {
    i = Object.assign(o[i.id] ??= {}, i);
    ((o[i.pid ?? ''] ??= {}).children ??= []).push(i);
    return o;
}, {})['']?.children

结果

[
  {
    "id": 1,
    "pid": null,
    "children": [
      {
        "id": 2,
        "pid": 1,
        "children": [
          {
            "id": 3,
            "pid": 2,
            "children": [
              {
                "id": 4,
                "pid": 3
              }
            ]
          }
        ]
      }
    ]
  },
  {
    "id": "a0",
    "pid": null,
    "children": [
      {
        "id": "a",
        "pid": "a0",
        "children": [
          {
            "id": "aa",
            "pid": "a"
          }
        ]
      }
    ]
  }
]

Answer 2

要最少代码实现这个功能，我也来写一个大家都能看得懂的，各位不服来战：

var arr = [
  { id: 4, pid: 3 },
  { id: 'aa', pid: 'a' },
  { id: 1, pid: null },
  { id: 3, pid: 2 },
  { id: 'a', pid: 'a0' },
  { id: 2, pid: 1 },
  { id: 'a0', pid: null }
];

const tree = arr.map((i) => {
  const target = arr.filter((_i) => _i.pid === i.id)
  i.children = [...target]
  return i
}).filter((i) => !Boolean(i.pid))

console.log(tree);

Answer 3

export const normalTree = data => {
  const map = {}
  const tree = []
  const reduce = (list, item) => {
    const { id, pid, ...child } = item
    child.id = id
    if (!pid) list.push(child)
    map[id] = child
    return list
  }
  data.reduce(reduce, tree)
  const each = item => {
    const { id, pid } = item || {}
    const child = map[pid]
    if (child) {
      const { children } = child
      children
        ? map[pid].children.push(map[id])
        : (map[pid].children = [map[id]])
    }
  }
  data.forEach(each)
  return tree
}

Answer 4

const toTree = (items) => {
    const map = Object.fromEntries(items.map(item => [item.id, item]))
    const roots = []
    items.forEach(item => {
        const { pid } = item
        if (pid === null) {
            roots.push(item)
            return
        }
        const parent = map[pid]
        if (! parent) throw `No item with id "${pid}"`
        ; (parent.children ??= []).push(item)
    })
    return roots
}

Answer 5

type ID = string | number | null
type Item = { id: ID; pid: ID; children?: Item[] }

const mp = new Map<ID, Item>([[null, { id: null, pid: null, children: [] }]])
const set = new Set<Item>(arr)

while (set.size)
    set.forEach(i => {
        const p = mp.get(i.pid)
        if (p) {
            p.children ??= []
            p.children.push(i)
            mp.set(i.id, i)
            set.delete(i)
        }
    })

const transformed = mp.get(null)?.children!

Answer 6

function list2tree(list) {
    const result = [];
    if (list.length) {
        const tree = {};
        let i = 0;
        do {
            const item = list[i];
            const { id, pid } = item;
            const parent = tree[pid];
            let child = tree[id];
            if (!child) {
                child = tree[id] = { ...item };
            } else if (child.pid === void 0) {
                for (const key in item) {
                    child[key] ??= item[key];
                }
            }
            if (pid === null) {
                result.push(child);
            } else if (!parent) {
                tree[pid] = { id: pid, children: [child] };
            } else if (!parent.children) {
                parent.children = [child];
            } else {
                parent.children.push(child);
            }
        } while (++i < list.length);
    }
    return result;
}
console.log(list2tree(arr));

Answer 7

/**
 * 构建包含两个泛型 key 的对象
 */
type Params<P extends string, PP extends string> = {
  [key in P]: string;
} & {
  [key2 in PP]?: string;
};

type AddChildern<T extends ArrayNode<any, any>, C extends string = 'children'> = T & { [key3 in C]: Array<AddChildern<T, C>> };

type ArrayNode<
  P extends string = 'id',
  PP extends string = 'parentId',
> = Params<P, PP>;

type TreeNode<
  T,
  P extends string = 'id',
  PP extends string = 'parentId',
  C extends string = 'children',
> = T extends ArrayNode<P, PP> ? AddChildern<T, C> : never;

export function convertArrayToTree<
  T,
  P extends string = 'id',
  PP extends string = 'parentId',
  C extends string = 'children',
>(
  arr: T extends ArrayNode<P, PP> ? T[] : never,
  id: P = 'id' as P,
  parentId: PP = 'parentId' as PP,
  children: C = 'children' as C,
) {
  const temp: { [str: string]: TreeNode<T, P, PP, C> } = {};
  const tree: TreeNode<T, P, PP, C>[] = [];
  for (let i = 0; i < arr.length; i++) {
    temp[arr[i][id]] = arr[i] as TreeNode<T, P, PP, C>;
  }
  for (let i = 0; i < arr.length; i++) {
    if (temp[arr[i][parentId]]) {
      let childrenValue = temp[arr[i][parentId]][children];
      if (!childrenValue) {
        childrenValue = [] as unknown as TreeNode<T, P, PP, C>[C];
      }
      childrenValue!.push(arr[i] as TreeNode<T, P, PP, C>);
      temp[arr[i][parentId]][children] = childrenValue;
    }
    else {
      tree.push(arr[i] as TreeNode<T, P, PP, C>);
    }
  }
  return tree;
}

支持从传入的数组类型自动推断转换后的树的类型。

const arr = [  
  {id: 4, pid: 3},  
  {id: 'aa',pid:'a'},
  {id: 1, pid: null},  
  {id: 3, pid: 2},
  {id: 'a',pid: 'a0'},
  {id: 2, pid: 1},
  {id: 'a0',pid: null}  
]; 

const tree = convertArrayToTree(arr, 'id', 'pid')
    // ^ {id: number | string, pid: null | number | string, children: {id: number | string, pid: null | number | string, children: ...[]}}

Answer 8

const arr = [
  {id: 4, pid: 3},
  {id: 'aa',pid:'a'},
  {id: 1, pid: null},
  {id: 3, pid: 2},
  {id: 'a',pid: 'a0'},
  {id: 2, pid: 1},
  {id: 'a0',pid: null}
];

function listToTree(list) {
    let map = {}, node, roots = [];
    for (let i = 0; i < list.length; i++) {
        map[list[i].id] = i;
        list[i].children = [];
    }
    for (let i = 0; i < list.length; i++) {
        node = list[i];
        if (node.pid == null) {
            roots.push(node);
        } else {
            list[map[node.pid]].children.push(node);
        }
    }
    return roots;
}

listToTree(arr);

只需要两次循环即可。