PHP Binary Tree Recursion Algorithm
Solution 1
If I understand correctly, this is what you want:
function tree(array $data, &$tree = array(), $level = 0) {
// init
if (!isset($tree[$level])) $tree[$level] = array();
foreach ($data as $key => $value) {
// if value is an array, push the key and recurse through the array
if (is_array($value)) {
$tree[$level][] = $key;
tree($value, $tree, $level+1);
}
// otherwise, push the value
else {
$tree[$level][] = $value;
}
}
}
Use it like this:
$binary_tree = array(1 => array(2 => array(4,5),4=>array(5,6)));
tree($binary_tree, $output);
var_dump($output);
This gives you:
array(3) {
[0]=>
array(1) {
[0]=>
int(1)
}
[1]=>
array(2) {
[0]=>
int(2)
[1]=>
int(4)
}
[2]=>
array(4) {
[0]=>
int(4)
[1]=>
int(5)
[2]=>
int(5)
[3]=>
int(6)
}
}
Solution 2
This function in class Tree view
you have got a return of array which has all node value then you can arrange on below tree view .
function getTreeDataFromReg($setid)
{
if(!empty($setid))
{
for($in=0 ;$in<7;$in++ )
{
if($setid[$in]>0)
{
$result=$this->selectQuery(
"tbl_registration"," * "," fl_reg_id ='".$setid[$in]."'",
" fl_placment_side ASC ");
$setar=mysql_fetch_array($result);
$leftid=$setar['fl_left_id'];
$rightid=$setar['fl_right_id'];
}else
{
$leftid=0;
$rightid=0;
}
switch($in)
{
case 0: $setid[1]=$leftid;
$setid[2]=$rightid;
break;
case 1: $setid[3]=$leftid;
$setid[4]=$rightid;
break;
case 2: $setid[5]=$leftid;
$setid[6]=$rightid;
break;
case 3: $setid[7]=$leftid;
$setid[8]=$rightid;
break;
case 4: $setid[9]=$leftid;
$setid[10]=$rightid;
break;
case 5: $setid[11]=$leftid;
$setid[12]=$rightid;
break;
case 6: $setid[13]=$leftid;
$setid[14]=$rightid;
break;
}
}
}
return $setid;
}
function printTreeView($parentid)
{
$setid=array($parentid);
$setarra=$this->getTreeDataFromReg($setid);
return $setarra;
}
Which creates a binary tree:
0
/ \
1 2
/ \ / \
3 4 5 6
/\ / \ /\ /\
![Samvel Kostanyan](https://lh5.googleusercontent.com/-_sTQxIajY24/AAAAAAAAAAI/AAAAAAAAAAA/AMZuucn-h3S2huX8lg3TTyLR1gd6OD4cVA/photo.jpg?sz=256)
Samvel Kostanyan
Updated on March 29, 2020Comments
-
Samvel Kostanyan about 4 years
I want to create a PHP recursive program using a Binary Tree and Recursion.
I want to print the binary tree level by level using recursion. I want to recurse through the tree, push the node into a hashmap that has the level as the reference point.
Here's what I have so far:
$binary_tree = array(array(1 => array(2 => array(4,5),4=>array(5,6)))); 1 | ------------------ | | 2 4 | | ---------- ---------- | | | | 4 5 5 6
And the end result should look like this:
$data[0] = array(1); $data[1] = array(2,4); $data[2] = array(4,5,5,6);
I can easily loop through the array and print out the numbers, which are corresponding to the level(the array index).
Here's the function, which is wrong, but my first shot:
function recurse_tree($data,$level=0){ $final = array(); $tmp = array() // first check if data is array if(is_array($data)){ // loop through data foreach($data as $elm){ // push data to the tmp array $tmp[] = recurse_tree($elm,$level+1); } // not an array } else { // push data to the final array. can we push to the tmp array. array_push($final[level],$elm); } // merge final and tmp array and return return ($final + $tmp); }
I am not too experienced with recursion nor problem solving, so I wrote out the steps below which are occurring. The problem I have here now is that on step 9 I an unsure how to handle the keys 2 and 4, and then finally to handle the root node, key 1. Also, when I get to steps 5-8, im at level 4, which is correct, however according to the tree, its level 2.
$flattened_tree = recurse_tree($data); // STEPS: 1./ called recurse_tree data: array(array(1 => array(2 => array(4,5),4=>array(5,6)))); level: 0 final: array(); tmp: array(); 2./ called recurse_tree: data: array(1 => array(2 => array(4,5),4=>array(5,6))); level: 1 final: array(); tmp: array(); 3./ called recurse_tree: data: array(2 => array(4,5),4=>array(5,6)); level: 2 final: array(); tmp: array(); 4./ called recurse_tree: data: array(4,5) level: 3 final: array(); tmp: array(); 5./ called recurse_tree: data: 4 level: 4 final: array(4 => 4) tmp: array() 6./ called recurse_tree: data: 5 level: 4 final: array(4 => 5) tmp: array(4 => 4) 7./ called recurse_tree: data: 5 level: 4 final: array(4=> 5) tmp: array(4 => array(4,5)) 8./ called recurse_tree: data: 6 level: 4 final: array(4 => 6) tmp: array(4 => array(4,5,5))
What is the best way to implement a Binary Tree recursion algorithm?