Algoritmo recursivo para un arbol

[vart001]

Algoritmo recursivo para un arbol
Este código nos permitirá  comprender la elaboración de diagramas de arbol, esta técnica  es utilizada por ejemplo en la elaboración de los esquemas de respuestas  en los foros de discusion.                                                               

Tenemos una tabla de dos dimensiones con los elementos a ordenar. Cada elemento tiene su propio índice, el índice de su elemento padre (si es 0 el es un elemento padre) y un texto.

El algoritmo lo ordena de forma que quede un arbol ordenado con todos los elementos hijos debajo de us elementos padre. El resultado de este ejemplo seria algo así:


BOISSONS
    Alcool
        biere
        porto
    Sans alcool
        eau
ALIMENTS
    Legumes
        salades
            batavia
            laitue
        carottes
        tomates
    viandes
        Jambon
        steack haché
DIVERS
    Dentifrice
    sacs poubelles
    lessive


El código del programa es el siguiente:



<?php

// ------------------------------------------------------------------------- //
// Autor:  Christophe GORGERY                                                //
// Email:  webmaster@desperaweb.com                                          //
// Web:   
Para ver este enlace Registrate o Inicia Sesion                                            //
// ------------------------------------------------------------------------- //

function espace($rang) {
  $ch="";
  for ($x=0;$x<$rang;$x++) {
      $ch=$ch."&nbsp;&nbsp;&nbsp;&nbsp;";
  }
return $ch;
}

/*fonction récursive d'affichage de l'arbre
    $tab  :tableau des éléments
    $pere :index de l'élément courrant
    $rang :décallage de l'élément
*/
function recur($tab,$pere,$rang) {

  //ballayage du tableau
  for ($x=0;$x<count($tab);$x++) {

    //si un élément a pour père : $pere
    if ($tab[$x][1]==$pere) {

       //on l'affiche avec le décallage courrant
       echo espace($rang).$tab[$x][2]."<BR>";

       /*et on recherche ses fils
         en rappelant la fonction recur()
       (+ incrémentation du décallage)*/
       recur($tab,$tab[$x][0],$rang+1);
    }
  }
}

/*-------------------- MAIN -----------------------
  tableau des éléments de l'arbre:
    c'est un tableau ÃÂ  2 dimensions.
    Une ligne représente un élément : data[$x]
    chaque ligne est décomposée en 3 données:
      - l'index de l'élément
      - l'index de l'élément parent
      - la chaîne ÃÂ  afficher
    ie: data[]= array (index, index parent, chaine )
*/
  //il faut d'abord déclarer un élément racine de l'arbre
  $data[] = array(0,-1,"racine");

  //puis tous les éléments enfants
  $data[] = array(1,0,"BOISSONS");
  $data[] = array(2,0,"ALIMENTS");
  $data[] = array(3,1,"Alcool");
  $data[] = array(4,1,"Sans alcool");
  $data[] = array(5,2,"Legumes");
  $data[] = array(6,5,"salades");
  $data[] = array(7,6,"batavia");
  $data[] = array(8,6,"laitue");
  $data[] = array(9,5,"carottes");
  $data[] = array(10,5,"tomates");
  $data[] = array(11,2,"viandes");
  $data[] = array(12,11,"Jambon");
  $data[] = array(13,11,"steack haché");
  $data[] = array(14,0,"DIVERS");
  $data[] = array(15,14,"Dentifrice");
  $data[] = array(16,14,"sacs poubelles");
  $data[] = array(17,14,"lessive");
  $data[] = array(18,3,"biere");
  $data[] = array(19,3,"porto");
  $data[] = array(20,4,"eau");

  //appelle de la fonction récursive (ammorce)
  //avec recherche depuis la racine.
  recur($data,0,0);

?>