javascript - 数组上的递归深度函数

Question

我有一个像这个输入这样的对象数组，我想将一些对象嵌套在另一个对象中(基于它们的 parentId 是否是 parent 的 forumId)，

我得到了这个函数，但深度最多为 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

一个学习相互递归的绝好机会。输入可以是任意 命令 -

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 , 和 forum.forumId .当我们在模块中考虑我们的代码时，我们被迫画出分隔线，因此我们的程序变得清晰。

下面， 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

我们可以写 index函数直接在 tree模块，但我们想要的行为并不特定于树。写一个单独的 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

编写模块可以帮助您从有意义的部分思考您的代码，并提高代码的高度可重用性。