Version: 0.2
Type: Full Script
Category: Algorithms
License: GNU General Public License
Description: This is a simple implementation of a Tree structure using matrix Queue representation. Functions for adding elements and listing the tree. I used it for a directory tree implementation.
<?php //Simple Tree v0.1 //This is a simple implementation of a Tree structure using matrix Queue representation. //Author:Mircea Banu ([email protected]) //02.02.2004 /* Simple Tree v0.2 added additional comments for the tree_add function, added a looping function that will find orphaned chilren and add them to the branch Added a sorting function to sort the items in a list alphabetically Added a dynamic tree view, will only show the current branching, will not remember which nodes are open Save the file as simple_tree_view_02.php Author: Ken Foubert ([email protected]) 2004-5-27 */ global $tree; $id = 6; if ( isset($_GET['id']) ) $id = $_GET['id']; $p=new Nod("root",0,0); $root=$p; tree_add($p); $arrCat = create_category_array('baseball'); //loop through each array and it to the tree foreach ( $arrCat AS $arrDetail ) { $p = new Nod($arrDetail['name'], $arrDetail['cat_id'], $arrDetail['parent_id']); tree_add($p); } //end forech ###################################################################################################################### ###################################################################################################################### ###################################################################################################################### ?> <html> <body> <?php //tree_list(); //print_r( $tree ); //echo "<hr>"; $tree = sort_tree( $tree ); //echo "<br>"; tree_list(); //echo "<br>"; create_tree_view( $tree, $id ); ?> </body> </html> </body> </html> <? ###################################################################################################################### ###################################################################################################################### ###################################################################################################################### function tree_add($to_add) { //Ads a new element into the tree global $tree; $i=0; $j=0; //loop through all the existing branches while($tree[$i][0]!=NULL) { $j=0; //if $to_add father id matches the first element id, //then place $to_element in the branch as the last element if($tree[$i][0]->get_id()==$to_add->get_father()) { while($tree[$i][$j]!=NULL) { $j++; } //end while $tree[$i][$j-1]->set_last_child(0); $tree[$i][$j]=$to_add; } //end if $i++; } //end while //create a new branch $tree[$i][0]=$to_add; $branch = 0; //exit if at athe root level if ( $tree[$i][0]->get_id() == 0 && $tree[$i][0]->get_father() == 0 ) { return 0; } //end if //loop through all the existing branches and find any orphaned children while($tree[$branch][0]!=NULL) { //the new position starts after the last element $new_element_pos = count( $tree[$i] ); //if $to_add id matches the first element father id of the branch, //then add that element as a child to the $to_add node if($tree[$i][0]->get_id()==$tree[$branch][0]->get_father()) { //the previous item is no longer the last child if ( $tree[$i][$new_element_pos - 1] != NULL ) { $tree[$i][$new_element_pos - 1]->set_last_child(0); } $tree[$i][$new_element_pos] = $tree[$branch][0]; $tree[$i][$new_element_pos]->set_last_child(1); } //end if $branch++; } //end while } //end function function sort_tree( $tree ) { foreach ( $tree as $key=>$branch ) { $branch = sort_array( $branch ); $tree[$key] = $branch; } //end foreach return $tree; } //end function //Sorts a branch of the tree alphabetically function sort_array( $branch ) { $array_size = count( $branch ); $hold = array(); //don't sort the first element, which is the parent //use a bubble sort for ( $pass = 1; $pass < $array_size - 1; $pass++ ) { for ( $current = 1; $current < $array_size - 1; $current++ ) { /* echo "branch[current]: ".$branch[$current]->get_name()."<br>"; echo "branch[current+1]: ".$branch[$current+1]->get_name()."<br>"; echo "<hr>"; */ if ( strcmp($branch[$current]->get_name(), $branch[$current + 1]->get_name()) > 0 ) { //set the last_child to 0 for all of them $branch[$current]->set_last_child(0); $branch[$current + 1]->set_last_child(0); $hold = $branch[$current]; $branch[$current] = $branch[$current + 1]; $branch[$current + 1] = $hold; /* echo "<b>Hold</b><br>"; print_r( $hold ); echo "<br>current<br>"; print_r( $branch[$current]); echo "<br>current + 1<br>"; print_r( $branch[$current + 1]); echo "<br>result<br>"; print_r( $branch ); echo "<br>"; */ } //end if } //end for } //end for loop //set last_child to 1 for last_element $branch[$array_size -1]->set_last_child(1); /* echo "<br>set last child<br>"; print_r( $branch ); echo "<br>"; */ return $branch; } //end function function tree_list() { //List the tree global $tree; $i=0; while($tree[$i][0]!=NULL) { $j=0; while($tree[$i][$j]!=NULL) { echo "(".$tree[$i][$j]->get_id().")".$tree[$i][$j]->get_id().' => '.$tree[$i][$j]->get_name().' p='.$tree[$i][$j]->get_father(); $j++; } //end while $i++; echo "<br>"; } //end while } //end function function tree_height($p) { //Returns the tree height global $tree; $i=0; $gata=0; if($p->get_id()==0) { return 0; } //end if else { while(($tree[$i][0]!=NULL)and($gata!=1)) { $j=1; while(($tree[$i][$j]!=NULL)and($gata!=1)) { if($tree[$i][$j]->get_id()==$p->get_id()) { $gata=1; } //end if $j++; } //end while $i++; } //end while if($tree[$i-1][0]->get_id()!=0) { return 1+tree_height($tree[$i-1][0]); } //end if else { return 1; } //end else } //end else } //end function function tree_has_children($p) { //Returns true if the tree has children global $tree; $i=0; while($tree[$i][0]->get_id()!=$p->get_id()) { $i++; } //end while if($tree[$i][1]!=NULL) { return 1; } //end if else { return 0; } //end else } //end function function create_category_array($type='baseball') { if( $type == 'rand' ) { $i=1; $arrCat = array(); while($i < 10) { $i_name = "node_".$i; $i_id = $i; $i_parent = rand(0,$i); $arrCat[] = array( "cat_id"=>$i_id, "parent_id"=>$i_parent, "name"=>$i_name); $i++; } //end while } elseif( $type == 'baseball' ) { $arrCat = array ( array( "cat_id"=>"1", "parent_id"=>0, "name"=>"National League"), array( "cat_id"=>"2", "parent_id"=>1, "name"=>"NL West"), array( "cat_id"=>"4", "parent_id"=>1, "name"=>"NL Central"), array( "cat_id"=>"14", "parent_id"=>40, "name"=>"AL Central"), array( "cat_id"=>"16", "parent_id"=>40, "name"=>"AL East"), array( "cat_id"=>"22", "parent_id"=>12, "name"=>"Seattle"), array( "cat_id"=>"20", "parent_id"=>12, "name"=>"Texas"), array( "cat_id"=>"33", "parent_id"=>14, "name"=>"Minnesota"), array( "cat_id"=>"27", "parent_id"=>14, "name"=>"Detroit"), array( "cat_id"=>"25", "parent_id"=>16, "name"=>"Baltimore"), array( "cat_id"=>"6", "parent_id"=>1, "name"=>"NL East"), array( "cat_id"=>"3", "parent_id"=>2, "name"=>"Los Angeles"), array( "cat_id"=>"5", "parent_id"=>2, "name"=>"San Francisco"), array( "cat_id"=>"7", "parent_id"=>4, "name"=>"Houston"), array( "cat_id"=>"13", "parent_id"=>4, "name"=>"Pittsburgh"), array( "cat_id"=>"15", "parent_id"=>6, "name"=>"Montreal"), array( "cat_id"=>"17", "parent_id"=>6, "name"=>"Atlanta"), array( "cat_id"=>"40", "parent_id"=>0, "name"=>"American League"), array( "cat_id"=>"12", "parent_id"=>40, "name"=>"AL West"), array( "cat_id"=>"19", "parent_id"=>16, "name"=>"Toronto") ); } elseif( $type == 'db_table' ) { ini_set( 'max_execution_time', '60' ); $connect = mysql_connect( 'www.test.com', 'tree_view', 'password' ); if( !$connect ){ die("Unable to make connection!"); } $db = mysql_select_db('nce'); if(!$db){ die("Problem choosing database!"); } $sql = 'SELECT c.id, c.name, c.parent_id FROM categories c WHERE c.active = "Y" '; $res = mysql_query($sql) or die(mysql_error()); while($i = mysql_fetch_assoc($res)) { $i_name = $i['name']; $i_id = $i['id']; $i_parent = $i['parent_id']; $arrCat[] = array( "cat_id"=>$i_id, "parent_id"=>$i_parent, "name"=>$i_name); $i++; } } return $arrCat; } //end function //================================================================================================================ //create a tree based on the id function create_tree_view( &$tree, &$id ) { ?> <p><a href="simple_tree_view_02.php?id=0">Home</a></p> <? $arrLevel = array(); $arrLevel = get_branches( $tree, $id ); //start at the last element, which is always the root level $level = count( $arrLevel ) - 1; //this function uses recursion print_level( $arrLevel, $level ); } //end function //get the branches based on the selected id function get_branches( &$tree, &$id ) { $arrLevel = array(); $end_search = ""; $level = 0; $selected_id = 0; $selected_id = $id; //loop until all the branches have been found while ( $end_search <> "end" ) { //loop through each $branch in the $tree array foreach ( $tree AS $branch ) { //check the first object in the branch //if the selected_id matches the id of first element, then get that branch if ( $selected_id == $branch[0]->get_id() ) { $arrLevel[$level] = $branch; //get the father id of the first element. This will determine //the next branch to grab. $selected_id = $branch[0]->get_father(); $level = $level + 1; //if the root level has been found, then quit if ( $branch[0]->get_id() == 0 && $branch[0]->get_father() == 0 ) { $end_search = "end"; } //end if //no reason to keep looping, quit the foreach continue; } //end if } //end foreach } //end while return $arrLevel; } //end function function print_level( &$arrLevel, $level ) { echo "<ul>n"; //loop through each child for ( $child = 1; $child < count($arrLevel[$level]); $child++ ) { $child_id = $arrLevel[$level][$child]->get_id(); $tree_url = "<a href="simple_tree_view_02.php?id=$child_id">"; echo "<li>$tree_url".$arrLevel[$level][$child]->get_name()."</a></li>"; //make sure the next level has children if ( count($arrLevel[$level-1]) > 1) { //if the next level contains the child, then print that level if ( $arrLevel[$level][$child]->get_id() == $arrLevel[$level-1][0]->get_id() ) { print_level($arrLevel, $level-1); } //end if } //end if } //end for loop echo "</ul>n"; } //end function //================================================================================================================ class Nod { //the class containing the tree element properties and some functions var $name; var $id; var $father; var $last_child;//1 is the last child added, 0 else function Nod($name,$id,$father_id) { //constructor $this->name=$name; $this->id=$id; $this->father=$father_id; $this->last_child=1; } //end function function get_name() { return $this->name; } //end function function get_id() { return $this->id; } //end function function get_father() { return $this->father; } //end function function last_child() { return $this->last_child; } //end function function set_last_child($val) { $this->last_child=$val; } //end function } //end class ?>
