javascript - 将递归函数转换为 JavaScript 中的迭代

Question

我无法将递归函数转换为迭代。考虑以下函数:

function getTreeDataFromRows (id, rows) {
  let ret_val = []

  for (let i = 0; i < rows.length; i++) {
    let row = rows[i]

    if (id == row.id_parent) {
      let new_element = {
        id:         row.id,
        id_parent:  row.id_parent,
        value:      row.value,
        data:       getTreeDataFromRows(row.id, rows)
      }

      for (let property in row) {
        if ('id' == property || 'id_parent' == property || 'value' == property) {
          continue
        }
        new_element[property] = row[property]
      }

      ret_val.push(new_element)
    }
  }

  return ret_val
}

我有一个类似于此的输入 json:

[{
    "id": "c-1",
    "id_parent": null,
    "value": "Chapter 1"
  },
  {
    "id": "a-1",
    "id_parent": "c-1",
    "value": "Article 1.1"
  },
  {
    "id": "a-2",
    "id_parent": "c-1",
    "value": "Article 1.2"
  },
  {
    "id": "c-2",
    "id_parent": null,
    "value": "Chapter 2"
  },
  {
    "id": "a-21",
    "id_parent": "c-2",
    "value": "Article 2.1"
  },
  {
    "id": "a-22",
    "id_parent": "c-2",
    "value": "Article 2.2"
  },
  {
    "id": "a-221",
    "id_parent": "a-22",
    "value": "Quote 221 from article 2.2"
  },
  {
    "id": "a-222",
    "id_parent": "a-22",
    "value": "Quote 222 from article 2.2"
  }
]

输出必须是这样的:

[{
    "id": "c-1",
    "id_parent": null,
    "value": "Chapter 1",
    "data": [{
        "id": "a-1",
        "id_parent": "c-1",
        "value": "Articole 1.1",
        "data": []
      },
      {
        "id": "a-2",
        "id_parent": "c-1",
        "value": "Articole 1.2",
        "data": []
      }
    ]
  },
  {
    "id": "c-2",
    "id_parent": null,
    "value": "Chapter 2",
    "data": [{
        "id": "a-21",
        "id_parent": "c-2",
        "value": "Articole 2.1",
        "data": []
      },
      {
        "id": "a-22",
        "id_parent": "c-2",
        "value": "Articole 2.2",
        "data": [{
            "id": "a-221",
            "id_parent": "a-22",
            "value": "Quote 221 from article 2.2",
            "data": []
          },
          {
            "id": "a-222",
            "id_parent": "a-22",
            "value": "Quote 222 from article 2.2",
            "data": []
          },
        ]
      },
    ]
  }
]

树表需要此输出。处理大量数据时，递归函数会出现“超出最大调用堆栈大小”错误。该树也可以有大量的 child (儿子、孙子等)。我尝试使用堆栈数组编写一个for循环，但没有成功。我很困惑，我的代码也可能很困惑。

function functionWithIteration (rows) {
  var my_stack = [null]
  var final_val = []

  while( my_stack.length > 0 ) {
    var ret_val = []
    var first_time = true
    var id = my_stack.pop()
    var temp_val = []
    for (let i = 0; i < rows.length; i++) {

      var row = rows[i]
      var signal = true
      if (id == row.id_parent) {
        signal = false
        var new_element = {
          id: row.id,
          id_parent: row.id_parent,
          value: row.value,
          data: []
        }

        for (let property in row) {
          if (property == 'id' || property == 'id_parent' || property == 'value') {
            continue
          }
          new_element[property] = row[property]
        }

        if (first_time){
          ret_val.push(new_element)
          first_time = false
        }
        else {
          ret_val[ret_val.length - 1].data.push(new_element)
        }
      }
      if ( signal) {
        temp_val.push(ret_val)
        my_stack.push(row.id)
      }
    }
    final_val.push(temp_val)
  }

  return final_val
}

任何帮助将不胜感激!谢谢!

Answer 1

一旦您弄清楚了保存对象引用的简单步骤，这是一个相当简单的解决方案。循环数组并创建一个以元素 id 作为键的对象。您可以使用它来引用该元素以添加其子元素。

var data = [{
    "id": "c-1",
    "id_parent": null,
    "value": "Chapter 1"
  },
  {
    "id": "a-1",
    "id_parent": "c-1",
    "value": "Article 1.1"
  },
  {
    "id": "a-2",
    "id_parent": "c-1",
    "value": "Article 1.2"
  },
  {
    "id": "c-2",
    "id_parent": null,
    "value": "Chapter 2"
  },
  {
    "id": "a-21",
    "id_parent": "c-2",
    "value": "Article 2.1"
  },
  {
    "id": "a-22",
    "id_parent": "c-2",
    "value": "Article 2.2"
  },
  {
    "id": "a-221",
    "id_parent": "a-22",
    "value": "Quote 221 from article 2.2"
  },
  {
    "id": "a-222",
    "id_parent": "a-22",
    "value": "Quote 222 from article 2.2"
  }
]

// we use reduce to loop over the object to build up our new object.
var result = data.reduce((obj, itm) => {
  // store it into a obj so we can reference it
  obj.temp[itm.id] = itm
  // check to see if we have a parent
  if (itm.id_parent) {
    // if we have a parent see if data is set yet
    // if not, set it to an empty array
    obj.temp[itm.id_parent].data = obj.temp[itm.id_parent].data || []
    // push the child into the parent
    obj.temp[itm.id_parent].data.push(obj.temp[itm.id])
  } else {
    // If we have no parent, than it is a root element
    // or we push it into an array to keep track of it
    obj.order.push(obj.temp[itm.id])
  }
  // return the object for reduces next iteration
  return obj
}, { temp:{}, order:[]}) // init recude with an empty object and array
  .order  // return the order

console.log(result)

此解决方案期望 parent 出现在 child 面前。如果情况并非如此，您可以采取以下措施。无论哪种方式，您都会创建一个“临时”对象，直到找到真正的对象。