组装菜单(节点树)，其中只有父节点是已知的 [英] Assemble menu (tree of nodes), where only parent is known

问题描述

我有一个菜单导航，如下所示:

I have a menu navigation, like this:

 - Page 1
 - Page 2
   - Subpage A
   - Subpage B
   - Subpage C
 - Page 3
   - Subpage D
   - Subpage E 
     - Subsubpage I
     - Subsubpage II
 - Page 4
   - Subpage F

但是我使用的 CMS 会吐出一棵扁平的树，只显示父级(而不是它们所在的级别).像这样:

But the CMS I use spits out a flat tree, only displaying the parent (not which level they're on). Like so:

$orig_tree = [
  [
    'db_id' => 1,
    'name' => 'Page 1',
    'parent' => 0
  ],
  [
    'db_id' => 2,
    'name' => 'Page 2',
    'parent' => 0
  ],
    'db_id' => 3,
    'name' => 'Subpage A',
    'parent' => 2
  ],
  [
    'db_id' => 4,
    'name' => 'Subpage B',
    'parent' => 2
  ],
  [
    'db_id' => 5,
    'name' => 'Subpage C',
    'parent' => 2
  ],
  [
    'db_id' => 6,
    'name' => 'Page 3',
    'parent' => 0
  ],
  [
    'db_id' => 7,
    'name' => 'Subpage D',
    'parent' => 6
  ],
  [
    'db_id' => 8,
    'name' => 'Subpage E',
    'parent' => 6
  ],
  [
    'db_id' => 9,
    'name' => 'Subsubpage I',
    'parent' => 8
  ],
  [
    'db_id' => 10,
    'name' => 'Subsubpage II',
    'parent' => 8
  ],
  [
    'db_id' => 11,
    'name' => 'Page 4',
    'parent' => 0
  ],
  [
    'db_id' => 12,
    'name' => 'Subpage F',
    'parent' => 11
  ]
]

这些信息存储在数据库中，因此必须在运行时进行组装(而且它非常大)，这意味着我希望尽可能使其性能友好.

These information are stored in the database, so it has to be assembled in runtime (and it's really large), which means that I would like to make it as performance-friendly as possible.

那么我该如何组合这棵树呢?

So how do I put together this tree? ​

假设

• 我很确定平坦的原始树总是井井有条.这样第一个条目将始终是根节点(而不是另一个节点的子节点之一).并且子节点将紧跟在父节点之后.
• 目前我最多有 3 个级别.但如果解决方案适用于任意数量的级别，那就太酷了.

我正在为所有这些操作创建一个对象和方法.这只是为了以最快的方式说明解决方案，使问题更容易消化.

I'm making an object and making methods for all these operations. This is just to illustrate the solution in the fastest manner, to make the problem more digestible.

尝试 1 - 递归

递归将是最漂亮的.我尝试了几次，但我无法让它工作.这是我做到的程度:

Recursion would be the prettiest. I had a few go's at it, but I couldn't get it to work. Here is how far I made it:

  __constructor( $orig_tree ){
  $final_tree = [];
    foreach( $orig_tree as $orig_node ){
      $final_tree = $this->addNode( $orig_node, $final_tree );
    }
  } 

  private function addNode( $node, $final_tree ){
    if( $node['parent'] == 'None' ){
      $final_tree[] = $node;
    } else {
      // This is where I get stuck...
      $this->findParentNode( $node, $final_tree ); // This is wrong
    }
  }

我不确定，是否应该从根部到叶部进行处理，或者相反.或者最终的树是否应该传递给递归方法.

I'm not sure, if I should work it from the root to the leaves or the other way around. Or if the final tree should be passed to the recursive method or not.

尝试 2 - 蛮力丑陋

首先组装所有的树枝，然后通过树枝组装树.

​First assemble all the branches, and then go through the branches and assemble the tree.

public static function makeMenu( $orig_tree ){
  $branches = [];
  $final_tree = [];

  // Assemble branches
  foreach( $orig_tree as $node ){
    $branches[ $node->parent ][] = $node;
  }

  $final_tree = $branches[0]; // Set root level manually
  unset( $branches[0] );

  // Go through the root nodes and see if any branches have them as parents
  foreach( $final_tree as &$root_node ){
    if( array_key_exists( $root_node->db_id, $branches ) ){
      $root_node->children = $branches[ $root_node->db_id ];
      unset( $branches[ $root_node->db_id ] );

      // Go through the newly added children and see if they have any branches, with them as parents
      foreach( $root_node->children as &$child ){
        if( array_key_exists( $child->db_id, $branches ) ){
          $child->children = $branches[ $child->db_id ];
          unset( $branches[ $child->db_id ] );
        }
      }
    }
  }

  if( !empty( $branches ) ){
    // Throw error.
    echo 'Something has gone wrong!'; // All branches should have been removed with above code 
    die();
  }


  return $final_tree;
}

这行得通，但很丑.

推荐答案

<?php

function makeMenu( $orig_tree ){
    $parent_set = [];
    $result = [];
    foreach($orig_tree as $node){
        $node['children'] = [];
        if($node['parent'] == 0){
            $result[] = $node;
            $parent_set[$node['db_id']] = &$result[count($result) - 1];
        }else{
            $parent = &$parent_set[$node['parent']];
            $parent['children'][] = $node;
            $parent_set[$node['db_id']] = &$parent['children'][count($parent['children']) - 1];
        }
    }
    
    return $result;
}

---

在上面的代码中，正如你提到的，父条目总是在子条目之前

• 我们维护一个变量 $result，我们只在其中添加父级 0 节点.
• 重要的部分是 $parent_set，我们在 & 地址说明符的帮助下存储 $result 中存在的节点的地址.
• 现在，每当我们想要向 $result 添加任何新节点时，我们都会从 $parent_set 中获取它的父节点并将当前节点添加到它的 children 数组.
• 完成后，我们再次在父节点的children 数组条目的帮助下更新$result 中当前节点的地址.

• We maintain a variable $result where we just add parent level 0 nodes.
• Important part is the $parent_set where we store the addresses of nodes present in $result with the help of & address specifier.
• Now, whenever we want to add any new node to $result, we fetch it's parent node from $parent_set and add current node in its children array.
• Once done, we again update current node's address in $result with the help of parent's children array entry.

这篇关于组装菜单(节点树)，其中只有父节点是已知的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！