Hello All,
I have been having a really hard time trying to come up with a pl/pgsql
recursive function to returns the end nodes of a tree.
Here is an example table definition:
CREATE TABLE parent_child (
parent_id integer NOT NULL,
child_id integer NOT NULL
);
INSERT INTO parent_child (parent_id, child_id) VALUES (1, 2);
INSERT INTO parent_child (parent_id, child_id) VALUES (1, 3);
INSERT INTO parent_child (parent_id, child_id) VALUES (1, 4);
INSERT INTO parent_child (parent_id, child_id) VALUES (2, 5);
INSERT INTO parent_child (parent_id, child_id) VALUES (2, 6);
INSERT INTO parent_child (parent_id, child_id) VALUES (4, 7);
INSERT INTO parent_child (parent_id, child_id) VALUES (4, 8);
INSERT INTO parent_child (parent_id, child_id) VALUES (4, 9);
INSERT INTO parent_child (parent_id, child_id) VALUES (9, 10);
This produces the following tree of data:
1
___|___
| | |
2 3 4
_|_ _|_
| | | | |
5 6 7 8 9
|
10
I want to create a function that returns the terminating nodes of
of this tree below a certain level i.e. if I input 1 to the function
I need it to return 5,6,3,7,8,10. If I input 4 to the function I would
get 7,8,10. I have written recursive functions which return all nodes
on a branch of a tree but I can't think of a way to return the end nodes
does anyone know of a solution?
I haven't programmed in PL/pgSQL in a while, but I'll write some pseudo
code. I think the code should be similar:
func(int node)
{
dynamic_array s;
dynamic_array leaves;
int top, count, leaf_id, popped, child;
leaf_id = top = 0;
s[top] = node;
count = 1;
// to a depth first search
while(count != 0)
{
popped = s[top];
top--;
count--;
foreach(select pc.child_id into child from parent_child pc where
pc.parent_id = popped)
{
select * from parect_child pc where parent_id = child;
// a count of zero indicates that child node has no children
if(count_of_above_query = 0)
{
leaves[leaf_id] = child;
leaf_id++;
}
else
{
// not a leaf, so add it to the stack for the next time through
// the loop
top++;
s[top] = child;
count++;
}
}
}
return leaves;
}
Regards,
Yasir
---------------------------(end of broadcast)---------------------------
TIP 2: Don't 'kill -9' the postmaster
