创建一个递归函数，将扁平的数组转换为树形数据结构。

Question

我正在尝试编写一个递归函数，将具有值、id和其父节点id的对象的平面数组转换为树形结构，其中结构的子节点是节点数组。子节点需要按id排序，如果是null，则可以是根节点。我尝试编写的函数toTree（data）只应接受数据数组。但我无法在没有父级的情况下完成它。到目前为止，我拥有一个函数（如下），它需要使用数据和父级来开始。

输入:

 const tasks = [
  { id: 1, parent: null, value: 'Make breakfast' },
  { id: 2, parent: 1, value: 'Brew coffee' },
  { id: 3, parent: 2, value: 'Boil water' },
  { id: 4, parent: 2, value: 'Grind coffee beans' },
  { id: 5, parent: 2, value: 'Pour water over coffee grounds' }
];

输出：

{
  id: 1,
  parent: null,
  value: 'Make Breakfast',
  children: [
     {
       id: 2,
       parent: 1,
       value: 'Brew coffee',
       children: [
          { id: 3, parent: 2, value: 'Boil water' },
          { id: 4, parent: 2, value: 'Grind coffee beans' },
          { id: 5, parent: 2, value: 'Pour water over coffee grounds'     }
       ]
     }
  ]
}


funciton toTree(data) {
  customtoTree (data, null);
}

function customToTree (data, parent) {
  const out = [];
  data.forEach((obj) => {
    if (obj.parent === parent) {
      const children = customToTree(data,obj.parent);

      if (children.length) {
        obj[children[0]] = children;
      }
      const {id,parent, ...content} = obj;
      out.push(content);
    }
  });
  return out;
}

我非常希望能够理解如何正确地进行这项操作，思考如何在不显式指定父元素的情况下实现。

- user3064626

---

子节点的父节点是否总是在扁平数组中首先列出，然后才是该子节点？ - CertainPerformance

将 JavaScript 中的平面数组构建成树形数组 - behzad besharati

Answer 1

我在面试中也遇到了同样的问题，一直没有解决。我也很困惑这个函数只应该将数组作为第一个且唯一的参数。

但是后来重新修改它（并得到一个聪明人的非常好的建议），我意识到您可以首先将数组作为第一个且唯一的参数调用函数，然后在递归调用期间传递父级作为第二个参数。

在函数内部，您只需要检查第二个参数是否未定义，如果是，则在数组中搜索您的根对象并将其分配给第二个参数。

所以这是我的解决方案，希望更加清晰： "最初的回答"

function toTree(arr, item) {

        if (!item) {
            item = arr.find(item => item.parent === null)
        }

        let parent = {...item}
        parent.children = 
            arr.filter(x => x.parent === item.id)
                .sort((a, b) => a.id - b.id)
                .map(y => toTree(arr, y))

        return parent     
}

toTree(tasks)

- christophe

Answer 2

如果您的输入已按id排序并且没有子节点可以出现在其父节点之前，则可以在一个循环中完成此操作，甚至不需要递归：

 const tasks = [
  { id: 1, parent: null, value: 'Make breakfast' },
  { id: 2, parent: 1, value: 'Brew coffee' },
  { id: 3, parent: 2, value: 'Boil water' },
  { id: 4, parent: 2, value: 'Grind coffee beans' },
  { id: 5, parent: 2, value: 'Pour water over coffee grounds' }
];

const tasksById = Object.create(null);

// abusing filter to do the work of a forEach() 
// while also filtering the tasks down to a list with `parent: null`
const root = tasks.filter((value) => {
  const { id, parent } = value;
  
  tasksById[id] = value;
  
  if(parent == null) return true;
  
  (tasksById[parent].children || (tasksById[parent].children = [])).push(value);
});

console.log("rootNodes", root);
console.log("tasksById", tasksById);

.as-console-wrapper{top:0;max-height:100%!important}

- Thomas

Answer 3

我无法检查更多的测试用例，但这是我能够快速想出来的东西，可以通过您的用例，看起来不太好，我建议将其用作初始结构，然后再进行改进。此外，我假设任务按父级升序排序，即子任务仅在其父任务之后出现在任务数组中。

const tasks = [
  { id: 1, parent: null, value: 'Make breakfast' },
  { id: 2, parent: 1, value: 'Brew coffee' },
  { id: 3, parent: 2, value: 'Boil water' },
  { id: 4, parent: 2, value: 'Grind coffee beans' },
  { id: 5, parent: 2, value: 'Pour water over coffee grounds' },
  { id: 6, parent: 5, value: 'Pour water over coffee grounds' },
  { id: 7, parent: 5, value: 'Pour water over coffee grounds' }
];

function Tree() {
  this.root = null;
  // this function makes node root, if root is empty, otherwise delegate it to recursive function
  this.add = function(node) {
    if(this.root == null)
      this.root = new Node(node);
    else
      // lets start our processing by considering root as parent
      this.addChild(node, this.root);
  }

  this.addChild = function(node, parent) {
    // if the provided parent is actual parent, add the node to its children
    if(parent.id == node.parent) {
      parent.children[node.id] = new Node(node);
    } else if(parent.children[node.parent]) {
      // if the provided parent children contains actual parent call addChild with that node
      this.addChild(node, parent.children[node.parent])
    } else if(Object.keys(parent.children).length > 0) {
      // iterate over children and call addChild with each child to search for parent
      for(let p in parent.children) {
        this.addChild(node, parent.children[p]);
      }
    } else {
      console.log('parent was not found');
    }
  }
}

function Node (node) {
  this.id = node.id;
  this.parent = node.parent;
  this.value = node.value;
  this.children = {};
}

const tree = new Tree();

// We are assuming that tasks are sorted in ascending order by parent

for(let t of tasks) {
  tree.add(t);
}

console.log(JSON.stringify(tree.root))

如果你有问题，请告诉我。让我们一起解决它。

- Umair Abid