javascript - 将D3js树中Json对象的子 Node 下的叶 Node 转换为子项

总体上下文是查找每个父节点（x）和子节点（x1）的叶节点，如果有两个以上的叶节点，则使它们成为子节点的子节点
我试图在Node.js中使用loadash，但是无法获得预期的结果

我有一个JSON数据

{
"Id": "1",
"name": "x",
"parent": "",
"children": [{
        "Id": "2",
        "name": "x1",
        "parent": "1",
        "children": [{
                "Id": "3",
                "name": "x2",
                "parent": "2"
            }, {
                "Id": "4",
                "name": "x3",
                "parent": "2"
            },
            {
                "Id": "5",
                "name": "x4",
                "parent": "2"
            },
            {
                "Id": "6",
                "name": "x5",
                "parent": "2"

            },
            {
                "Id": "7",
                "name": "x6",
                "parent": "2"
            },
            {
                "Id": "8",
                "name": "x7",
                "parent": "2"
            }
        ]
    },
    {
        "Id": "9",
        "name": "x8",
        "parent": "1"
    },
    {
        "Id": "10",
        "name": "x10",
        "parent": "1"
    }, {
        "Id": "11",
        "name": "x9",
        "parent": "1"
    },
    {
        "Id": "12",
        "name": "x11",
        "parent": "1"
    }
]

}

我想更改为以下格式

{
"Id": "1",
"name": "x",
"parent": "",
"children": [{
        "Id": "2",
        "name": "x1",
        "parent": "1",
        "children": [{
                "Id": "3",
                "name": "x2",
                "IC": "Yes",
                "parent": "2",
                "children": [{
                    "Id": "5",
                    "name": "x4",
                    "IC": "Yes",
                    "parent": "2",
                    "children": [{
                        "Id": "7",
                        "parent": "2",
                        "name": "x6"
                    }]
                }]
            },
            {
                "Id": "4",
                "name": "x3",
                "IC": "Yes",
                "parent": "2",
                "children": [{
                    "Id": "5",
                    "name": "x5",
                    "IC": "Yes",
                    "parent": "2",
                    "children": [{
                        "Id": "7",
                        "name": "x7",
                        "IC": "Yes",
                        "parent": "2"
                    }]
                }]
            }
        ]
    },
    {
        "Id": "9",
        "name": "x8",
        "parent": "1",
        "children": [{
            "Id": "10",
            "name": "x10",
            "IC": "Yes",
            "parent": "1"
        }]
    },
    {
        "Id": "11",
        "name": "x9",
        "parent": "1",
        "children": [{
            "Id": "11",
            "name": "x11",
            "parent": "1",
            "IC": "Yes"
        }]
    }
]

}

注意：
1.如果有8个叶节点，则应将其拆分为4 + 4，
2.如果有9个叶节点，则应将其拆分为5 + 4，
3.同样，如果它有13个，则可以分为7 + 6。

任何帮助，将不胜感激
提前致谢

最佳答案

以下代码将获取所有叶节点并从中创建2个偶数分支。输出与您的输出不同，但是您在注释中提到可以从叶节点随机构建分支，并且此代码符合该要求。

const input = {
  "name": "x",
  "children": [
    {
      "name": "x1",
      "children": [
        {
          "name": "x2"
        },
        {
          "name": "x3"
        },
        {
          "name": "x4"
        },
        {
          "name": "x5"
        },
        {
          "name": "x6"
        },
        {
          "name": "x7"
        }
      ]
    },
    {
      "name": "x8"
    },
    {
      "name": "x10"
    },
    {
      "name": "x9"
    },
    {
      "name": "x11"
    }
  ]
};

function cutLeafNodes(node){
  if(!node.children){
    return;
  }

  const leaves = [];
  const branches = [];
  node.children.forEach(child => {
    if(child.children){
      branches.push(child);
    } else {
      leaves.push(child);
    }
  });
  node.children = branches;

  return leaves;
}

function reorderLeaves(nodes){
  if(!nodes){
    return;
  }

  const midpoint = nodes.length / 2;
  const newChildren = [];
  newChildren.push(createAncestry(nodes.splice(0, midpoint)));
  newChildren.push(createAncestry(nodes));
  return newChildren;
}

function createAncestry(nodes){
  let currentChild = nodes[0];
  const firstChild = currentChild;
  for (let i = 1; i < nodes.length; i++) {
    currentChild.children = [nodes[i]];
    currentChild = currentChild.children[0];
  }
  return firstChild;
}

function reorganizeTree(node){
  const leaves = cutLeafNodes(node);

  if(node.children){
    node.children.forEach(child => {
      reorganizeTree(child);
    });
  }

  if(leaves){
    const newBranches = reorderLeaves(leaves);
    newBranches.forEach(branch =>{
      node.children.push(branch);
    })
  }

  return node;
}

const output = reorganizeTree(input);
console.debug(output);