Преобразование плоского определенного дерева в дерево глубины, JavaScript

Question

Для входного плоского дерева:

let input = [{
        levelId: '1'
    }, {
        levelId: '1.1'
    }, {
        levelId: '1.1.1'
    }, {
        levelId: '1.2'
    }, {
        levelId: '2'
    }, {
        levelId: '2.1.1'
    }
]

Как лучше всего преобразовать это в многоуровневое дерево, где levelId определяет уровень дерева:

let output = [{
        levelId: '1',
        children: [{
                levelId: '1.1',
                children: [{
                        levelId: '1.1.1'
                    }
                ]
            }
        ]
    }, {
        levelId: '2',
        children: [{
                levelId: '2.1.1'
            }
        ]
    }
]

Используется Lodash.

Answer 1

Сначала я сортирую массив в соответствии с уровнем объекта, затем создаю промежуточный объект для сопоставления каждого идентификатора уровня с самим объектом и нахожу его родителя из промежуточного объекта. Затем я вывожу массив с объектом, у которого нет родителя.

Надеюсь, что это поможет.

var input = [
  {
	levelId: '1'
  },
  {
	levelId: '1.1'
  },
 {
	levelId: '1.1.1'
  },
  {
	levelId: '1.2'
  },
  {
	levelId: '2'
  }, 
  {
	levelId: '2.1.1'
  },
  {
	levelId: '3.1'
  },
  {
	levelId: '3.1.1'
  }
];


function exec(input){

	var temp = {};
	
	//Sort the array by level then create an intermediate object that map level id with the level object and map with its parent
	input.sort((a,b) => a.levelId.split(".").length - b.levelId.split(".").length).forEach( lvl => {
		temp[lvl.levelId] = lvl;
		
		if(lvl.levelId.indexOf('.') !== -1){
			var parentLevelId = lvl.levelId;
			var parent = undefined;
			//Search parent level by level (ie. 3.1.1 -> 3.1 -> 3)
			do{
				if(parentLevelId.indexOf('.') === -1) break;
				parentLevelId = parentLevelId.substr(0, parentLevelId.lastIndexOf("."));
				parent = temp[parentLevelId];
			}while(typeof parent === 'undefined')
			
			if(typeof parent !== 'undefined'){
				if(typeof parent.children === 'undefined'){
					parent.children = [];
				}
				parent.children.push(lvl);
				lvl.parent = parent;
			}
		}
	});
	
	
	//push the root object (level object that has no parent) to an output array
	var output = [];
	for(var key in temp){
		if(typeof temp[key].parent !== 'undefined'){
			delete temp[key]["parent"];
		}else{
			output.push(temp[key]);
		}
	}

	return output;

}


console.log(JSON.stringify(exec(input), 0, 3));

Answer 2

Другой подход:

• на первом проходе, построить дерево из узлов, как вы найдете их на входе.
• Затем за второй проход реорганизуйте все узлы, родительские узлы которых существуют в дереве.

Код:

let input = [{
        levelId: '1'
    }, {
        levelId: '2.1.1'
    }, {
        levelId: '2.1.1.2.5'
    }, {
        levelId: '1.1'
    }, {
        levelId: '1.2'
    }, {
        levelId: '2'
    }, {
        levelId: '1.1.1.1.1'
    }, {
        levelId: '3.1.1.1.1'
    }
]

console.log(JSON.stringify(treeify(input)))

function treeify(input) {

  let built = {},
      result = { levelId:"", children:[] };

// First pass: build the tree in the order you encounter the nodes:  
  buildTree();
// Second pass: look for children already having an ancestor   
  reorganize(result);  
// For return value, start with list of top level nodes    
  return result.children

// --- First pass: build tree from flat list
  function buildTree() {
    for (let o of input) {
      let parentId = getParentId(o.levelId);
      addChild(built[parentId]||result,o);
      built[o.levelId] = o;
    }
  }

// --- Second pass: switch parents if found
  function reorganize(node) {
    if (!("children" in node)) return;
// Backward loop, as items will be removed during the loop    
    for (let i=node.children.length-1;i>=0;i--) {      
      let c = node.children[i];
// Attach node to first ancestor found      
      for(let parentId = getParentId(c.levelId);parentId;parentId=getParentId(parentId)) {
        if (parentId in built) {
          if (built[parentId]==node) {
            break;  // Already in right position
          }
          addChild(built[parentId],c);
          node.children.splice(i,1);
          break;
        }
      }
    }
// Do it recursively on all child nodes    
    node.children.forEach(reorganize);    
  }

// --- Insert a child    
  function addChild(parent,child) {
    if (!("children" in parent)) {
      parent.children = [];
    } 
    parent.children.push(child);
  }

// --- Determine parent id (by splitting off the last segment of the ID)
  function getParentId(id) {
    return id.replace(/^\d+$|\.\d+$/,"")
  }

}