Суммируйте дочерние значения и сохраняйте результат в родительский элемент в n-арном дереве в JavaScript

Question

У меня есть дерево в Javascript со следующей структурой, простой пример:

tree: [
    {
      id: 'A'
      parents: []
      children: ['B']
      value: 1
    },
    {
      id: 'B'
      parents: ['A']
      children: ['C', 'D']
      value: 1
    },
    {
      id: 'C'
      parents: ['B']
      children: []
      value: 1
    },
    {
      id: 'D'
      parents: ['B']
      children: []
      value: 1
    }
]

      A
      |
      B
     / \
    C   D

У каждого узла может быть нефиксированное число детей, и я использую массив родителей, чтобы узнать корень дерева(когда массив parent пуст).

Я пытаюсь сделать рекурсивную функцию: сумма дочерних значений сохраняется в родительском (перезаписывая значение).Если есть только один дочерний элемент, дочерний элемент сохраняется в родительском элементе.Таким образом, значения накапливаются в корне.

В порядке ли древовидная структура?Как я могу сделать функцию?

Спасибо.

Редактировать:

Ожидаемый результат:

tree: [
        {
          id: 'A'
          parents: []
          children: ['B']
          value: 2
        },
        {
          id: 'B'
          parents: ['A']
          children: ['C', 'D']
          value: 2
        },
        {
          id: 'C'
          parents: ['B']
          children: []
          value: 1
        },
        {
          id: 'D'
          parents: ['B']
          children: []
          value: 1
        }
    ]

Другой пример:

       A
     /   \
    B     E
   / \    |
  C   D   F

Все значения узлов = 1.

Ожидаемый результат:

tree: [
        {
          id: 'A'
          parents: []
          children: ['B','E']
          value: 3
        },
        {
          id: 'B'
          parents: ['A']
          children: ['C', 'D']
          value: 2
        },
        {
          id: 'C'
          parents: ['B']
          children: []
          value: 1
        },
        {
          id: 'D'
          parents: ['B']
          children: []
          value: 1
        },
        {
          id: 'E'
          parents: ['A']
          children: ['F']
          value: 1
        },
        {
          id: 'F'
          parents: ['E']
          children: []
          value: 1
        }
    ]

Значение A = значение B + значение E.

значение B= Значение C + значение D.

значение E = значение F.

Answer 1

let tree = [
  {
    id: 'A',
    parents: [],
    children: ['B'],
    value: 1
  },
  {
    id: 'B',
    parents: ['A'],
    children: ['C', 'D'],
    value: 1
  },
  {
    id: 'C',
    parents: ['B'],
    children: [],
    value: 1
  },
  {
    id: 'D',
    parents: ['B'],
    children: [],
    value: 1
  }
];
let leafNodes = [];
function ArrayToObject(array, keyField) {
  return array.reduce((obj, item) => {
    obj[item[keyField]] = item;
    if (!item.children.length && !leafNodes.includes(item[keyField])) leafNodes.push(item[keyField]);
    return obj;
  }, {});
}


let treeObject = ArrayToObject(tree, 'id');

addSumToParentNode(leafNodes);

function addSumToParentNode(childNodes) {
  if (childNodes.length) {
    let parentNodes = [];
    childNodes.map(child => {
      if (treeObject[child].parents.length) {
        let parent = treeObject[child].parents[0];
        if (!parentNodes.includes(parent)) parentNodes.push(parent);
        treeObject[parent].value += treeObject[child].value;
      }
    });
    addSumToParentNode(parentNodes);
  }
}

console.log(Object.values(treeObject));

Answer 2

Вы можете хранить ссылки корневых элементов и каждого элемента в хеш-таблице для более быстрого доступа.Затем выполните итерацию корневых элементов для получения требуемой суммы с помощью рекурсии для детей.

Этот подход просто обновляет данный массив.

function update(array) {
    var root = [],
        references = array.reduce((r, o) => {
            if (!o.parents.length) {
                root.push(o.id);
            }
            r[o.id] = o;
            return r;
        }, Object.create(null));
    
    root.reduce(function sum(s, id) {
        var o = references[id];
        return s + (o.value = o.children.reduce(sum, 0) || o.value);
    }, 0);

    return array;
}


var data1 = [{ id: 'A', parents: [], children: ['B'], value: 1 }, { id: 'B', parents: ['A'], children: ['C', 'D'], value: 1 }, { id: 'C', parents: ['B'], children: [], value: 1 }, { id: 'D', parents: ['B'], children: [], value: 1 }],
    data2 = [{ id: 'A', parents: [], children: ['B', 'E'], value: 1 }, { id: 'B', parents: ['A'], children: ['C', 'D'], value: 1 }, { id: 'C', parents: ['B'], children: [], value: 1 }, { id: 'D', parents: ['B'], children: [], value: 1 }, { id: 'E', parents: ['A'], children: ['F'], value: 1 }, { id: 'F', parents: ['E'], children: [], value: 1 }]

console.log(update(data1));
console.log(update(data2));

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

Answer 3

Обратите внимание, что древовидная структура отличается от вашей, но вы также можете вставить другие свойства (например, id ).

const tree = {
    value: 1,
    children: [{
        value: 1,
        children: [{
            value: 1,
            children: null
        },
        {
            value: 1,
            children: null
        }]
    }]
};

function sum(node) {
    var childSum = 0;
    if (!node.children) return node.value;
    for (var i = 0; i < node.children.length; i++) {
        childSum += sum(node.children[i]);
    }
    node.value = childSum;
    return childSum;
}

sum(tree);