Register now or log in to join your professional community.
I have a binary tree and I want to find out all Nodes which have6 child-nodes including left and right nodes. Make sure each parent node has child on its left and right nodes so in simple words, tree should be balanced all the time. For example: http://i39.tinypic.com/x0ts01.png so1 node should be returned. Binary tree could be of any depth but I need all those nodes which have6 child node under it.
This is an example of binary structure of php using my sql
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 <?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');
Did You need code to silve this problem or you need just procedure it will be solved in both way if you need code please send me your case where you have staucked.
