Some time ago, I read an article, interviewed more than ten advanced front-end, even (flat data structure to Tree) can not write, mentioned that according to the array to Tree structure, this kind of demand is indeed encountered in the development, especially some Tree graph type of processing. So I thought and sorted out several related algorithms, including common recursion and higher efficiency of the cycle.

The test data

const 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},]const obj = {
  id: 1.name: Department of "1".pid: 0.children: [{id: 2.name: "Department of 2".pid: 1.children: []}, {id: 3.name: "Unit 3".pid: 1.children: [{id: 4.name: "Department of 4".pid: 3.children: [{id: 5.name: Department of "5".pid:4.children: []}]}]}Copy the code

Tips: The following algorithms are implemented in the above data structure, mainly reflecting the ideas, pay attention to the notes

Array to tree

recursive

Defines a method to get all children with the specified ID. Each child recursively calls this method to get children.

/ * * *@param {arr: array Array, id: number parent node ID} 
 * @return {children: array subarray}* /
function getChildren(arr, id) {
  const res = [];
  for (let item of arr) {
    if (item.pid === id) { // Find the child element of the current id
      // Insert child elements, and children for each child are generated by a callbackres.push({... item,children: getChildren(arr, item.id)}); }}return res;
}

getChildren(arr, 0);
Copy the code

Defines a method to get a node with the specified ID. Each element of Node. children calls this method to get a new child element

/ * * *@param {arr: array array, id: number Current element id} 
 * @return {children: array subarray}* /
function getNode(arr, id){
  const node = arr.find(i= > i.id === id); // Find the current element
  node.children = [];
  for(const item of arr) {
    if (item.pid === id) {
      // Add child nodes to the current element. Each child node is called recursivelynode.children.push(getNode(arr, item.id)); }}return node;
}

getChildren(arr, 1);
Copy the code

cycle

Map is used to store array data, and each time the loop processes the corresponding elements, using Pointers to the principle of memory space

/ * * *@param {arr: array, pid: number}
 * @return {obj: object}* /
function fn(arr, pid) {
  const map = new Map(a);// Generate map store elements
  for(const item of arr) {
    if(! map.has(item.id)) {// If there is no current element in map, add and initialize childrenmap.set(item.id, {... item,children: []});
    }
    if (map.has(item.pid)){ // Find the parent element and insert it into children if it exists
      map.get(item.pid).children.push(map.get(item.id));
    } else { // Otherwise initialize the parent element and insert children
      map.set(item.pid, {children: [map.get(item.id)]}); }}return map.get(pid);
}

fn(arr, 0);
Copy the code

Tree to array 【 flat data 】

recursive

/ * * *@param {obj: object, res: array}
 * @return {arr: array}* /
function fn(obj, res = []) { // Default initial result array is []
  res.push(obj); // The current element is pushed
  // If the element contains children, iterate over children and recursively push each child element onto the stack
  if (obj.children && obj.children.length) {
    for(const item ofobj.children) { fn(item, res); }}return res;
}

fn(arr);
Copy the code
/ * * *@param { arr: array } Receives a subarray, which can be called with the constructor '{children: [...] } 'start calling *@return { arr: array }* /
function fn(arr) {
  constres = []; res.push(... arr);// chilren inserts the result array
  for(const item of arr) { // Iterate over the child element, recursively if it contains children
    if(item.children && item.children.length) { res.push(... fn(item.children)) } }return res;
}

fn([children: [obj]]);
Copy the code

cycle

Basically, most recursion can be changed into a loop using the idea of a stack, where each element that needs to be processed is pushed onto the stack, and after processing, it pops out until the stack is empty

/ * * *@param {obj: object} 
 * @return {arr: array}* /
function fn(obj) {
  const stack = [];         // Declare a stack to store elements to be processed
  const res = [];           // Receive the result
  stack.push(obj);          // Push the initial element onto the stack
  while(stack.length) {     // if the stack is not empty, the loop is executed
    const item = stack[0];  // Fetch the top element of the stack
    res.push(item);         // The element itself is pressed into the result array
    stack.shift();          // Pops the current element off the stack
    // If the current element contains child elements, the child elements are pushed onto the stack
    if (item.children && item.children.length) {
      stack.push(...item.children);
    }
  }
  return res;
}

fn(obj);
Copy the code

reference

Interviewed a dozen advanced front-end, even (flat data structure to Tree) can not write out