Help writing a recursive function

[dlite922]

I need to get a list of employees out of a database table.

I need to end up with an array of ids (primary keys) such as

Array(03,9,2,5, 1)

The employee table has a self reference so that each record has a parentID and a level. For example

id_____parentID____Level________Name
12_____15__________1_____________John
15_____-1__________0_____________Harry
19_____15__________1_____________Smith
20_____19__________2_____________Jane

In this example, Harry is the top manager. He has two managers under him, John and Smith, further more Smith has Jane under him. (get your mind out of the gutter!)

Instead of the recursive function calling the database each time to get an id, I'll do one call and put the entire employee table in an array of assoc array(id, parentID) since there's only several records.

[PHP]
Array(
[0] = Array("
["id"] = 12,
["parentID"] = 15
)
[1] = Array (......and so on, you get the point)

[/PHP]

The recursive function will be given the primary id of the employee I need to build for. The returned array list will contain this id along with every employee under him, going down the tree as needed. I'll do one more thing, i'll even give you the employee array (shown above) as the second parameter like so:

function Recursive($_SES SION['employeeID'], $employeeArray)
{

// do magic here


}

does anybody get the idea? I never really liked recursive functions, but If I build it, i'll post it here.

thanks,



Dan

[Brosert]

You would want to have a look at Tree structures on the internet..
You should easily be able to find recursive algorithms to traverse a tree....

Basically, there are two options....
Pre-Traversal (where you use the current node BEFORE it's childeren (this is the one you want, I think)
Post-Traversal (where you deal with the curtrent node AFTER it's childeren)
(There is also a third for Binary trees, but I doubt this structure can be limited to a binar y tree...

Basically, in non-php terms, what you want to do is:

Recurse(EmployeeId, ChildrenArray)
  Print out EmployeeID (and anything else you want to print out)
  foreach Child in ChildrenArray do
    Recurse(Child, Child->ChildrenArray);
  endloop
endfunction

[dlite922]

Did it, please let me know if there's any mistakes you see.

[PHP]

$employees= array(
array("id" => 1, "parentID" => 2),
array("id" => 2, "parentID" => 3),
array("id" => 3, "parentID" => -1),
array("id" => 4, "parentID" => -1)
);

function buildEmpList($r unningList,$emp loyees, $employeeID)
{
array_push($run ningList, $employeeID);
foreach ($employees AS $emp)
{
if($emp['parentID'] == $employeeID)
{
$runningList = $runningList + buildEmpList($r unningList, $employees, $emp['id']);
}
}

return $runningList;
}

$result = array();
print_r(buildEm pList($result, $employees,3));

//outputs:
Array
(
[0] => 3
[1] => 2
[2] => 1
)

[/PHP]


This drove me nuts for a little while.


-Dan

[dlite922]

You would want to have a look at Tree structures on the internet..
You should easily be able to find recursive algorithms to traverse a tree....

Basically, there are two options....
Pre-Traversal (where you use the current node BEFORE it's childeren (this is the one you want, I think)
Post-Traversal (where you deal with the curtrent node AFTER it's childeren)
(There is also a third for Binary trees, but I doubt this structure can be limited to a binar y tree...

Basically, in non-php terms, what you want to do is:

Recurse(EmployeeId, ChildrenArray)
  Print out EmployeeID (and anything else you want to print out)
  foreach Child in ChildrenArray do
    Recurse(Child, Child->ChildrenArray);
  endloop
endfunction

Thanks, yes I'm familiar with BTrees, and Sorting Algorithms. breadth-first searches (I paid attention in algorithm class)

But I barely got a C.

Anyways, I wouldn't care what order they are in, these will end up right back in a MySQL query IN() where-clause, wouldn't matter.

It's been a while since I wrote a recursive function.



Dan