如何将记录列表与 JavaScript 中的父记录指针树结合起来？

Question

我有这样的数据：

const listOfRecords = Array.from({ length: 10000 }, (x, i) => ({ id: i + 1 }))

const treeOfParents = {
  id: 1,
  children: [
    {
      id: 1,
      children: [
        {
          id: 3,
          children: [
            {
              id: 3,
              children: [
                {
                  id: 5,
                },
                {
                  id: 10,
                },
                {
                  id: 17,
                },
                {
                  id: 321,
                },
              ]
            },
          ]
        },
        {
          id: 401,
          children: [
            {
              id: 401,
              children: [
                {
                  id: 405,
                },
                {
                  id: 410,
                },
                {
                  id: 417,
                },
                {
                  id: 499,
                },
              ]
            },
          ]
        },
        {
          id: 1010,
          children: [
            {
              id: 1021,
              children: [
                {
                  id: 1023,
                },
                {
                  id: 1026,
                },
                {
                  id: 1051,
                },
                {
                  id: 1065,
                },
              ]
            },
          ]
        }
      ]
    },
    {
      id: 1099,
      children: [
        {
          id: 1099,
          children: [
            {
              id: 1103,
              children: [
                {
                  id: 1104,
                },
                {
                  id: 1111,
                },
                {
                  id: 1200,
                },
                {
                  id: 1400,
                },
              ]
            },
          ]
        },
        {
          id: 1591,
          children: [
            {
              id: 1591,
              children: [
                {
                  id: 1591,
                },
                {
                  id: 1701,
                },
                {
                  id: 1821,
                },
                {
                  id: 1900,
                },
              ]
            },
          ]
        },
      ]
    }
  ]
}


traverse(treeOfParents)

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

function traverse(tree) {
  const traversed = iterativeDFS(tree)
  let i = 0
  while (i < traversed.length) {
    let current = traversed[i++]
    let next = traversed[i]

    // mutable hack
    current.records = []

    if (!next) return

    // get diff to know how many records to add.
    let diff = next.id - current.id
    let records = listOfRecords.splice(0, diff)
    current.records.push(...records)
  }
}

function iterativeDFS(start) {
  const stack = [start]
  const result = []
  while (stack.length) {
    const node = stack.pop()
    result.push(node)
    node.children?.forEach(child => {
      stack.push(child)
    })
  }
  return result
}

我刚刚通过递增一个ID生成了一个包含10,000条记录的列表，并根据我的数据组成了一棵树，这是一棵部分树。树中的节点按顺序连接到列表中的 ID，但它会在某些点收集块。我的意思是，例如，在深度 3（位置 0.0.0），它从 1 到 3。这意味着在级别 2（位置 0.0），它包括记录 1 和 2。但是然后到深度 4（位置 0.0 .0.0)，没有处理新记录，但是到深度 5（位置 0.0.0.0.0），我们又添加了 2 条记录（id: 5 现在）。所以在深度 4 处，我们应该再添加 2 条记录

所以前几个树节点链接到记录的输出应该是：

const filledTree = {
  id: 1,
  children: [
    {
      id: 1,
      records: [ { id: 1 }, { id: 2 } ],
      children: [
        {
          id: 3,
          children: [
            {
              id: 3,
              records: [ { id: 3 }, { id: 4 } ],
              children: [
                {
                  id: 5,
                  records: [ { id: 5 }, ..., { id: 9 } ],
                },
                {
                  id: 10,
                  records: [ { id: 10 }, ..., { id: 16 } ],
                },
                ...

注意它是如何仅在遍历中的下一个节点发生变化时才添加记录的。并将所有节点添加到 id - 1.

如何在 JavaScript 中为此构建算法？到目前为止（以上）我所拥有的是令人费解的，我感到困惑。

Answer 1

我想是因为我的iterativeDFS错了。任何想法如何解决它？我认为它与递归一起工作：

function traverse(tree) {
  const traversed = collect(tree)
  let i = 0
  while (i < traversed.length) {
    let current = traversed[i++]
    let next = traversed[i]

    // mutable hack
    current.records = []

    if (!next) return

    // get diff to know how many records to add.
    let diff = next.id - current.id
    if (diff) {
      let records = listOfRecords.splice(0, diff)
      current.records.push(...records)
    }
  }
}

function collect(start) {
  const list = []
  recursiveDFS(start, node => list.push(node))
  return list
}

function recursiveDFS(start, callback) {
  callback(start)
  start.children?.forEach(child => {
    recursiveDFS(child, callback)
  })
}

如何将记录列表与 JavaScript 中的父记录指针树结合起来？

How to combine list of records with tree of parent record pointers in JavaScript?

javascript

algorithm

tree-traversal