TREE Structure:
A tree is a recursive structure that usually maps an ordered set of data from an internal definition to some data space. Tree parts are often named after their contemporaries in family trees; trees contain nodes known as parent, child, and sibling. Trees are made of nodes, which can contain both data to be stored and always link to further levels in the tree. Trees are often formed from a single node known as root; alternatively, trees may be built from a set of original nodes--this is known as a forest of trees
Representing TREE in a table:
Amazing DFS:
The general idea behind a depth first search beginning at a starting node A is follows. First we examine the starting node A. Then we examine each node N along a path P which begins at A. That is we process a neighbor of A, then neighbor of (neighbor of A) and so on. After coming to the “dead end” that is, to the end of path P, we backtrack on P until we continue along another path P. And so on.
Pre order Traversal:
The first depth-first traversal method we consider is called preorder traversal. Preorder traversal is defined recursively as follows. To do a preorder traversal of a general tree:
1. Visit the root first; and then
2. Do a preorder traversal each of the sub trees of the root one-by-one in the order given.
Algorithm (DFS):
dfs(graph G)
{
list L = empty
tree T = empty
choose a starting vertex x
search(x)
while(L is not empty)
{
remove edge (v, w) from beginning of L
if w not yet visited
{
add (v, w) to T
search(w)
}
}
}
search(vertex v)
{
visit v
for each edge (v, w)
add edge (v, w) to the beginning of L
}
Example Code (PHP - mysql):
<?php
function cats_tree($id = 0,$table)
{
static $categs = array ();
static $level = 0;
$level ++;
$sql = "SELECT category_id, category_name FROM ".$table." WHERE parent = ". $id ." ORDER BY sibling_order";
$result = mysql_query($sql);
while ($row_category = mysql_fetch_assoc($result))
{
$rs[] = $row_category;
}
if (isset($rs)) {
foreach ($rs as $row) {
$categs[$row['category_id']] = str_repeat('| ', $level -1) .'|__'. $row['category_name'];
cats_tree($row['category_id'],$table);
}
}
$level --;
return $categs;
}
$conn = mysql_connect("localhost", "USER", "PASS");
mysql_select_db("DB_NAME");
echo "<pre>";
print_r(cats_tree(0,"category"));
echo "</pre>";
?>
Output:
