Javascript-форум (https://javascript.ru/forum/)
-   Общие вопросы Javascript (https://javascript.ru/forum/misc/)
-   -   Рекурсия при обходе дерева (https://javascript.ru/forum/misc/68941-rekursiya-pri-obkhode-dereva.html)

maternik 18.05.2017 20:53

Рекурсия при обходе дерева
 
Я сочиняю функию , которая получает массив mas (он задаёт структуру дерева) и массив с параметрами param, которые нужно сложить по правилу в зависимости от заданной структуры дерева. Для приведённого примера ввода на выход приходит массив сумм [ 5, 4, 3, 2, 1, 2, 1, 2, 1 ], а ожидался [ 9, 8, 7, 2, 1, 2, 1, 2, 1 ]. Причина в цикле, в котором происходит рекурсивный вызов функции. Цикл выполняется, но набранная сумма теряется. Как это исправить?
onload = function() {
var mas2=[[1],[2],[3,5,7],[4],[],[6],[],[8],[]]; 
var param=[1,1,1,1,1,1,1,1,1];
var out=[],f=0;
var N=param.length; 
for (var i=0; i<N;i++){
  out[i]=recurs(i);
}
console.log(out);
function recurs(i){ 
  if (mas2[i].length==0) { 
    f= param[i] ;
  } else{
    var Nc=mas2[i].length;
    for (var j=0; j<Nc; j++){ 
      f= param[i]+
	  recurs(mas2[i][j]);
    }
 }
 
 return f;
 }
 
 }

Массив mas задаёт следующее правило: в его i-м элементе находятся номера элементов, которые являются дочерними для i-го. Так как в массиве param все единицы, то функция вернёт количество элементов от i-го до концевого, которые находятся в цепочке под i-м.

рони 18.05.2017 21:17

:write: подожду переводчика

maternik 18.05.2017 21:37


Первый элемент выходного массива получается при обходе дерева как на рисунке: начинаем с элемента с номером 0, каждый следующий даёт +1. Должно получиться 9.
Второй элемент выходного массива получится аналогично, но начнём с элемента с номером 1, поэтому сумма будет 8 и т.д.
В цикле затираются суммы для веток 3-4 и 5-6, поэтому в сумме не 9, а 5. Вот как бы

рони 18.05.2017 21:59

maternik,
var mas2 = [
        [1],
        [2],
        [3, 5, 7],
        [4],
        [],
        [6],
        [],
        [8],
        []
    ];
    var param = [1, 1, 1, 1, 1, 1, 1, 1, 1];
    var out = [];
    var N = param.length;
    for (var i = 0; i < N; i++) out[i] = recurs(i);
    alert(out);

    function recurs(i) {
        var f = param[i];
        if (mas2[i].length) {
            var Nc = mas2[i].length;
            for (var j = 0; j < Nc; j++) f += recurs(mas2[i][j])
        }
        return f
    }


Часовой пояс GMT +3, время: 09:22.