How to Efficiently Convert Parent-Child Relationships into Nested Hierarchical Trees?

Converting Parent-Child Relationships into Hierarchical Trees

Problem:

Given a set of name-parentname pairs representing hierarchical relationships, the task is to transform them into a minimal number of nested tree structures. For instance, with the following input:

Child : Parent
    H : G
    F : G
    G : D
    E : D
    A : E
    B : C
    C : E
    D : NULL

The expected output is a series of hierarchical trees:

D
├── E
│   ├── A
│   │   └── B
│   └── C   
└── G
    ├── F
    └── H

The goal is to generate nested

elements with each
• containing the child's name.

  Solution:

  To effectively convert the input into a hierarchical tree structure, a recursive approach is employed. The following functions are defined:

  function parseTree($tree, $root = null): array
  {
      $return = [];
      foreach ($tree as $child => $parent) {
          if ($parent == $root) {
              unset($tree[$child]);
              $return[] = [
                  'name' => $child,
                  'children' => parseTree($tree, $child),
              ];
          }
      }
      return empty($return) ? null : $return;    
  }
  
  function printTree($tree)
  {
      if (!is_null($tree) && count($tree) > 0) {
          echo '<ul>';
          foreach ($tree as $node) {
              echo '<li>'.$node['name'];
              printTree($node['children']);
              echo '</li>';
          }
          echo '</ul>';
      }
  }

  Usage:

  $result = parseTree($tree);
  printTree($result);

  This approach first parses the input, creating a hierarchical tree structure in an array format. Subsequently, it traverses the tree, generating the desired nested

  elements.

  Combined Function:

  For a more efficient implementation, a combined version of the two functions can be created:

  function parseAndPrintTree($root, $tree)
  {
      if (!is_null($tree) && count($tree) > 0) {
          echo '<ul>';
          foreach ($tree as $child => $parent) {
              if ($parent == $root) {                    
                  unset($tree[$child]);
                  echo '<li>'.$child;
                  parseAndPrintTree($child, $tree);
                  echo '</li>';
              }
          }
          echo '</ul>';
      }
  }

  The above is the detailed content of How to Efficiently Convert Parent-Child Relationships into Nested Hierarchical Trees?. For more information, please follow other related articles on the PHP Chinese website!