PHPBuilder - Simple Tree



RSS Twitter
Snippets 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
?>

Comment and Contribute

Your comment has been submitted and is pending approval.

Author:
Ken Foubert

Comment:



Comment:

(Maximum characters: 1200). You have characters left.