在PHP中树数组中所有节点的总值

huangapple go评论59阅读模式
英文:

The sum value of all nodes in the tree array in php

问题

我有一个类似的扁平数组

[
    {
        "id": "1",
        "parentId": "0",
        "cost": 1000
    },
    {
        "id": "2",
        "parentId": "1",
        "cost": 2000
    },
    {
        "id": "3",
        "parentId": "2",
        "cost": 4000
    },
    ...
]

要求:

  • 将扁平数组转换为树状数组 --> (已完成)
  • 每个id的总和是它和其子元素的总价格

现在问题出现了:

  • 应该在从扁平数组转换为树状数组之前还是之后执行求和操作?

这是我尝试将扁平数组转换为树状数组的代码:

public function buildTree(array $flat)
{
    $grouped = [];
    $fnBuilder = function ($companies) use (&$fnBuilder, $grouped) {
        foreach ($companies as $k => $company) {
            $id = $company['id'];
            if (isset($grouped[$id])) {
                $company['children'] = $fnBuilder($grouped[$id]);
            }
            $companies[$k] = $company;
        }
        return $companies;
    };
    return $fnBuilder($grouped[0]);
}

我的期望结果如下:

[
    {
        "id": "1",
        "sum": 7000,
        "children": [
            {
                "id": "2",
                "sum": 6000,
                "children": [
                    {
                        "id": "3",
                        "sum": 4000,
                    },

我想知道是否可能在buildTree函数内处理求和?我的想法是首先构建树,然后处理子级的求和,但我无法处理将求和分配给父元素。

英文:

I have flat array like:

[
    {
        "id": "1",
        "parentId": "0",
        "cost": 1000
    },
    {
        "id": "2",
        "parentId": "1",
        "cost": 2000
    },
    {
        "id": "3",
        "parentId": "2",
        "cost": 4000
    },
    ...
]

Requirement:

  • convert flat array to tree array --> (DONE)
  • sum of each id is the total price of it and its child

now the problem appears:

  • should summation be done before or after converting from flat array to tree array

This is my code is try convert flat to tree:

public function buildTree(array $flat)
    {
        $grouped = [];
        $fnBuilder = function ($companies) use (&$fnBuilder, $grouped) {
            foreach ($companies as $k => $company) {
                $id = $company['id'];
                if (isset($grouped[$id])) {
                    $company['children'] = $fnBuilder($grouped[$id]);
                }
                $companies[$k] = $company;
            }
            return $companies;
        };
        return $fnBuilder($grouped[0]);
    }

My expect result is like:

[
    {
        "id": "1",
        "sum": 7000,
        "children": [
            {
                "id": "2",
                "sum": 6000,
                "children": [
                    {
                        "id": "3",
                        "sum": 4000,
                    },

I wonder if it's possible to handle the summing inside the buildTree?

My idea is to have a tree and then handle the sum of sublevels, but i can't handle assigning the sum to the parent element

答案1

得分: 0

我创建了一个类并加入了你的想法。

class TreeBuilder {
    private $flatArr;
    private $idToNode;

    public function __construct($flatArr) {
        // 在需要时保留平面数组。
        $this->flatArr = $flatArr;
        // 创建一个查找节点以确定其是否存在的数组。
        $this->idToNode = array_combine(array_column($flatArr, 'id'), $flatArr);
    }

    public function buildTree() {
        // 创建一个空数组来保存根节点
        $roots = [];
        // 遍历每个节点并将其添加到其父节点的子节点列表中
        foreach ($this->flatArr as &$node) {
            $id = $node['id'];
            $parentId = $node['parentId'];
            if (isset($this->idToNode[$parentId])) {
                $this->out("将子节点添加到 $parentId " . print_r($node, true));
                $parentNode = &$this->idToNode[$parentId];
                if ( isset($parentNode['children']) ) {
                    $parentNode['children'] = [&$this->idToNode[$id]];
                } else {
                    $parentNode['children'][] = &$this->idToNode[$id];
                }
            } else {
                $this->out("添加到根节点 " . print_r($node, true));
                $roots[] = &$this->idToNode[$id];
            }
        }
        // 递归计算每个节点及其子节点的总和
        foreach ($roots as &$root) {
            $this->calculateSum($root);
        }
        return $roots;
    }

    private function calculateSum(&$node) {
        // 计算当前节点的总和
        $node['sum'] = $node['cost'];
        // 递归计算子节点的总和
        $children = &$node['children'];
        if (isset($children)) {
            foreach ($children as &$child) {
                $node['sum'] += $this->calculateSum($child);
            }
        }
        return $node['sum'];
    }

    private function out($s) {
        echo "$s\n";
    }
}

以上是你提供的代码的翻译部分。如有任何问题,请随时提问。

英文:

I created a class and incorporated your ideas.

class TreeBuilder {
private $flatArr;
private $idToNode;
public function __construct($flatArr) {
// Keep the flat arr in case we need it.
$this->flatArr = $flatArr;
// Create an array to lookup a node to determine if it exists.
$this->idToNode = array_combine(array_column($flatArr, 'id'), $flatArr);
}
public function buildTree() {
// create an empty array to hold root nodes
$roots = [];
// iterate through each node and add it to its parent's children list
foreach ($this->flatArr as &$node) {
$id = $node['id'];
$parentId = $node['parentId'];
if (isset($this->idToNode[$parentId])) {
$this->out("add child to $parentId " . print_r($node, true));
$parentNode = &$this->idToNode[$parentId];
if ( isset($parentNode['children']) ) {
$parentNode['children'] = [&$this->idToNode[$id]];
} else {
$parentNode['children'][] = &$this->idToNode[$id];
}
// $children[] = &$node;
} else {
$this->out("add to root " . print_r($node, true));
$roots[] = &$this->idToNode[$id];
}
}
// calculate the sum of each node and its children recursively
foreach ($roots as &$root) {
$this->calculateSum($root);
}
return $roots;
}
private function calculateSum(&$node) {
// calculate the sum of the current node
$node['sum'] = $node['cost'];
// recursively calculate the sum of the children nodes
$children = &$node['children'];
if (isset($children)) {
foreach ($children as &$child) {
$node['sum'] += $this->calculateSum($child);
}
}
return $node['sum'];
}
private function out($s) {
echo "$s\n";
}
}

答案2

得分: 0

以下是您要求的中文翻译:

您可以在不使用递归的情况下构建树,然后使用递归来更新总和,按照后序深度优先的顺序:

function buildTree(array $flat) {
    foreach ($flat as ["id" => $id, "cost" => $sum]) {
        $keyed[$id] = ["id" => $id, "sum" => $sum];
    }
    foreach ($flat as ["id" => $id, "parentId" => $parentId]) {
        if (isset($keyed[$parentId])) {
            $keyed[$parentId]["children"][] = &$keyed[$id];
        } else {
            $root = &$keyed[$id];
        }
    }
    function updateSum(&$node) {
        foreach ($node["children"] ?? [] as &$child) {
            $node["sum"] += updateSum($child);
        }
        return $node["sum"];
    }
    updateSum($root);
    return $root;
}

示例运行:

$flat = json_decode('[
    {
        "id": "1",
        "parentId": "0",
        "cost": 1000
    },
    {
        "id": "2",
        "parentId": "1",
        "cost": 2000
    },
    {
        "id": "3",
        "parentId": "2",
        "cost": 4000
    }
]', true);

$root = buildTree($flat);
print_r($root);
英文:

You could build the tree without recursion, and then use recursion to update the sum, in post-order depth first order:

function buildTree(array $flat) {
foreach ($flat as ["id" => $id, "cost" => $sum]) {
$keyed[$id] = ["id" => $id, "sum" => $sum];
}
foreach ($flat as ["id" => $id, "parentId" => $parentId]) {
if (isset($keyed[$parentId])) {
$keyed[$parentId]["children"][] = &$keyed[$id]; 
} else {
$root = &$keyed[$id];
}
}
function updateSum(&$node) {
foreach ($node["children"] ?? [] as &$child) {
$node["sum"] += updateSum($child);
}
return $node["sum"];
}
updateSum($root);
return $root;
}

Example run:

$flat = json_decode('[
{
"id": "1",
"parentId": "0",
"cost": 1000
},
{
"id": "2",
"parentId": "1",
"cost": 2000
},
{
"id": "3",
"parentId": "2",
"cost": 4000
}
]', true);
$root = buildTree($flat);
print_r($root);

huangapple
  • 本文由 发表于 2023年2月19日 10:46:12
  • 转载请务必保留本文链接:https://go.coder-hub.com/75497695.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定