在Javascript中将子节点值并将结果保存到n-ary树中的父节点 [英] Sum children values and save result to parent in n-ary tree in Javascript

问题描述

我在Javascript中有一个具有以下结构的树，一个简单的例子：

I have a tree in Javascript with the following structure, a simple example:

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

每个节点都可以拥有一个不确定数量的子节点，我正在使用parents数组来知道树根（当父数组为空时）。

Every node can have an unfixed number of children, and I'm using the parents array to know the tree root (when the parents array is empty).

我正在尝试做什么是一个递归函数：子值的总和保存在父级中（覆盖该值）。如果只有一个子节点，则子节点值将保存在父节点中。所以值累积到根。

What I'm trying to do is a recursion function: the sum of the child values is saved in the parent (overwriting the value). If there is only one child, the child value is saved in the parent. So the values accumulate to the root.

树结构是否正常？我该怎么做这个功能？

Is the tree structure fine? How can I do the function?

谢谢。

编辑：

预期结果：

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价值。

A value = B value + E value.

B值= C值+ D值。

B value = C value + D value.

E值= F值。

推荐答案

您可以存储根元素的引用以及哈希表中的每个项目，以便更快地访问。然后通过对子项使用递归来迭代根元素以获得所需的总和。

You could store the reference of the root elemnts as well as every item in a hash table for faster access. Then iterate the root elements for getting the wanted sum by using recursion for the children.

这种方法只是更新给定的数组。

This approach just updates the given array.

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; }

这篇关于在Javascript中将子节点值并将结果保存到n-ary树中的父节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！