árbol de adyacencia de una sola mesa

Question

He leído un montón de gente discutiendo listas anidadas, pero me preguntaba la manera de recorrer una lista adjacancy / árbol en PHP.

Tengo una tabla con: ID, título, parent_id

Y he seleccionado todos los registros hacia fuera en una matriz llamada $ páginas.

A continuación, el uso de este php:

function makeList($pages, $used) {
    if (count($pages)) {
        echo "<ul>";
        foreach ($pages as $page) {
            echo "<li>".$page['pag_title'];
            $par_id = $page['pag_id'];
            $subsql("SELECT * FROM pages WHERE pag_parent = ".$par_id."");

            // running the new sql through an abstraction layer
            $childpages = $dbch->fetchAll();
            makeList($childpages, $used, $lastused);
            echo "</li>";
        }
        echo "</ul>";
    }
}

Este tipo de obras, pero termino con cualquier submenú se repiten por ejemplo.

• Inicio
  • Noticias
    • Sub-noticias
  • artículos
    • artículo
• Noticias
  • Sub-noticias
• artículos
  • artículo
• Sub-noticias
• artículo

He intentado añadir el ID actual en una matriz que se pasa a través de la función, y luego usando in_array para comprobar si está allí, pero no he tenido la alegría de hacer eso.

Cualquier ayuda sería muy apreciada.

Tengo que analizar todo el árbol lo que la elección de los padres como 0 no es una opción

Answer 1

Desde hace ya SQL, usted no tiene que hacerlo fuera antes de la primera llamada a la función.

function makeList($par_id = 0) {
    //your sql code here
    $subsql("SELECT * FROM pages WHERE pag_parent = $par_id");
    $pages = $dbch->fetchAll();

    if (count($pages)) {
        echo '<ul>';
        foreach ($pages as $page) {
            echo '<li>', $page['pag_title'];
            makeList($page['pag_id']);
            echo '</li>';
        }
        echo '</ul>';
    }
}

Para almacenar más árbol como es posible que desee ver en este sitio: Almacenamiento Los datos jerárquicos en una base de datos .

Answer 2

Si crea un conjunto de páginas agrupadas por ID de padre es bastante fácil de construir de forma recursiva la lista. Esto sólo requerirá una consulta de base de datos.

<?php

 //example data
 $items = array(
    array('id'=>1, 'title'=>'Home', 'parent_id'=>0),
    array('id'=>2, 'title'=>'News', 'parent_id'=>1),
    array('id'=>3, 'title'=>'Sub News', 'parent_id'=>2),
    array('id'=>4, 'title'=>'Articles', 'parent_id'=>0),
    array('id'=>5, 'title'=>'Article', 'parent_id'=>4),
    array('id'=>6, 'title'=>'Article2', 'parent_id'=>4)
 );

 //create new list grouped by parent id
 $itemsByParent = array();
 foreach ($items as $item) {
    if (!isset($itemsByParent[$item['parent_id']])) {
        $itemsByParent[$item['parent_id']] = array();
    }

    $itemsByParent[$item['parent_id']][] = $item;
 }

 //print list recursively 
 function printList($items, $parentId = 0) {
    echo '<ul>';
    foreach ($items[$parentId] as $item) {
        echo '<li>';
        echo $item['title'];
        $curId = $item['id'];
        //if there are children
        if (!empty($items[$curId])) {
            makeList($items, $curId);
        }           
        echo '</li>';
    }
    echo '</ul>';
 }

printList($itemsByParent);

Answer 3

¿Dónde está la página $ viene? Es posible que tenga una vulnerabilidad de inyección SQL en su código si usted no está escapar de ella o el uso de una declaración preparada.

También la instrucción SELECT dentro de un bucle for salta como una mala práctica. Si la tabla no es tan grande, a continuación, seleccione el contenido de toda la mesa y luego recorrer el conjunto de resultados en PHP para construir la estructura de datos de árbol. Esto podría tomar hasta n * (n-1) / 2 iteraciones en el caso patológico de su árbol de ser una lista enlazada. Se detiene cuando todos los nodos se han añadido al árbol, o el número de nodos restantes sigue siendo el mismo de una iteración a la siguiente -. Esto significa que los nodos restantes no son hijos de su nodo raíz

Por otra parte, si su base de datos soporta consultas SQL recursivas, puede usar eso, y sólo seleccionará los nodos que son hijos de su nodo padre. Usted todavía tendrá que construir el árbol de objetos a sí mismo en PHP. La forma de la consulta sería algo como:

WITH temptable(id, title, parent_id) AS (
  SELECT id, title, parent_id FROM pages WHERE id = ?
  UNION ALL
  SELECT a.id, a.title, a.parent_id FROM pages a, temptable t
   WHERE t.parent_id = a.id
) SELECT * FROM temptable

Sustituir el '?' en la segunda línea con el ID de página de inicio.

Answer 4

La solución más simple sería más que, cuando usted está haciendo el selecto inicial para establecer $pages (que no se presenta), añadir una cláusula WHERE como:

WHERE pag_parent = 0

(o es nulo, dependiendo de cómo se está almacenando las páginas de "alto nivel").

De esa manera no va a seleccionar todos los niños inicialmente.

Answer 5

Cuando la mesa se hace grande, la recursividad puede conseguir difícil de manejar. Escribí un post sobre un método de recursión-menos: http://www.alandelevie.com/2008/07/12/recursion-less-storage-of-hierarchical-data-in-a-relational-database/

Answer 6

Búsqueda de matriz superior, todos los padres, y todos los hijos de un nodo (mejoras para la respuesta de Tom Haigh):

<?php

 //sample data (can be pulled from mysql)
 $items = array(
    array('id'=>1, 'title'=>'Home', 'parent_id'=>0),
    array('id'=>2, 'title'=>'News', 'parent_id'=>1),
    array('id'=>3, 'title'=>'Sub News', 'parent_id'=>2),
    array('id'=>4, 'title'=>'Articles', 'parent_id'=>0),
    array('id'=>5, 'title'=>'Article', 'parent_id'=>4),
    array('id'=>6, 'title'=>'Article2', 'parent_id'=>4)
 );

 //create new list grouped by parent id
 $itemsByParent = array();
 foreach ($items as $item) {
    if (!isset($itemsByParent[$item['parent_id']])) {
        $itemsByParent[$item['parent_id']] = array();
    }

    $itemsByParent[$item['parent_id']][] = $item;
 }

 //print list recursively 
 function printList($items, $parentId = 0) {
    echo '<ul>';
    foreach ($items[$parentId] as $item) {
        echo '<li>';
        echo $item['title'];
        $curId = $item['id'];
        //if there are children
        if (!empty($items[$curId])) {
            printList($items, $curId);
        }           
        echo '</li>';
    }
    echo '</ul>';
 }

printList($itemsByParent);


/***************Extra Functionality 1****************/

function findTopParent($id,$ibp){


    foreach($ibp as $parentID=>$children){ 

            foreach($children as $child){


            if($child['id']==$id){


             if($child['parent_id']!=0){

            //echo $child['parent_id'];
            return findTopParent($child['parent_id'],$ibp);

          }else{ return $child['title'];}

         }              
        }
}
}

$itemID=7;  
$TopParent= findTopParent($itemID,$itemsByParent);





/***************Extra Functionality 2****************/

function getAllParents($id,$ibp){ //full path

foreach($ibp as $parentID=>$nodes){ 

    foreach($nodes as $node){

        if($node['id']==$id){

             if($node['parent_id']!=0){

                $a=getAllParents($node['parent_id'],$ibp);
                array_push($a,$node['parent_id']);
                return $a;

              }else{
                    return array();
                  }

             }
    }
}
}


$FullPath= getAllParents(3,$itemsByParent);
print_r($FullPath);

/*
Array
(
[0] => 1
[1] => 2
)
*/

/***************Extra Functionality 3****************/

 //this function gets all offspring(subnodes); children, grand children, etc...
 function getAllDescendancy($id,$ibp){

 if(array_key_exists($id,$ibp)){

         $kids=array();
         foreach($ibp[$id] as $child){

            array_push($kids,$child['id']);

            if(array_key_exists($child['id'],$ibp))

$kids=array_merge($kids,getAllDescendancy($child['id'],$ibp));

             }

         return $kids;       

     }else{
            return array();//supplied $id has no kids
          }
 }

print_r(getAllDescendancy(1,$itemsByParent));
/*
Array
(
[0] => 2
[1] => 3
)
*/


print_r(getAllDescendancy(4,$itemsByParent));
/*
Array
(
[0] => 5
[1] => 6
)
*/


print_r(getAllDescendancy(0,$itemsByParent));
/*
Array
(
[0] => 1
[1] => 2
[2] => 3
[3] => 4
[4] => 5
[5] => 6
)

*/

?>