Как рассчитать сумму детей в общем дереве, используя Javascript - PullRequest
Новая
       52

Как рассчитать сумму детей в общем дереве, используя Javascript

0 голосов
/ 27 марта 2020

enter image description here

Я хочу вычислить сумму дочерних узлов и сохранить ее на родительском узле. Как показано на рисунке синие цифры - сумма детей.

Я пробовал это до сих пор: 

    const tree = {
          name:"Root Node",
          value:0,
          sumOfTheChildren:0,
          children: [
              {

                 name:"A Node",
                 value:10,
                 sumOfTheChildren:0,
                 children:[]
              },

              {

                 name:"B Node",
                 value:10,
                 sumOfTheChildren:0,
                 children:[]
              }

    ]

    }

and so on ....

Итак, в sumOfTheChildren каждого узла я хочу вычислить сумму дочерних элементов (всех узлов-потомков)

, поэтому я Я пытаюсь сделать post-order tree traversal, как это. 

let sum = 0;
function postOrder(root) {
  if (root == null) return;

  root.children.forEach((el) =>{
     postOrder(el);

  });

  sum+=root.value;

  // Here i am not sure how to do this 
  root.sumOfTheChildren+=root.value;

}

postOrder(tree);

Но это не дает требуемого результата. Итак, как мне получить правильную сумму?

1 Ответ

1 голос
/ 27 марта 2020

Лог c может быть упрощен путем рекурсивного вычисления сначала суммы детей, а затем возврата суммы значений детей и значения родителей. 

const tree = {
  name: "Root Node",
  value: 0,
  sumOfTheChildren: 0,
  children: [{

      name: "A Node",
      value: 10,
      sumOfTheChildren: 0,
      children: [{

        name: "D Node",
        value: 35,
        sumOfTheChildren: 0,
        children: []
      }]
    },

    {

      name: "B Node",
      value: 10,
      sumOfTheChildren: 0,
      children: []
    }

  ]
};

function postOrder(root) {
  if (root.children) {
    root.children.forEach(child => {
      root.sumOfTheChildren += postOrder(child);
    });
  }

  return root.sumOfTheChildren + root.value;
}

console.log(postOrder(tree));
console.log(tree);
...