I have a tree of categories of the following structure:
[6] => Array
(
[id] => 6
[name] => computers
[productCount] => 0
[children] => Array
(
[91] => Array
(
[id] => 91
[name] => notebook
[productCount] => 5
[children] => Array
(
)
)
[86] => Array
(
[id] => 86
[name] => desktop
[productCount] => 0
[children] => Array
(
)
)
)
)
Beside a subcategory, each category may contain products (like a folder may contain subfolders and just files).
I'm trying to write a recursive function which I want to take this array as reference and strip both leaf categories with [productCount] = 0 and all parent categories that contain such empty nodes. In other words, after processing I want to have only those categories that hold products on any sublevels.
I've wrote some code, now debugging it and it doesn't strip empty nodes. May be I'm not using references properly. Please, help me fix it, if possible.
function pruneTree( & $node) {
if ( ! $node['children'] && ! $node['productCount']) {
unset($node);
}
if ( ! empty($node['children'])) {
foreach ($node['children'] as $key => $child) {
pruneTree($node['children'][$key]);
}
}
return;
}
Yes, it has to be pass by reference.
Now onto callbacks which differ from recursions, within a function another separate function called within is a callback. Let's see an example. Here we have the function dogWalking() being called, as it executes it runs line 2's console.
Recursion means “solving a problem using the solution of smaller subproblems (smaller version of the same problem)” or “defining a problem in terms of itself”. This is a widely used idea in data structures and algorithms to solve complex problems by breaking them down into simpler ones.
Pass by reference (also called pass by address) means to pass the reference of an argument in the calling function to the corresponding formal parameter of the called function so that a copy of the address of the actual parameter is made in memory, i.e. the caller and the callee use the same variable for the parameter.
You could also change the parameter in the function to take an array of nodes instead of a single node. This changes the recursion slightly, and prevents the need to pass along a key:
function pruneTree(&$nodes) {
foreach ($nodes as $key => $node) {
if (!$node['children'] && !$node['productCount']) {
unset($nodes[$key]);
} elseif (!empty($node['children'])) {
pruneTree($nodes[$key]['children']);
// This line checks if all the children have been pruned away:
if (empty($nodes[$key]['children'])) {
unset($nodes[$key]);
}
}
}
}
Also, added a check that ensures that if all child nodes are pruned, the parent (now, leaf) node also gets pruned.
Hope this helps!
Test data:
$data = array(
6 => array(
'id' => 6,
'name' => 'computers',
'productCount' => 0,
'children' => array(
91 => array(
'id' => 91,
'name' => 'notebook',
'productCount' => 5,
'children' => array()
),
86 => array(
'id' => 86,
'name' => 'desktop',
'productCount' => 0,
'children' => array()
)
)
)
);
The Call:
pruneTree($data);
echo '<pre>';
print_r($data);
echo '</pre>';
unset
deletes only the reference but not the referenced variable:
If a variable that is PASSED BY REFERENCE is
unset()
inside of a function, only the local variable is destroyed. The variable in the calling environment will retain the same value as beforeunset()
was called.
So you need to pass the parent array and the key to delete that variable:
function pruneTree(&$parent, $key) {
$node = &$parent[$key];
if (!$node['children'] && !$node['productCount']) {
unset($parent[$key]);
}
if (!empty($node['children'])) {
foreach ($node['children'] as $key => &$child) {
pruneTree($node['children'], $key);
}
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With