数组上的递归深度函数

Question

我有一个像这个输入一样的 objects 数组，我想将一些 objects 嵌套在另一个 objects 中（如果它们的 parentId 是 parents'论坛 ID),

我的功能可以正常工作，但最多 1 个深度，我怎样才能让它在 n 个深度下工作？任何想法或优化表示赞赏！

编辑：指出后，输入不一定有序。

const input = [
  {
    forumId: 1,
    parentId: null,
    forumName: "Main",
    forumDescription: "",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 2,
    parentId: 1,
    forumName: "Announcements",
    forumDescription: "Announcements & Projects posted here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 3,
    parentId: 1,
    forumName: "General",
    forumDescription: "General forum, talk whatever you want here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 4,
    parentId: 3,
    forumName: "Introduction",
    forumDescription: "A warming introduction for newcomers here",
    forumLocked: false,
    forumDisplay: true,
  },
];

function processInput(forumInput) {
  const topLevelForums = forumInput.filter(function (forum) {
    return forum.parentId === null;
  });

  let output = topLevelForums;

  forumInput.forEach(function (forum) {
    if (forum.parentId !== null) {
      const forumParentId = forum.parentId;
      output.forEach(function (parentForum, idx) {
        if (parentForum.forumId === forumParentId) {
          if (!output[idx].hasOwnProperty("subForums")) {
            output[idx].subForums = [];
          }
          parentForum.subForums.push(forum);
        }
      });
    }
  });

  return output;
}

这是预期输出：

[
  {
    forumId: 1,
    parentId: null,
    forumName: "Main",
    forumDescription: "",
    forumLocked: false,
    forumDisplay: true,
    subForums: [
      {
        forumId: 2,
        parentId: 1,
        forumName: "Announcements",
        forumDescription: "Announcements & Projects posted here",
        forumLocked: false,
        forumDisplay: true,
      },
      {
        forumId: 3,
        parentId: 1,
        forumName: "General",
        forumDescription: "General forum, talk whatever you want here",
        forumLocked: false,
        forumDisplay: true,
        subForums: [
          {
            forumId: 4,
            parentId: 3,
            forumName: "Introduction",
            forumDescription: "A warming introduction for newcomers here",
            forumLocked: false,
            forumDisplay: true,
          },
        ],
      },
    ],
  },
]

这是当前输出:

[
  {
    forumDescription: "",
    forumDisplay: true,
    forumId: 1,
    forumLocked: false,
    forumName: "Main",
    parentId: null,
    subForums: [
      {
        forumDescription: "Announcements & Projects posted here",
        forumDisplay: true,
        forumId: 2,
        forumLocked: false,
        forumName: "Announcements",
        parentId: 1,
      },
      {
        forumDescription: "General forum, talk whatever you want here",
        forumDisplay: true,
        forumId: 3,
        forumLocked: false,
        forumName: "General",
        parentId: 1,
      },
    ],
  },
]

Answer 1

您可以获取一个对象，该对象包含从对象到子对象和父对象到子对象的所有关系，并获取没有父对象的节点。

此方法适用于任何深度、未排序的数据，并且仅使用一个循环。

const
    input = [{ forumId: 3, parentId: 1, forumName: "General", forumDescription: "General forum, talk whatever you want here", forumLocked: false, forumDisplay: true }, { forumId: 2, parentId: 1, forumName: "Announcements", forumDescription: "Announcements & Projects posted here", forumLocked: false, forumDisplay: true }, { forumId: 4, parentId: 3, forumName: "Introduction", forumDescription: "A warming introduction for newcomers here", forumLocked: false, forumDisplay: true }, { forumId: 1, parentId: null, forumName: "Main", forumDescription: "", forumLocked: false, forumDisplay: true }],
    tree = function(data, root) {
        var t = {};
        data.forEach(o => {
            Object.assign(t[o.forumId] = t[o.forumId] || {}, o);
            t[o.parentId] = t[o.parentId] || {};
            t[o.parentId].subForums = t[o.parentId].subForums || [];
            t[o.parentId].subForums.push(t[o.forumId]);
        });
        return t[root].subForums;
    }(input, null);

console.log(tree);

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

Answer 2

学习相互递归的绝好机会。输入可以是任意顺序-

function makeIndex (items, indexer)
{ const append = (r, k, v) =>
    r.set(k, (r.get(k) || []).concat([ v ]))

  return items.reduce
    ( (r, i) => append(r, indexer(i), i)
    , new Map
    )
}

function makeTree (index, root = null)
{ const many = (all = []) =>
    all.map(one)

  const one = (forum = {}) =>
    ( { ...forum
      , subforums: many(index.get(forum.forumId))
      }
    )

  return many(index.get(root))
}

const input =
  [{forumId:1,parentId:null,forumName:"Main",forumDescription:"",forumLocked:false,forumDisplay:true},{forumId:2,parentId:1,forumName:"Announcements",forumDescription:"Announcements & Projects posted here",forumLocked:false,forumDisplay:true},{forumId:3,parentId:1,forumName:"General",forumDescription:"General forum, talk whatever you want here",forumLocked:false,forumDisplay:true},{forumId:4,parentId:3,forumName:"Introduction",forumDescription:"A warming introduction for newcomers here",forumLocked:false,forumDisplay:true}]

const result =
  makeTree(makeIndex(input, forum => forum.parentId))

console.log(JSON.stringify(result, null, 2))

[
  {
    "forumId": 1,
    "parentId": null,
    "forumName": "Main",
    "forumDescription": "",
    "forumLocked": false,
    "forumDisplay": true,
    "subforums": [
      {
        "forumId": 2,
        "parentId": 1,
        "forumName": "Announcements",
        "forumDescription": "Announcements & Projects posted here",
        "forumLocked": false,
        "forumDisplay": true,
        "subforums": []
      },
      {
        "forumId": 3,
        "parentId": 1,
        "forumName": "General",
        "forumDescription": "General forum, talk whatever you want here",
        "forumLocked": false,
        "forumDisplay": true,
        "subforums": [
          {
            "forumId": 4,
            "parentId": 3,
            "forumName": "Introduction",
            "forumDescription": "A warming introduction for newcomers here",
            "forumLocked": false,
            "forumDisplay": true,
            "subforums": []
          }
        ]
      }
    ]
  }
]

模块化

上面的 makeIndex 是以一种可以索引任何数据数组的方式编写的，但是 makeTree 做出了像 ...forum、subforums 和 [=19 这样的假设=].当我们考虑模块中的代码时，我们被迫画出分隔线，因此我们的程序变得杂乱无章。

下面，input 定义在 main 中，因此我们在此处保留有关 input 的所有知识 -

// main.js
import { tree } from './tree'

const input =
  [{forumId:1,parentId:null,forumName:"Main",forumDescription:"",forumLocked:false,forumDisplay:true},{forumId:2,parentId:1,forumName:"Announcements",forumDescription:"Announcements & Projects posted here",forumLocked:false,forumDisplay:true},{forumId:3,parentId:1,forumName:"General",forumDescription:"General forum, talk whatever you want here",forumLocked:false,forumDisplay:true},{forumId:4,parentId:3,forumName:"Introduction",forumDescription:"A warming introduction for newcomers here",forumLocked:false,forumDisplay:true}]

const result =
  tree
    ( input                    // <- array of nodes
    , forum => forum.parentId  // <- foreign key
    , (forum, subforums) =>    // <- node reconstructor function
        ({ ...forum, subforums: subforums(forum.forumId) }) // <- primary key
    )

console.log(JSON.stringify(result, null, 2))

当我制作 tree 时，我不想先考虑制作 index。在我们原来的程序中，我怎么知道 tree 需要 index？让 tree 模块来担心 -

// tree.js
import { index } from './index'

const empty =
  {}

function tree (all, indexer, maker, root = null)
{ const cache =
    index(all, indexer)

  const many = (all = []) =>
    all.map(x => one(x))
                             // zero knowledge of forum object shape
  const one = (single) =>
    maker(single, next => many(cache.get(next)))

  return many(cache.get(root))
}

export { empty, tree } // <-- public interface

我们可以直接在 tree 模块中编写 index 函数，但我们想要的行为并不特定于树。编写一个单独的 index 模块更有意义 -

// index.js
const empty = _ =>
  new Map

const update = (r, k, t) =>
  r.set(k, t(r.get(k)))

const append = (r, k, v) =>
  update(r, k, (all = []) => [...all, v])

const index = (all = [], indexer) =>
  all.reduce
      ( (r, v) => append(r, indexer(v), v) // zero knowledge of v shape
      , empty()
      )

export { empty, index, append } // <-- public interface

编写模块可以帮助您将代码分成有意义的部分并提高代码的可重用性。

Answer 3

由于 parents 可能在输入中的 children 之后，我想我可以通过按 ID 构建 Map 论坛，然后添加 children 给他们：

function processInput(forumInput) {
    // Get a map of forums by ID
    const forumsById = new Map();
    for (const forum of forumInput) {
        forumsById.set(forum.forumId, forum);
    }

    // Add child forums to their parents
    for (const forum of forumInput) {
        const {parentId} = forum;
        if (parentId !== null) {
            const parent = forumsById.get(forum.parentId);
            parent.subForums = parent.subForums || []; // Or you could use `?? []` now
            parent.subForums.push(forum);
        }
    }

    // Return the parents array
    return [...forumsById.values()].filter(({parentId}) => parentId === null);
}

实例：

const input = [
  {
    forumId: 1,
    parentId: null,
    forumName: "Main",
    forumDescription: "",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 2,
    parentId: 1,
    forumName: "Announcements",
    forumDescription: "Announcements & Projects posted here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 3,
    parentId: 1,
    forumName: "General",
    forumDescription: "General forum, talk whatever you want here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 4,
    parentId: 3,
    forumName: "Introduction",
    forumDescription: "A warming introduction for newcomers here",
    forumLocked: false,
    forumDisplay: true,
  },
];

function processInput(forumInput) {
    // Get a map of forums by ID
    const forumsById = new Map();
    for (const forum of forumInput) {
        forumsById.set(forum.forumId, forum);
    }

    // Add child forums to their parents
    for (const forum of forumInput) {
        const {parentId} = forum;
        if (parentId !== null) {
            const parent = forumsById.get(forum.parentId);
            parent.subForums = parent.subForums || []; // Or you could use `?? []` now
            parent.subForums.push(forum);
        }
    }

    // Return the parents array
    return [...forumsById.values()].filter(({parentId}) => parentId === null);
}

console.log(processInput(input));

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

请注意，如果某个论坛声称在 parent 论坛中但不在输入中，则上述内容将引发错误。

Answer 4

我认为系统的方法是 1.创建一个id到object的map 2.创建父->子映射 3.将所有父级添加到结果中 4.递归添加子论坛（子论坛）

const input = [
  {
    forumId: 1,
    parentId: null,
    forumName: "Main",
    forumDescription: "",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 2,
    parentId: 1,
    forumName: "Announcements",
    forumDescription: "Announcements & Projects posted here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 3,
    parentId: 1,
    forumName: "General",
    forumDescription: "General forum, talk whatever you want here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 4,
    parentId: 3,
    forumName: "Introduction",
    forumDescription: "A warming introduction for newcomers here",
    forumLocked: false,
    forumDisplay: true,
  },
];

const mapIdToForums = input.reduce((acc, cur) => {
  acc[cur.forumId] = cur;
  return acc;
}, {});

const mapForumsToSubForums = input.reduce((acc, cur) => {
  parentId = cur.parentId || ""; // no parent
  acc[parentId] = acc[parentId] || [];
  acc[parentId].push(cur);
  return acc;
}, {});


const addChildren = (parent) => {
  var children = mapForumsToSubForums[parent.forumId];
  if (children) {
    parent.subForums = children

    children.forEach(c => addChildren(c));
  }
};

results = mapForumsToSubForums[""];
results.forEach(p => addChildren(p));
console.log(results);

Answer 5

作为其他一些答案，我会使用 Map 通过它们的 forumId 来键控节点，然后将子项填充到相应的值中：

let input = [{ forumId: 3, parentId: 1, forumName: "General", forumDescription: "General forum, talk whatever you want here", forumLocked: false, forumDisplay: true }, { forumId: 2, parentId: 1, forumName: "Announcements", forumDescription: "Announcements & Projects posted here", forumLocked: false, forumDisplay: true }, { forumId: 4, parentId: 3, forumName: "Introduction", forumDescription: "A warming introduction for newcomers here", forumLocked: false, forumDisplay: true }, { forumId: 1, parentId: null, forumName: "Main", forumDescription: "", forumLocked: false, forumDisplay: true }];

let root = {};
let map = new Map(input.map(o => [o.forumId, ({...o})]))
map.forEach(o => (p => p.subForms = (p.subForms || []).concat(o))(map.get(o.parentId) || root));
let result = root.subForms;

console.log(result);

Answer 6

有人问这个问题已经有一段时间了，但由于 has been linked in another question而且我觉得它太复杂了，我也会在这里添加我的答案：

让它足够抽象以处理任意树？好的，好的。
输入中 parents/children 的随机顺序？当然可以，为什么不呢。
最重要的是，对输入数组进行一次扫描

function makeTree(input, indexer, maker, root = null) {
  const cache = new Map;
  // get or create (and return) children array for the passed key;
  const getChildrenArray = key => cache.get(key) || cache.set(key, []).get(key);

  for (let item of input) {
    getChildrenArray(indexer(item)).push(
      maker(item, getChildrenArray)
    );
  }
  
  return cache.get(root);
}

const input = [
  {
    forumId: 1,
    parentId: null,
    forumName: "Main",
    forumDescription: "",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 2,
    parentId: 1,
    forumName: "Announcements",
    forumDescription: "Announcements & Projects posted here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 3,
    parentId: 1,
    forumName: "General",
    forumDescription: "General forum, talk whatever you want here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 4,
    parentId: 3,
    forumName: "Introduction",
    forumDescription: "A warming introduction for newcomers here",
    forumLocked: false,
    forumDisplay: true,
  },
];

function makeTree(input, indexer, maker, root = null) {
  const cache = new Map;
  // get or create (and return) children array for the passed key;
  const getChildrenArray = key => cache.get(key) || cache.set(key, []).get(key);

  for (let item of input) {
    getChildrenArray(indexer(item)).push(
      maker(item, getChildrenArray)
    );
  }
  
  return cache.get(root);
}

const result = makeTree(
  input,
  item => item.parentId,
  (item, getChildrenFor) => ({ 
    ...item, 
    subForums: getChildrenFor(item.forumId) 
  }),
  null
);

console.log(result);

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

数组上的递归深度函数

Recursive depth function on an array

javascript

arrays

recursion

object

higher-order-functions