Tree making

Question

I am a little fixated on this issue, and I have been thinking about it for a while. I have a table in my database that contains tasks. Each task can have a parent task by holding its primary key in the parent_id field. I have no limit to how deeply these tasks can be related.

+-----------+-------+-----+ | Field | Type | Key | +-----------+-------+-----+ | id | int | PRI | | parent_id | int | MUL | +-------------------+-----+ 

A task without parent_id is a "project", and all tasks can be grouped into task groups by sharing the parent task. Now I would like to fill in the HTML selection box with the entire descendant of the project.

 Task 1 -Task 1.1 -Task 1.2 -Task 1.2.1 -Task 1.2.2 -Task 1.3 Task 2 

How can i do this? I believe that some kind of recursive function is fine, but I cannot imagine how to do it.

Any help would be greatly appreciated. :)

Answer 1

I highly recommend that you read this article about storing hierarchical data in a database . Two algorithms are discussed there, and one of them may be appropriate depending on your needs.

Affection List Model

This is what you have. Each node of the tree stores a link to its parent, and you can recursively determine the path to the node by selecting each level of the tree and iterating through the nodes. This is easy to implement, but the disadvantage is that recursive queries are required to determine the specific path to the node. If your tree is subject to a lot of changes (i.e., Writes), this is a good way, since dynamically detecting each node works well with an ever-changing tree. If it reads-heavy, you have some recursion overhead.

Changed order tree traversal

My favorite, this is a very neat algorithm. Instead of storing a link to the parent (which you can do anyway for convenience), you store a link to the "left" and "right" nodes for each given node. The entire path to the node can be defined in a single select request or, conversely, all the children of the node. The algorithm is harder to implement, but it has performance advantages for trees with high strength. The disadvantage is that every time a node is moved or added, it is necessary to recalculate all branches of the tree, so it may not be suitable for datasets with a record.

In any case, hope the article gives you some ideas. This one good.

Answer 2

This is an example of how you can recursively traverse your database to customize an HTML form. This is an implementation of what a zombat is called an “adjacency list model”.

It uses two functions: just get top-level elements (projects); and one recursive, to get all the children of a given element. Then I use this to fill out the HTML form.

 <?php /** * Fetches all the projects and returns them as an array. * "Projects" meaning: tasks without a parent. * @return array */ function getProjects() { $sql = "SELECT id FROM tree WHERE parentID IS NULL"; $result = mysql_query($sql) or die(mysql_error()); $results = array(); while($row = mysql_fetch_assoc($result)) { $results[] = $row['id']; } return $results; } /** * Fetches all tasks belonging to a specific parent. * Adds HTML space entities to represent the depth of each item in the tree. * @param int $parent_id The ID of the parent. * @param array $data An array containing the dat, filled in by the function. * @param int $current_depth Indicates the current depth of the recursion. * @return void */ function getTasks($parent_id, &$data, $current_depth=1) { $sql = "SELECT id FROM tree WHERE parentID = {$parent_id}"; $result = mysql_query($sql) or die(mysql_error()); while($row = mysql_fetch_assoc($result)) { $data[] = str_repeat('&nbsp;', $current_depth) . '- ' . $row['id']; getTasks($row['id'], $data, $current_depth + 1); } } /* * Fetch all the data and set it up so it can be used in the HTML */ mysql_connect('localhost', 'usr', 'pwd'); mysql_select_db('test'); // Get all the projects, adding a "-" as the initial value of the box. $projects = array_merge(array('-'), getProjects()); // Fetch the tasks. // If no project has been selected, just show a "please select" $tasks = array(); if(isset($_GET['project']) && $_GET['project'] != '-') { getTasks($_GET['project'], $tasks); } else { $tasks = array('Select a project'); } mysql_close(); ?> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <title>Tree Select Example</title> <meta http-equiv="content-type" content="text/html; charset=UTF-8"> </head> <body> <form action="<?php echo $_SERVER['PHP_SELF']; ?>" method="get"> <select name="project" onchange="this.parentNode.submit();"> <?php foreach($projects as $_project) { $selected = ($_project == @$_GET['project']) ? ' selected' : ''; echo "<option value=\"{$_project}\"{$selected}>{$_project}</option>"; } ?> </select><br> <select name="tasks[]" multiple size="10"> <?php foreach($tasks as $_task) { echo "<option value=\"{$_task}\">{$_task}</option>"; } ?> </select><br> <input type="submit"> </form> <pre><?php print_r($_GET); ?></pre> </body> </html> 

Answer 3

please, you have this function in order to have a tree view with a dotted line with you - indicator. I made for the block selection option.

 function display_children($parent, $level) { // retrieve all children of $parent $output = ""; $result = mysql_query('SELECT * FROM treeview_items WHERE parent_id="'.$parent.'";'); while ($row = mysql_fetch_array($result)) { echo "<option value='".$row['id']."'>".str_repeat('--',$level).$row['name']."</option>" ."<br>"; display_children($row['id'], $level+1); } }