从一组父子关系中创建树形结构

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页面上使用它来构建菜单。如何仅使用我的父子关系数组来完成这个任务？

我知道stackoverflow上有很多类似的算法，但没有一个适用于多个根或我正在使用的特定数组输入结构。

- khernik

---

0 索引是父级，1 索引是它的子级。 - khernik

你能解释一下从数组1到数组2的逻辑吗？例如，那个null是从哪里来的？ - Michel

即使有图片，仍然不清楚这张图片是如何从平面数组表示中绘制出来的。现在更加混乱了：在您的文本树中有两个根，其中一个根在图片上。 - zerkms

重写并澄清了问题——现在应该可以理解了。 - i alarmed alien

不要重复说明外部索引的无关性，直接将它们删除即可。我认为它们会增加混乱。 - Yoshi

Answer 1

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

1. 父元素
2. 既是父元素又是子元素的元素
3. 子元素

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

1. 遍历所有元素，按编号存储父元素和子元素。

   结果：3个父元素分别为1、3和10。
           6个子元素分别为3、5、7、9、10和15。
   

2. 现在我们需要筛选这些结果：

   2a: 孤儿子是指在子元素中而不在父元素中的元素

          结果**真正的孩子**：5、7、9和15没有自己的子元素
   

   2b: 通过从所有子元素中减去孤儿子来获取父/子组合

          结果**父/子**：3和10有父元素和子(们)
   

   2c: 通过从父元素中减去父/子来获取整体父元素

          结果：**真正的父元素**是1
   

3. 构建一个菜单，从真正的子元素开始，将它们添加到它们正确的父元素中，并将它们添加到整体父元素中。

在代码中...

$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

编辑：更改两行以创建有效的HTML

还有一个新的小工具。

- Michel

---

@我惊动了外星人。已经改正了。 - Michel

我不是原帖作者，所以谁知道期望的结构是什么，但你的HTML现在是有效的。 :^) - i alarmed alien

@i 惊讶的外星人。太晚了，我才发现是你而不是 OP 发表评论。无论如何，还是谢谢你的评论。 - Michel

至少我们现在都有完美的HTML，即使OP从未查看这些答案... ;^) - i alarmed alien

Answer 2

根据评论，OP表示这将用于构建菜单系统，因此我编写了一些代码，将数组转换为更易理解的数据结构，构建嵌套列表（适用于用作菜单），并使用第二个$content数组中的数据填充列表项。对于实际应用，$content中的数据可以是一组链接或任何所需内容。

# input array
$array = array(
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
));

# associative array of node IDs and the node contents
# obviously for a menu, the node contents will probably be links
$content = array(
  1 => 'ape',
  3 => 'bear',
  5 => 'cow',
  7 => 'dog',
  9 => 'elephant',
  10 => 'frog',
  15 => 'giraffe'
);

$tree = [];

# simplify the parent-child 
foreach (array_values($array) as $a) {
  $tree[ $a[0] ][ $a[1] ] = 'value';
}

$roots = get_root($array);

# start our initial list...    
$str = '<ul>';
foreach (array_keys($roots) as $r) {
  $str .= build_tree( $tree, $content, $r );
}
$str .= "</ul>";
echo $str;

/**
 * build_tree($tree, $content, $n)
 * 
 * builds an html representation of a tree using $tree, a data structure
 * containing parent-child relationships, $content, the content of each
 * node of the tree, and $n, the current node in the tree. Calls itself
 * recursively when it encounters a subtree to be built
 *
 * @param array $tree 
 * @param array $content - assoc array of 
 * @param string $n - current node in the tree
 * @return string $html representing the tree
 */
function build_tree($tree, $content, $n) {
  $html = "<li>node id: $n; ".$content[$n]."</li>";
  # does $n exist in $tree -- i.e. does it have a child?
  if ( isset($tree[$n]) ) {
    # if so, start a new nested list
    $html .= '<li><ul>';
    # for each of the children of $n, our parent node,
    # run the build_tree code to create the html
    foreach (array_keys($tree[$n]) as $node) {
      $html .= build_tree($tree, $content, $node);
    }
    $html .= '</ul></li>';
  }
  return $html;
}

/**
 * get_root ( $input )
 *
 * input array format:
 * 0 => [ 0 => parent_node_id, 1 => child_node_id ],
 * 1 => [ 0 => parent_node_id2, 1 => child_node_id2 ],;
 *
 * takes an associative array of parent-child relationships
 * and makes two arrays, one containing all the parent nodes,
 * and one containing the child nodes. The root nodes are
 * those that appear in the parent node array but not the
 * child node array.
 *
 * @param array $input 
 * @return array $r - assoc arr. with root nodes as keys
 */
function get_root ($input) {
  $p = [];
  $c = [];
  $r = [];
  foreach ($input as $k => $v) {
    $p[ $v[0] ] = 1; # parent node
    $c[ $v[1] ] = 1; # child node
  }
  # find the array items in $p that aren't in $c
  foreach ($p as $k => $v) {
    if (! isset($c[$k]) ) {
      $r[$k] = 1;
    }
  }
  return $r;
}

以上代码的结果（使用此在线演示进行测试）：

• 节点 ID：1；内容：猿
• • 节点 ID：3；内容：熊
  • • 节点 ID：5；内容：牛
    • 节点 ID：7；内容：狗
    • 节点 ID：9；内容：大象
  • 节点 ID：10；内容：青蛙
  • • 节点 ID：15；内容：长颈鹿

原始 HTML（通过 HTML tidy 运行）：

<ul>
    <li>Node ID: 1; content: ape</li>
    <li>
      <ul>
        <li>Node ID: 3; content: bear</li>
        <li>
          <ul>
            <li>Node ID: 5; content: cow</li>
            <li>Node ID: 7; content: dog</li>
            <li>Node ID: 9; content: elephant</li>
          </ul>
        </li>
        <li>Node ID: 10; content: frog</li>
        <li>
          <ul>
            <li>Node ID: 15; content: giraffe</li>
          </ul>
        </li>
      </ul>
    </li>
</ul>

- i alarmed alien

---

你的HTML不符合验证规则;-)在节点9和节点15之后，你交换了</li>和</ul>。 - Michel