Преобразовать рекурсивную функцию в итерацию в 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": []
          },
        ]
      },
    ]
  }
]

Этот вывод необходим для древовидной таблицы.Рекурсивная функция выдает ошибку «Превышен максимальный размер стека вызовов» при обработке большого количества данных.Также на дереве может быть большое количество детей (сын, внук и т. Д.).Я пытался написать цикл для, используя массив стека, но мне это не удалось.Я немного сбит с толку, и мой код также может сбивать с толку.

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

Это довольно простое решение, когда вы разберетесь с простым шагом удержания ссылок на объекты. Зациклите массив и создайте объект с идентификатором элемента в качестве ключа. Вы используете это для ссылки на элемент, чтобы добавить его потомков.

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)

Это решение предполагает, что родители предстанут перед своими детьми. Если это не так, то есть несколько вещей, которые вы можете сделать. В любом случае вы создаете временный объект, пока не найдете настоящий.

Answer 2

Я думаю, что в вашей логике есть ошибка.Когда он повторяется, кажется, что он начинается с с самого начала. Интуитивно это позволит рекурсивному экземпляру наткнуться на точно такое же состояние, как и раньше, и, таким образом, будет повторяться до бесконечности. (ВС точки зрения логики, несколько вложенных экземпляров заканчиваются одним и тем же значением для переменной цикла i.)

Answer 3

Вы можете использовать однопетлевой подход с объектом для известных идентификаторов и родителей.

Это решение не ожидает данных в отсортированном порядке.

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" }],
    tree = function (data, root) {
        var o = {};
        data.forEach(function (a) {
            if (o[a.id] && o[a.id].children) {
                a.children = o[a.id].children;
            }
            o[a.id] = a;
            o[a.id_parent] = o[a.id_parent] || {};
            o[a.id_parent].children = o[a.id_parent].children || [];
            o[a.id_parent].children.push(a);
        });
        return o[root].children;
    }(data, null);

console.log(tree);

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