Displaying Binary Tree

[Nuv]

This is my first try to display binary tree so please go easy on me.

I am trying to display binary tree using array. The values are stored in mysql.

 

Structure of mysql-

CREATE TABLE IF NOT EXISTS `tree` (
  `parent` int(7) NOT NULL,
  `rchild` int(7) NOT NULL,
  `lchild` int(7) NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

 

Display should look like

                    1
              ______|______
             |             |
             2             3
                     ______|______
                    |             |
                    4              5   

 

My Code till now-

<?php
include 'connection.php';
$rsearch = "SELECT rchild FROM tree WHERE parent='".$parent."'";
$lsearch = "SELECT lchild FROM tree WHERE parent='".$parent."'";
    
  $rexec = mysql_query($rsearch);
  $lexec = mysql_query($lsearch);
  
  while($rrow = mysql_fetch_assoc($rexec)) // Putting right branch in an array first
{
    $rtree[$i][0] = $rrow['parent'] ; 
    $rtree[$i][1] = $rrow['lchild'] ;
    $rtree[$i][2] = $rrow['rchild'] ;
    $i++;
}
while($lrow = mysql_fetch_assoc($lexec)) // Putting left branch in an array 
{
    $ltree[$j][0] = $lrow['parent'] ; 
    $ltree[$j][1] = $lrow['lchild'] ;
    $ltree[$j][2] = $lrow['rchild'] ;
    $j++;
}

function displaytree($parent,$array)
{
   // Im stuck here. Can someone please help me with it
}
?>

 

I am stuck at displaying the tree function. Can someone please point me in the right direction ?

 

 

 

[mikosiko]

here you go

http://blogs.sitepoint.com/hierarchical-data-database-2/

 

P.S: read pages 1 and 3 too

[Nuv]

Hi,

 

My main aim is not to traverse through the tree or add a node automatically, but to display.I just want a graphical representation for better understanding.The display should be like i mentioned in my initial post.

[mikosiko]

did you read or try to adjust/modify the function display_tree($root) that is in the provided link?

[Nuv]

Hi,

 

Thankyou for replying.After copying it from the blog my code becomes

<?php
include'config.php'
function rebuild_tree($parent, $left) {  
    // the right value of this node is the left value + 1   <br>  
    $right = $left+1;
   
    // get all children of this node   <br>  
   $sql = "SELECT title FROM tree WHERE parent='".$parent."'";
    $result = mysql_query($sql);   
    while ($row = mysql_fetch_array($result)) {   
        // recursive execution of this function for each   <br>  
        // child of this node   <br>  
        // $right is the current right value, which is   <br>  
        // incremented by the rebuild_tree function   <br>  
        $right = rebuild_tree($row['title'], $right); 
    }   
  
    // we've got the left value, and now that we've processed   <br>  
    // the children of this node we also know the right value   <br>  
    mysql_query('UPDATE tree SET lft='.$left.', rgt='.   
                 $right.' WHERE title="'.$parent.'";'); 
    
    // return the right value of this node + 1   <br>  
    return $right+1; 
} 

function display_tree($root) {  
    // retrieve the left and right value of the $root node  <br>  
    $result = mysql_query('SELECT lft, rgt FROM tree '.  
                           'WHERE title="'.$root.'";');   
    $row = mysql_fetch_array($result);  
  
    // start with an empty $right stack  <br>  
    $right = array();
   
    // now, retrieve all descendants of the $root node  <br>  
    $result = mysql_query('SELECT title, lft, rgt FROM tree '.  
                           'WHERE lft BETWEEN '.$row['lft'].' AND '.  
                           $row['rgt'].' ORDER BY lft ASC;');  
   
    // display each row  <br>  
    while ($row = mysql_fetch_array($result)) {    
        // only check stack if there is one  <br>  
        if (count($right)>0) {  
            // check if we should remove a node from the stack  <br>  
            while ($right[count($right)-1]<$row['rgt']) {  
                array_pop($right);   
            } 
        }  

        // display indented node title  <br>  
        echo str_repeat('----',count($right)).$row['title']."\n";
  
        // add this node to the stack  <br>  
        $right[] = $row['rgt'];  
    } 
}  
rebuild_tree('Food', 1);
display_tree('Food');

 

I have few questions regarding it.

 

1. So i will have to CREATE a temporary table every time someone wishes to see a tree with different root ?

 

2.Im still scratching my head over the display. However i tried their code with root='Food' and i got the following result

 

Food ----Cherry ----Yellow --------Banana ------------Meat ----------------Beef ----------------Pork ----Fruit --------Red 

 

Is this right ?

 

 

[Nuv]

The above table image was copied from the blog however my table looks something like

 

The rgt and lft values seem different.

 

[mikosiko]

@Nuv... you got this wrong... (partially wrong by the way).

 

- To display the tree the only function that you need to use is display_tree() ... surprising isn't?

      * if you want to change the final display layout you must adjust this function to your needs, specifically this part:

        // display indented node title  <br>  
        echo str_repeat('----',count($right)).$row['title']."\n"

 

and by the way... but a better display change the "\n" in that line with a "<br />"

 

- The function rebuild_tree() must be used only when you add/modify/delete elements in your tree... it has nothing to do with the display.. but if you make modifications to your tree obviously you must use it before to call the display_tree().

 

- You are no creating any "temporary table"... and by now your table looks different to the example in the blog because you executed the rebuild_tree() function when was not needed.

 

 

 

[Nuv]

@Nuv... you got this wrong... (partially wrong by the way).

 

- To display the tree the only function that you need to use is display_tree() ... surprising isn't?

      * if you want to change the final display layout you must adjust this function to your needs, specifically this part:

        // display indented node title  <br>  
        echo str_repeat('----',count($right)).$row['title']."\n"

 

 

If i use my initial database structure i made a new display function but its very far from ok.Can you please help me with it ?

<?php
function display_tree($root) {  
       $level = 1;
    $result = mysql_query('SELECT rchild,lchild,parent FROM tree '.  
                           'WHERE parent="'.$root.'";');   
     $row = mysql_fetch_array($result);  
     
     echo str_repeat('    ',($level * 2 )).$row['parent']."<br />";
     echo str_repeat('    ',($level * 2))."|"."<br />";
     echo str_repeat('____',($level*2))."<br />";
     echo "|".str_repeat('    ',($level * 4))."|"."<br />" ;
     echo $row['lchild'].str_repeat('    ',($level * 4)).$row['rchild'];
     
} 
?>  

 

Output

 

How should i remove any spaces plus how should i print the complete tree and not just 1 node and its children.

 

 

 

 

 

 

 

 

 

[mikosiko]

  ... Oh well....  I'm not going to write the code for you, but here is more food for your thoughts that should help you to implement/solve what you want:

 

http://evolt.org/node/4047/  ... it is old, but it shows some concepts that could help you.

 

good luck.