在Javascript的n进制树中求和子级值并将结果保存到父级

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

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

我试图做的是一个递归函数：子值的总和保存在父值中（覆盖该值）。如果只有一个子项，则子项值保存在父项中。因此，这些值累积到根。

树的结构好吗？我怎么做这个功能？

谢谢

编辑：

预期结果：

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