文章/答案/技术大牛

发布

社区首页 >问答首页 >将嵌套的值数组转换为树结构

问将嵌套的值数组转换为树结构
EN

Code Review用户

提问于 2019-04-30 09:51:50

回答 1查看 9.2K关注 0票数 4

我有一个嵌套数组，它表示父级子关系，需要转换为树结构。

示例嵌套数组

list = [
        ['lvl-1 item-1', 'lvl-2 item-1'],
        ['lvl-1 item-1', 'lvl-2 item-1', 'lvl-3 item-1'],
        ['lvl-1 item-1', 'lvl-2 item-1', 'lvl-3 item-2'],
        ['lvl-1 item-2', 'lvl-2 item-1', 'lvl-3 item-1'],
        ['lvl-1 item-2', 'lvl-2 item-2', 'lvl-3 item-2', 'lvl-4 item-1'],
    ]

每个树节点具有以下结构。

{
    name: "item",
    parent: "parent_name",
    children: []
}

嵌套数组中的每个项表示对象中的一个级别。

期望JSON

{
  "name": "0",
  "parent": null,
  "children": [
    {
      "name": "lvl-1 item-1",
      "parent": "0",
      "children": [
        {
          "name": "lvl-2 item-1",
          "parent": "lvl-1 item-1",
          "children": [
            {
              "name": "lvl-3 item-1",
              "parent": "lvl-2 item-1",
              "children": []
            },
            {
              "name": "lvl-3 item-2",
              "parent": "lvl-2 item-1",
              "children": []
            }
          ]
        }
      ]
    },
    {
      "name": "lvl-1 item-2",
      "parent": "0",
      "children": [
        {
          "name": "lvl-2 item-1",
          "parent": "lvl-1 item-2",
          "children": [
            {
              "name": "lvl-3 item-1",
              "parent": "lvl-2 item-1",
              "children": []
            }
          ]
        },
        {
          "name": "lvl-2 item-2",
          "parent": "lvl-1 item-2",
          "children": [
            {
              "name": "lvl-3 item-2",
              "parent": "lvl-2 item-2",
              "children": [
                {
                  "name": "lvl-4 item-1",
                  "parent": "lvl-3 item-2",
                  "children": []
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}

下面的代码是我想出来的，但是还有很大的改进空间。

首先，我循环列表中的每一项及其所有子项。

我将每个级别名称添加到父数组中，以便以后可以导航它以找到现有的子对象。一旦到达子循环的末尾，就会将当前级别添加到父级，以便在下一次迭代中使用。

一旦到达父循环的末尾，我就会检查子程序中是否存在当前名称，如果不存在，则添加它。

这是经过大量尝试和错误产生的，我很难准确地解释它。

谁能帮我检查一下这段代码，更好地理解和改进它。

我在使初始结构工作时遇到了困难，我最终创建了一个冗余对象，其中包含一个children字段，使其与预期的格式相匹配。

任何帮助都将不胜感激。如果有什么事情我没有解释清楚，请告诉我。

list = [
    ['lvl-1 item-1', 'lvl-2 item-1'],
    ['lvl-1 item-1', 'lvl-2 item-1', 'lvl-3 item-1'],
    ['lvl-1 item-1', 'lvl-2 item-1', 'lvl-3 item-2'],
    ['lvl-1 item-2', 'lvl-2 item-1', 'lvl-3 item-1'],
    ['lvl-1 item-2', 'lvl-2 item-2', 'lvl-3 item-2', 'lvl-4 item-1'],
];

console.log(nestedArrayToJson(list));

function nestedArrayToJson(structure) {
    const top_item = '0';

    let data = {
        children: [
            {
                name: top_item,
                parent: null,
                children: [],
            }],
    };

    for(let i = 0; i < structure.length; i++) {
        let parents = [top_item];
        for(let j = 0; j < structure[i].length; j++) {
            let obj = data;
            for(parent of parents) {
                obj = obj.children.find(o => o.name === parent);
            }
            const name = structure[i][j];
            if(!obj.children.find(o => o.name === name)) {
                obj.children.push({
                    name,
                    parent,
                    children: [],
                });
            }
            parents.push(structure[i][j]);
        }
    }

    return data.children[0];
}

更新脚本

list = [
  ['lvl-1 item-1', 'lvl-2 item-1'],
  ['lvl-1 item-1', 'lvl-2 item-1', 'lvl-3 item-1'],
  ['lvl-1 item-1', 'lvl-2 item-1', 'lvl-3 item-2'],
  ['lvl-1 item-2', 'lvl-2 item-1', 'lvl-3 item-1'],
  ['lvl-1 item-2', 'lvl-2 item-2', 'lvl-3 item-2', 'lvl-4 item-1']
]

function createTree(arr, topItem = "Top") {
  const node = (name, parent = null) => ({
    name,
    parent,
    children: []
  });
  const addNode = (parent, child) => {
    parent.children.push(child);

    return child;
  };
  const findNamedNode = (name, parent) => {
    for (const child of parent.children) {
      if (child.name === name) {
        return child
      }
      const found = findNamedNode(name, child);
      if (found) {
        return found
      }
    }
  };

  const top = node(topItem);
  let current;

  for (const children of arr) {
    current = top;
    for (const name of children) {
      const found = findNamedNode(name, current);
      current = found ? found : addNode(current, node(name, current.name));
    }
  }

  return top;
}

console.log(createTree(list, 'lvl-0 item-1'))

javascript

algorithm

array

tree

回答 1

Code Review用户

回答已采纳

发布于 2019-05-01 17:48:44

白话

命名是非常重要的，它首先使用正确的术语。

在使用这个术语时，没有JSON对象这样的东西。有JSON字符串和JSON文件。还有一个内置的JSON对象.它提供了一个API来帮助在对象和JSON字符串之间进行转换

JavaScript使用对象以属性的形式存储数据。

对象可以使用JSON.stringify转换为JSON字符串，也可以使用JSON.parse从JSON字符串创建。并非所有对象都可以转换为JSON，而所有有效的JSON字符串都可以转换为对象。

你的题目毫无意义..。

“将嵌套的值数组转换为JSON对象”

"JSON对象“作为树更有意义

“将嵌套数组转换为树”

风格

变量data和parent应该声明为常量const，因为它们持有的引用不会更改。
JavaScript命名约定是camelCase，尽量避免使用蛇_案例。top_item的名字应该是topItem --使用snake_case的唯一时间是某些类型的常量，在这种情况下，我们使用SNAKE_UPPER_CASE。
在可能的情况下(不需要数组索引)使用for...of循环而不是for(;;)循环

码逻辑

函数

好的代码试图避免在一个函数中做太多的事情。将代码分解为不同的任务，并将这些任务分配给函数，可以在复杂性开始增加时更容易管理。

在两个位置创建节点对象。好的源代码避免重复。避免重复的最有效的方法是创建通过调用完成相同或类似事情的函数。

您需要搜索节点以找到添加新子节点的位置。搜索树的最简单方法是通过递归函数。递归函数利用嵌套数据的相似性来降低代码的复杂性。

避免冗余

不需要将data对象创建为顶级父级。作为data的孩子，data.children[0]可以作为最好的父母。

重写

我们可以重写代码，将其分解成更小的函数。

主要有三种功能。

node创建一个新节点
addNode将一个节点添加到父节点
findNamedNode将找到一个具有名称的节点。如果该节点不存在，则返回undefined。

函数的主体只是迭代每个数组，按名称搜索每个节点。如果找到一个，它就会移动到下一个。如果没有找到节点，则创建并添加一个新节点。

function createTree(structure, topItem = "Top") {
    const node = (name, parent = null) => ({name, parent, children: []});
    const addNode = (parent, child) => (parent.children.push(child), child);
    const findNamedNode = (name, parent) => {
        for (const child of parent.children) {
            if (child.name === name) { return child }
            const found = findNamedNode(name, child);
            if (found) { return found }            
        }
    }
    const TOP_NAME = "Top";
    const top = node(TOP_NAME);
    var current;

    for (const children of structure) {
        current = top;
        for (const name of children) {
            const found = findNamedNode(name, current);
            current = found ? found : addNode(current, node(name, current.name));
        }
    }
    return top;
}

为了确保一切正常工作(没有排字或白痴编码器入侵)，代码片段只在一个简单的数据集上运行一次。

logTree(createTree(data()));

function createTree(structure) {
    const node = (name, parent = null) => ({name, parent, children: []});
    const addNode = (parent, child) => (parent.children.push(child), child);
    const findNamed = (name, parent) => {
        for (const child of parent.children) {
            if (child.name === name) { return child }
            const found = findNamed(name, child);
            if (found) { return found }            
        }
    }
    const TOP_NAME = "Top", top = node(TOP_NAME);
    for (const children of structure) {
        let par = top;
        for (const name of children) {
            const found = findNamed(name, par);
            par = found ? found : addNode(par, node(name, par.name));
        }
    }
    return top;
}



















   function data() { return [['A1', 'B1'],['A1', 'B1', 'C1'],['A1', 'B1', 'C2'],['A2', 'B1', 'C1'],['A2', 'B2', 'C2', 'D1'],['A2', 'B2', 'C2', 'D2'],['A2', 'B2', 'C2', 'D3'],['A2', 'B2', 'C2', 'D4'],['A2', 'B2', 'C2', 'D5'],['A2', 'B3', 'C1', 'D1'],['A3', 'B1', 'C1', 'D1'],['A3', 'B1', 'C1', 'D2'], ['A3', 'B1', 'C1', 'D3']]; }





/*=============================================================================*/
// Support code unrelated to answer
function log(textContent) {
    info.appendChild(Object.assign(document.createElement("div"),{textContent}));
}    
function logTree(parent, indent = "", end) {
    const tail = parent.children.length > 0 ? "┬" : "─";
    if(end){
        log(indent + "└──┬─" + "►parent: " + parent.parent);
        log(indent + "   └" + tail + "►name..: " + parent.name);
        indent +="    ";
    } else {
        log(indent + "├──┬─" + "►parent: " + parent.parent);
        log(indent + "│  └" + tail + "►name..: " + parent.name);
        indent +="│   ";
    }
    var idx = 0;
    for (const child of parent.children) {
        logTree(child, indent, (idx++ === parent.children.length -1));
    }
}

body {background:black}
#info {color:#CC0;font-size:smaller;white-space:pre-wrap;}

<code id="info"></code>

票数 4

页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://codereview.stackexchange.com/questions/219418

复制

相似问题

问将嵌套的值数组转换为树结构
EN

更新脚本

回答 1

Code Review用户

白话

风格

码逻辑

函数

避免冗余

重写

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问将嵌套的值数组转换为树结构EN

更新脚本

回答 1

Code Review用户

白话

风格

码逻辑

函数

避免冗余

重写

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问将嵌套的值数组转换为树结构
EN