Snippets Algorithms
Algorithms
Simple Tree
by: Ken Foubert
|
May 27, 2004
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 (banu@ss.pub.ro)
//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 (kfoubert@sitecrafting.com)
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
?>
PHPBuilder
Policies
PHP Developer
Topics
PHP Developer
Resources
PHP Developer
References
