Wie lassen sich Eltern-Kind-Beziehungen effizient in verschachtelte hierarchische Bäume umwandeln?

Eltern-Kind-Beziehungen in hierarchische Bäume umwandeln

Problem:

Gegeben sei eine Reihe von Name-Eltern-Name-Paaren, die hierarchische Strukturen darstellen Die Aufgabe besteht darin, diese Beziehungen in eine minimale Anzahl verschachtelter Baumstrukturen umzuwandeln. Zum Beispiel mit der folgenden Eingabe:

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

Die erwartete Ausgabe ist eine Reihe hierarchischer Bäume:

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

Das Ziel besteht darin, verschachtelte

Elemente mit jedem
• enthält den Namen des Kindes.

  Lösung:

  Um die Eingabe effektiv in eine hierarchische Baumstruktur umzuwandeln, wird ein rekursiver Ansatz verwendet. Die folgenden Funktionen sind definiert:

  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>';
      }
  }

  Verwendung:

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

  Dieser Ansatz analysiert zunächst die Eingabe und erstellt eine hierarchische Baumstruktur in einem Array-Format. Anschließend durchläuft es den Baum und generiert das gewünschte verschachtelte

  Elemente.

  Kombinierte Funktion:

  Für eine effizientere Implementierung kann eine kombinierte Version der beiden Funktionen erstellt werden:

  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>';
      }
  }

  Das obige ist der detaillierte Inhalt vonWie lassen sich Eltern-Kind-Beziehungen effizient in verschachtelte hierarchische Bäume umwandeln?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!