Jump to content

Binary tree - ischild function not working .


Nuv

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);
     }
   
  }  

Link to comment
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.

Link to comment
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().

Link to comment
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] => 
                )

        )

)

 

Link to comment
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. "(

Link to comment
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);
}

}

Link to comment
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 ?

Link to comment
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?

Link to comment
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"

Link to comment
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

Link to comment
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;
  } ?> 

Link to comment
Share on other sites

This thread is more than a year old. Please don't revive it unless you have something important to add.

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...

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.