单表格中的邻接树

Question

我读过很多讨论嵌套列表的人，但我想知道如何在PHP中通过邻接列表/树进行迭代。

我有一个表：ID，标题，PARENT_ID

而且我选择的所有记录了到数组名为$页。

然后使用这个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>"; 
    } 
} 

这种类型的作品，但我最终被重复例如任意子菜单

• 首页
  • 新闻
    • 次新闻
  • 文章
    • 文章
• 新闻
  • 次新闻
• 文章
  • 文章
• 次新闻
• 第

我试着将当前的id添加到数组中，通过函数传递，然后使用in_array检查它是否存在，但我没有这样做的喜悦。

任何帮助将不胜感激。

我需要分析整个树，以便选择父为0是不是一种选择

Answer 1

由于它已经完成了SQL，所以在第一次函数调用之前，您不必在外面执行该操作。

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

为了存储更多的树，你可能想看看这个网站：Storing Hierarchical Data in a Database。

Answer 2

最简单的修复也只是，当你正在做的初始选择设定$pages（你不显示） ，添加一个WHERE子句，如：

WHERE pag_parent = 0 

（或IS NULL，具体取决于您如何存储“顶级”页面）。

这样你最初不会选择所有的孩子。

Answer 3

$ page从哪里来？如果您没有转义或使用准备好的语句，那么您的代码中可能存在sql注入漏洞。

此外for循环中的SELECT语句跳出作为一个不好的做法。如果表格不是那么大，那么选择整个表格的内容，然后遍历PHP中的结果集来构建树型数据结构。在树的病态情况下，这可能会花费n *（n-1）/ 2次迭代作为链表。当所有节点都添加到树中时停止，或者从一次迭代到下一次迭代剩余节点的数量保持不变 - 这意味着其余节点不是根节点的子节点。

或者，如果您的数据库支持递归SQL查询，则可以使用该查询，并且它只会选择父节点的子节点。您仍然必须自己在PHP中构建树对象。查询的形式如下：

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 

替换'？'在起始页面ID的第二行。

Answer 4

如果您创建按父级ID分组的页面数组，则递归构建列表相当容易。这将只需要一个数据库查询。

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

当该表变大时，递归会变得笨重。我写了一个博客帖子大约递归少方法：http://www.alandelevie.com/2008/07/12/recursion-less-storage-of-hierarchical-data-in-a-relational-database/

Answer 6

寻找顶部家长，所有家长和节点的所有儿童（汤姆·黑格的回答增强）：

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

*/ 

?>