php - 从一组父子关系创建树结构

Question

我有一个数组数组，它​​保存图中节点之间的父子关系。每个嵌套数组的形式都是

array( 0 => parent_node_id, 1 => child_node_id )

所以在这个数组中:

0 => array(
   0 => 1
   1 => 3
)

两个节点为1和3，节点1和节点3之间存在父子关系(外层数组索引0无关)。

1 => array(
   0 => 3
   1 => 5
),

表示节点3和节点5之间的父子关系(1无关)。

这里是父子关系数组(注意外层数组的数组索引(0、1、2、3等)不代表任何东西):

0 => array(
   0 => 1
   1 => 3
),
1 => array(
   0 => 3
   1 => 5
),
2 => array(
   0 => 3
   1 => 7
),
3 => array(
   0 => 3
   1 => 9
),
4 => array(
   0 => 1
   1 => 10
),
5 => array(
   0 => 10
   1 => 15
)

这是它编码的数据结构的图形表示:

并且在代码格式中(尽管对于我以后可以生成 HTML 列表的数组结构的任何更好的想法将不胜感激!):

0 => array
   0 => 1
   1 => array
      0 => 3
      1 => array
         0 => 5
      2 => array
         0 => 7
      3 => array
         0 => 9
   2 => array
      0 => 10
      1 => array
         0 => 15

使用这个数组中的信息，我想生成一个树，然后我可以用它在 html 页面中构建一个菜单。如何仅使用我的父子关系数组来做到这一点？

我知道有许多类似的算法可用于堆栈溢出，但没有一个适用于多个根或我正在使用的特定数组输入结构。

Answer 1

我的贡献。数组中只有三种元素:

1. 父元素
2. 元素是 PARENT 和 CHILD
3. 子元素

基于这三个规则，您可以构建一个菜单:

1. 循环所有元素并按编号存储 parent 和 child 。

   result: 3 parents: 1, 3 and 10.
           6 children: 3, 5, 7, 9, 10 and 15.
   

2. 现在我们需要过滤这些结果:

   2a:孤独的 child 是 child 的一个元素，而不是 parent

   的元素

          result **real children**: 5, 7, 9, and 15 have no child of their own
   

   2b:通过从所有 child 中减去 LONLY CHILDREN 得到 PARENT/CHILD 组合

          result **parent/child**: 3 and 10 have a parent and child(ren)
   

   2c:通过从 PARENT 中减去 PARENT/CHILD 得到 OVERALL PARENT

          result: **real parent** is 1
   

3. 构建一个菜单，从真正的 child 开始，将他们添加到他们的合法父项中，然后将它们添加到整个父项中。

在代码中...

$arr=array(array(1,3),array(3,5),array(3,7),array(3,9),array(1,10),array(10,15));
$menu=array(1=>'menu 1',3=>'menu 3',5=>'menu 5',7=>'menu 7',9=>'menu 9',10=>'menu 10',15=>'menu 15');


  //1. loop array and store parents and children
foreach($arr as $k=>$v){
    $P[$v[0]]=$v[0];
    $PC[$v[1]]=$v[0];
    }
  //2a: filter out the real children
$C = array_diff_key($PC,$P);
  //2b: get the parent_child combinations 
$PC=array_diff_key($PC,$C);
  //3: Get the real parent 
$P=array_diff_key($P,$PC);

 //Sorting the arrays is only needed if the starting array is not ordered
ksort($P);
ksort($PC);
ksort($C);

  //3: Building a menu
  // Create LONELY CHILDS
foreach($C as $k=>$v){
    if(!isset($MC[$v])){$MC[$v]=array();}
    $MC[$v][]='<li>'.$menu[$k].'</li>';
    }

  // Build the PARENT-CHILD menu by adding the CHILDREN to their rightfull parents
foreach($PC as $k=>$v){
    if(!isset($MPC[$v])){$MPC[$v]=array();}
    // $MPC[$v][]='<ul><li>'.$menu[$k].'</li><ul>'.implode('',$MC[$k]).'</ul></ul>'; //(OLD) 
$MPC[$v][]='<ul><li>'.$menu[$k].'<ul>'.implode('',$MC[$k]).'</ul></li></ul>';  //**NEW**
}

  // Create the REAL PARENT
foreach($P as $k=>$v){
    if(!isset($MP[$v])){$MP[$v]=array();}
    $MP[$v][]='<ul><li>'.$menu[$k].implode('',$MPC[$k]).'</li></ul>';
    }

  //CREATE FINAL MENU
$menu=array();
foreach($MP as $k=>$v){
    $menu[]=implode('',$v);
    }
//$menu='<ul>'.implode('',$menu).'</ul>'; //(OLD)
$menu=implode('',$menu);  //**NEW**

echo $menu;

以上结果:

• 菜单 1
  • 菜单 3
    • 菜单 5
    • 菜单 7
    • 菜单9
  • 菜单 10
    • 菜单 15

EDIT 更改了两行以创建有效的 HTML

还有一个 new fiddle