Construire une vue d'arbre

Question

Je suis un peu perplexe sur ce problème et j'y pense depuis un moment maintenant. J'ai une table dans ma base de données qui contient des tâches. Chaque tâche peut avoir une tâche parent en maintenant sa clé primaire dans le champ parent_id. Je n'ai aucune limite sur la profondeur de ces tâches.

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

Une tâche sans id_parent est un « projet » et toutes les tâches peuvent être regroupées en groupes de travail en partageant une tâche parent. Je voudrais maintenant remplir une boîte de sélection HTML avec tous les descendants du projet.

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

Comment puis-je faire à ce sujet? J'imagine qu'une sorte de fonction récursive est en ordre, mais je n'arrive pas vraiment à comprendre comment s'y prendre.

Toute aide serait grandement appréciée. :)

Answer 1

Je vous recommande fortement de lire cet article à propos de storing hierarchical data in a database. Il y a deux algorithmes discutés ici, et selon vos besoins, l'un ou l'autre pourrait être approprié.

contiguïté Liste modèle

C'est ce que vous avez actuellement. Chaque nœud de l'arborescence stocke une référence à son parent, et vous pouvez déterminer de manière récursive le chemin d'un nœud en sélectionnant chaque niveau d'un arbre et en itérant à travers les nœuds. Ceci est simple à implémenter, mais l'inconvénient est que pour déterminer un chemin spécifique vers un nœud, des requêtes récursives sont requises. Si votre arbre est sujet à beaucoup de changements (c'est-à-dire écrit), c'est une bonne façon de procéder, car trouver dynamiquement chaque nœud fonctionne bien avec un arbre en constante évolution. Si c'est lourd, vous avez un peu de surcharge dans la récursivité.

modifié Précommande Arbre Traversal

Mon préféré, il est un algorithme très propre. Au lieu de stocker une référence au parent (ce que vous pouvez faire de toute façon à des fins de commodité), vous stockez une référence aux nœuds "left" et "right" pour chaque nœud donné. Le chemin complet vers un nœud peut être déterminé dans une seule requête select, ou inversement, tous les enfants d'un nœud. L'algorithme est plus difficile à mettre en œuvre, mais il présente des avantages en termes de performances pour les arborescences en lecture lourde. L'inconvénient est que chaque fois qu'un nœud est déplacé ou ajouté, des branches entières de l'arbre doivent être recalculées, de sorte qu'il peut ne pas convenir aux ensembles de données à écriture forte.

De toute façon, espérons que cet article vous donne quelques idées. C'est un bon.

Answer 2

Ceci est un exemple de la façon dont vous pouvez traverser récursivement votre base de données pour configurer un formulaire HTML. C'est une implémentation de ce que zombat appelle un "modèle de liste d'adjacence".

Il utilise deux fonctions: une pour obtenir simplement les éléments de «premier niveau» (projets); et une récursive, pour obtenir tous les enfants d'un élément donné. Je l'utilise ensuite pour remplir un formulaire HTML.

<?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

Veuillez avoir cette fonction pour avoir une vue arborescente avec un pointillé. Je l'ai fait pour l'option de boîte de sélection.

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); 
    } 
}