單表格中的鄰接樹

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 
) 

*/ 

?>