Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

PHP Binary Tree Recursion Algorithm

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?

like image 831
somejkuser Avatar asked Feb 16 '11 18:02

somejkuser


2 Answers

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)
  }
}
like image 173
netcoder Avatar answered Sep 28 '22 05:09

netcoder


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
     /\  / \  /\   /\
like image 23
vinay bhardwaj Avatar answered Sep 28 '22 05:09

vinay bhardwaj