親子関係をネストされた階層ツリーに効率的に変換するにはどうすればよいですか?

親子関係を階層ツリーに変換する

問題:

階層を表す名前と親名のペアのセットが与えられたとします。関係を構築するには、それらを最小限の数のネストされたツリー構造に変換する必要があります。たとえば、次の入力の場合:

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

期待される出力は一連の階層ツリーです:

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

目標は、ネストされた

を生成することです。各
• を持つ要素

  解決策:

  入力を階層ツリー構造に効果的に変換するには、再帰的アプローチが使用されます。次の関数が定義されています:

  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 '

  '; foreach ($tree as $node) { echo '
  • '.$node['name']; printTree($node['children']); echo '
  '; } echo '
  '; } }

  使用法:

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

  このアプローチでは、まず入力を解析し、配列形式で階層ツリー構造を作成します。その後、ツリーを走査し、必要なネストされた

  を生成します。要素。

  結合関数:

  より効率的な実装のために、2 つの関数の結合バージョンを作成できます:

  function parseAndPrintTree($root, $tree)
  {
      if (!is_null($tree) && count($tree) > 0) {
          echo '

  '; foreach ($tree as $child => $parent) { if ($parent == $root) { unset($tree[$child]); echo '
  • '.$child; parseAndPrintTree($child, $tree); echo '
  '; } } echo '
  '; } }

以上が親子関係をネストされた階層ツリーに効率的に変換するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。