Построить дерево из пар ребер и root

Question

Я пытаюсь написать программу, которая берет массив пар ребер и превращает его в дерево. Мне дали root. В этом примере root равен 2.

Единственное ограничение: каждый узел может иметь максимум 2 дочерних элементов.

Пример ввода:

[[1,2],[2,3],[3,4],[1,5]]

Ожидаемый результат :

{
   "id":2,
   "children":[
      {
         "id":1,
         "children":[
            {
               "id":5
            }
         ]
      },
      {
         "id":3,
         "children":[
            {
               "id":4
            }
         ]
      }
   ]
}
enter code here

Будет выглядеть примерно так:

       2
      / \
     1   3
    /     \    
   5       4

Это моя попытка:

  const tree = {};
  const edgePairs = [[1, 2], [2, 3], [3, 4], [1, 5]];
  let root = 2;
  let children;

  function hasTwoChildren(node) {
    let counter = 0;
    for (const i in edgePairs) {
      if (edgePairs[i].includes(node)) counter++;
    }
    return counter === 2;
  }

  function getChildren(root) {
    const children = [];
    for (let i = 0; i < edgePairs.length; i++) {
      if (edgePairs[i][0] === root) children.push(edgePairs[i][1]);
      if (edgePairs[i][1] === root) children.push(edgePairs[i][0]);
    }
    return children;
  }

  function makeTree(tree, root) {
    if (tree.id === undefined) {
      tree.id = root;
    } else if (hasTwoChildren(root)) {
      children = getChildren(root);
      tree.children = makeTree(tree, children[0]);
      makeTree(tree, children[1]);
    } else {
      makeTree(tree, children[0]);
    }
    return tree;
  }

  for (const i in edgePairs) {
    makeTree(tree, root);
  }

Мне кажется, что это должно быть довольно просто, но я что-то упустил .. Любая помощь? :)

Answer 1

Ух, я люблю этот вопрос. И это тоже довольно сложно! Это был мой первый случай рекурсивного подхода к определенной проблеме. И я думаю, что мне удалось понять это.

let root = 2;

// more complicated data (with 1 branch that doesn't connect to any other node)
let nodes = [[1, 2], [2, 3], [3, 4], [1, 5], [1, 6], [2, 8], [100, 101]];


function createTree(root, nodes){
    
    let children = [];
    for (let i = 0; i < nodes.length; i++){
        const index_of_root = nodes[i].indexOf(root)
        if (index_of_root !== -1){
            children.push(nodes[i][Number(!index_of_root)]); // note that data like [1,2,4] or [1] will not work.
            nodes.splice(i, 1);
            i--; // after removing the element, decrement the iterator
        }
    }

    let tree = { 
        id:  String(root)
    };

    if (children.length !== 0){ // if there are any children, 
        tree.children = [];     // add the children property to the tree object
        for (let child of children){ 
            tree.children.push(createTree(child, nodes)); // then add the tree of each of the children
        }
    }
    return tree;
}    

console.log(createTree(root, nodes));

Обычно, когда функция createTree() замечает, что есть какой-либо узел, связанный с root, она создает объект дерева со свойством children. Это дочернее свойство заполняется всеми деревьями, возвращенными каждым из детей, связанных с root.

Если дочерних элементов нет, он просто возвращает объект дерева без дочерних элементов. Честно говоря, мой код может быть немного трудным для чтения из-за того, что он рекурсивный, поэтому он может помочь напечатать некоторые значения в середине функции.

Теперь этот с ограничением (только то, что if (index_of_root !== -1){ заменяется на if (index_of_root !== -1 && children.length !== 2){):

let root = 2;

// more complicated data (with 1 branch that doesn't connect to any other node)
let nodes = [[1, 2], [2, 3], [3, 4], [1, 5], [1, 6], [2, 8], [100, 101]];


function createTree(root, nodes){
    
    let children = [];
    for (let i = 0; i < nodes.length; i++){
        const index_of_root = nodes[i].indexOf(root)
        if (index_of_root !== -1 && children.length !== 2){
            children.push(nodes[i][Number(!index_of_root)]); // note that data like [1,2,4] or [1] will not work.
            nodes.splice(i, 1);
            i--; // after removing the element, decrement the iterator
        }
    }

    let tree = { 
        id:  String(root)
    };

    if (children.length !== 0){ // if there are any children, 
        tree.children = [];     // add the children property to the tree object
        for (let child of children){ 
            tree.children.push(createTree(child, nodes)); // then add the tree of each of the children
        }
    }
    return tree;
}    

console.log(createTree(root, nodes)); //notice how [2, 8] pair is excluded from the tree

Надеюсь, это помогло. Ура :) 1022 *