Jump to content

Archived

This topic is now archived and is closed to further replies.

Nuv

Binary tree - ischild function not working .

Recommended Posts

I made a function to check if the child belongs to a parent ($node) or not. However its not working completely.If i include immediate children of the parent ($node) then the answer is yes otherwise it gives nothing (indicating it isnt the child) which is wrong. I think its because of recursive functions.Can someone please point out my mistake.

 

<?php
function ischild($node,$child)   //$node is parent to see if $child is its child or not.
  {
    $sql = "SELECT lchild,rchild FROM tree WHERE parent = '$node'";
    $execsql = mysql_query($sql);
    $array = mysql_fetch_array($execsql);
    
    if(($array['lchild']) == $child)
    {
   
      return "yes";
    }
    elseif (!empty($array['lchild']))
    {
        ischild($array['lchild'],$child);
    } 
    if($array['rchild'] == $child)
    {
        return "Yes";
    }
    elseif(!empty($array['rchild']))
    {
        ischild($array['rchild'],$child);
     }
   
  }  

Share this post


Link to post
Share on other sites

What happens to the return value of the recursive calls?  And is the final result "yes" if either of the recursive calls returns "yes"?

Share this post


Link to post
Share on other sites

Well i am trying to count the left node and right node  added on a particular date under $node(parent). However i cannot make a proper function for that. (it would be nice if you would help me with it) what i am doing is to find all the nodes with that date and then find if it is the child of $node(parent) and then the display the count.

Share this post


Link to post
Share on other sites

Just looking at ischild() for now - a child C is a child of node N iff:

 

1.  C is a the left child or right of N (you have implemented this already), or

2.  C is a child (recursively) of the left child or the right child of N (you have the calls here, but don't handle the return value)

 

So your recursive calls to ischild() need to handle the return value to implement that second rule.  There's a number of ways to do it.  The simplest is probably like this:

 

    elseif (!empty($array['lchild']))
    {
        $ischild = ischild($array['lchild'],$child);
        if ($ischild == "Yes") return "Yes";
    } 

 

And make the same change to the right child check.  That will make it so the return value of the recursive calls, which was being ignored before, are passed back to the caller of the initial call to ischild().

Share this post


Link to post
Share on other sites

Thanks. Nice explanation.

 

I am also having trouble displaying a binary tree level wise.Level 0 being $node(parent) , Level 1 being immediate children of $node etc. I made a function to gather the nodes in an array but i don't know how to utilize it to my advantage.

 

 <?php
function tree_gather($node)   //Function to calculate count
  {
    $sql = "SELECT lchild,rchild FROM tree WHERE parent = '$node'";
    $execsql = mysql_query($sql);
    $array = mysql_fetch_array($execsql);
    
    if(!empty($array['lchild']) || !empty($array['rchild']))
    {
   
      $child[] = $array['lchild'];
      $child[] = $array['rchild'];
      $child[] = tree_gather($array['lchild']);
      $child[] = tree_gather($array['rchild']);
      
    } 
     return $child;
  } ?> 

 

Output-

Array
(
    [0] => 2
    [1] => 3
    [2] => Array
        (
            [0] => 4
            [1] => 5
            [2] => Array
                (
                    [0] => 10
                    [1] => 11
                    [2] => 
                    [3] => 
                )

            [3] => Array
                (
                    [0] => 8
                    [1] => 9
                    [2] => 
                    [3] => 
                )

        )

    [3] => Array
        (
            [0] => 7
            [1] => 6
            [2] => Array
                (
                    [0] => 15
                    [1] => 14
                    [2] => 
                    [3] => 
                )

            [3] => Array
                (
                    [0] => 13
                    [1] => 12
                    [2] => 
                    [3] => 
                )

        )

)

 

Share this post


Link to post
Share on other sites

Are you displaying it on text or some kind of markup like HTML, or some other method?

Share this post


Link to post
Share on other sites

I will be displaying it using <table>.

Share this post


Link to post
Share on other sites

Have you decided how you will display it in the table?  Will you be using td elements to get the right spacing?

Share this post


Link to post
Share on other sites

Yeah i have already decided that. I will be placing it in <td> tag.

Share this post


Link to post
Share on other sites

Can you give a bit more detail about how you're going to display the tree?

Share this post


Link to post
Share on other sites

Hi,

 

Displaying will be normal in tables like if i enter level 1.Then it will show data like

 

Sr No.    Member id    Member name    Position

1.              3343              Drake                Left

2.              3435              Rob                    Right

 

 

Easy. Not too complicated. Its just the levels. How to show the members level wise. And how can i use my function. "(

Share this post


Link to post
Share on other sites

Does the order in which the nodes are printed matter?  In any case, you can use a recursive function which keeps track of depth in the tree to find the depth of each node.  Whenever the recursive function calls itself for a lower node in the tree it calls itself with $depth+1 as an argument.  And the initial call will start with depth 1.  eg

 

function print_tree($tree) {
   print_tree_depth($tree, 1);
}

function print_tree_depth($tree, $depth) {
  # print current node
  print_tree_depth(left child, $depth+1);
  print_tree_depth(right child, $depth+1);
}

}

Share this post


Link to post
Share on other sites

Does the order in which the nodes are printed matter?  In any case, you can use a recursive function which keeps track of depth in the tree to find the depth of each node.  Whenever the recursive function calls itself for a lower node in the tree it calls itself with $depth+1 as an argument.  And the initial call will start with depth 1.  eg

 

function print_tree($tree) {
   print_tree_depth($tree, 1);
}

function print_tree_depth($tree, $depth) {
  # print current node
  print_tree_depth(left child, $depth+1);
  print_tree_depth(right child, $depth+1);
}

}

 

Is $tree the node ?

Also, Consider the following tree with node A(level 0) has immediate child,right child = C and left child = B (level 1 constitutes B and C). D,E and F become level 2 and so on.

    |-------A------|                     <--- Level 0
|--B--|         |--C--|                  <--- Level 1
D     E         F                           <--- Level 2

 

So if i want to see level 2 the function will fetch all the elements of level 2 i.e D, E and F only.Was i wrong in explaining it earlier or your function does the same ?

Share this post


Link to post
Share on other sites

My function prints the nodes out in the order it finds them.  That will be A, B, D, E, C, F in your example tree.  It will always print the left child first.

 

What order do you want to print them in?

Share this post


Link to post
Share on other sites

What order do you want to print them in?

 

This is why I haven't replied yet.  There is no point in me writing a function to print out the tree, and then have you say it's in the wrong order.  In your previous post you mentioned wanting to print out all nodes on a specific level as well.  Can you please clarify what it is that you want the function to do.

 

For example: "Function arguments are $tree and $depth.  Function prints out all nodes at level $depth, from left to right"

Share this post


Link to post
Share on other sites

Sequence really doesnt matter. However, from left to right should do.

Share this post


Link to post
Share on other sites

you can binary tree put in array in this way

1. root node put on index 1 in array

2. lchild of node with index n put in array element with indeks 2*n

3. rchild of node with index n put in array element with indeks 2*n+1

 

parent element of element with index n is in position (int)(n/2)

 

level of element with index n is log(n, 2) (root element is level 0)

 

on n-th level is elements with index from pow(2, n) to pow(2, n+1)-1

 

here is code for put tree in array

 <?php
function tree_gather($node)   //Function to calculate count
  {
    $tree = array(1 => $node);
    b_tree($node, 1, &$tree);
    return $tree;
  } 
  function b_tree($node, $index, &$tree){
      $sql = "SELECT lchild,rchild FROM tree WHERE parent = '$node'";
      $execsql = mysql_query($sql);
      if($array = mysql_fetch_array($execsql)){
          if(!empty($array['lchild'])){
              $tree[$index * 2] = $array['lchild'];
              b_tree($array['lchild'], $index * 2, &$tree);
          }
          if(!empty($array['rchild'])){
              $tree[$index * 2 + 1] = $array['rchild'];
              b_tree($array['rchild'], $index * 2 + 1, &$tree);
          }
      }
  }
  ?>

the code is not tested

Share this post


Link to post
Share on other sites

Since tree_gather() already traverses the whole tree, you can add code in it to track the levels and display each node as it goes.

 

 <?php
function tree_gather($node, $level)   //Function to calculate count
  {
    # SQL to fetch node data here
    print "[$level] - Display node data here\n";

    $sql = "SELECT lchild,rchild FROM tree WHERE parent = '$node'";
    $execsql = mysql_query($sql);
    $array = mysql_fetch_array($execsql);
    
    if(!empty($array['lchild']) || !empty($array['rchild']))
    {
   
      $child[] = $array['lchild'];
      $child[] = $array['rchild'];
      $child[] = tree_gather($array['lchild'], $level + 1);
      $child[] = tree_gather($array['rchild'] $level + 1);
      
    } 
     return $child;
  } ?> 

Share this post


Link to post
Share on other sites

×

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.