Блог

Главная - Вопросы по программированию - Найти глубину глубокого вложенного массива

Найти глубину глубокого вложенного массива

#javascript #arrays #recursion #nested

#javascript #массивы #рекурсия #вложенный

Вопрос:

У меня есть вложенный массив. Как показано ниже: я хочу найти глубину этого вложенного массива, что означает, что дочерний элемент имеет большинство глубоко вложенных дочерних элементов.

 let arr = [
   {
     name: 'tiger',
     children: [{
       name: 'sinba',
       children: [{
         name: 'cute',
         children: []
        }]
      }]
    },
    {
      name: 'lion',
      children: []
    }
]

В этом случае глубина равна 3, tiger имеет 3 уровня. Итак, глубина равна 3

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

Заранее спасибо.

Ответ №1:

Предполагая, что нет циклических ссылок, вы могли бы попробовать что-то вроде этого

 let arr = [{
    name: 'tiger',
    children: [{
      name: 'sinba',
      children: [{
        name: 'cute',
        children: []
      }]
    }]
  },
  {
    name: 'lion',
    children: []
  }
]

function count(children) {
  return children.reduce((depth, child) => {
    return Math.max(depth, 1   count(child.children)); // increment depth of children by 1, and compare it with accumulated depth of other children within the same element
  }, 0); //default value 0 that's returned if there are no children
}

console.log(count(arr))

Наша функция не работала бы, если бы было несколько циклических ссылок, поэтому, возможно, потребуется соответствующим образом ее настроить. Обнаружение циклических ссылок — это целое испытание. Если с этим ничего не предпринять, функция выдаст ошибку превышения максимального размера стека вызовов.

Для того, чтобы справиться с этим без какой-либо дополнительной реализации функциональности, вы могли бы использовать уже существующий native JSON.stringify для этого. Опция stringify выдаст исключение, только если вы попытаетесь сериализовать BigInt значения, с которыми мы можем справиться сами, или когда объекты являются циклическими, чего мы как раз и хотели.

 let arr = [{
  name: 'tiger',
  children: []
}]

function testCircular(arr){
  try {
    BigInt.prototype.toJSON = function() { return this.toString() } // Instead of throwing, JSON.stringify of BigInt now produces a string
    JSON.stringify(arr);
    return false;
  }
  catch (e) {
    // will only enter here in case of circular references
    return true;
  }
}

function count(children) {
  if (testCircular(children)) return Infinity;
  return children.reduce((depth, child) => {
    return Math.max(depth, 1   count(child.children)); // increment depth of children by 1, and compare it with accumulated depth of other children within the same element
  }, 0); //default value 0 that's returned if there are no children
}

console.log(count(arr)) // normally counting
arr[0].children = arr; // creates circular reference
console.log(count(arr)) // counting for circular

Комментарии:

1. почему Math.max и сравнение?

2. @KunalMukherjee функция уменьшения повторяется по всем дочерним элементам, мне нужно сравнить результаты подсчета дочерних элементов друг с другом, чтобы узнать, у какого из них больше всего, и сохранить информацию только о нем. Конечно, я сравниваю не более 2 элементов одновременно, я, вероятно, мог бы использовать простой оператор if else, но max работает так же хорошо

3. Отличное решение!

4. обратите внимание, что BigInt расширение не будет возвращать JSON.parse большие числа к BigInt . Например, JSON.parse("999999999999999999999999999999999999999999") возвращает 1e 42

5. здесь это используется только для удаления ошибки, а не для фактического анализа данных