質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.93%

再帰処理のアルゴリズム

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 2,448

owqbpu

score 13

前提・実現したいこと

PHP初心者です。
一次元の配列から、階層構造の配列を作成したいのですが再帰処理を使用したことがなく、うまく出来ずにいます。

元データから、2つの結果を導きたいです。
導き出した配列はメニュー用に表示したりして使おうと思っています。

わかりやすい方法、短く書くことが出来る方法、やテクニカルな方法など色々な形を見たいです。
もしくは、結果の構造はこっちのほうが良いよ、などのアドバイスなどもあれば是非聞きたいです。
(元はparentなのにchildrenを作ろうとしていることに少し違和感があります)

よろしくお願いします!

// 元データ
$original = [
        // id, 親id, 名前
    ['id' => 1, 'parent' => 0, 'name' => 'aaaa'],
    ['id' => 2, 'parent' => 0, 'name' => 'bbbb'],
    ['id' => 3, 'parent' => 1, 'name' => 'cccc'],
    ['id' => 4, 'parent' => 2, 'name' => 'dddd'],
    ['id' => 5, 'parent' => 3, 'name' => 'eeee'],
];
// 1つ目はこの結果が欲しい
$result1 = [
    1 => [
        'catname' => 'aaaa', // 名前を連結する
        'name' => 'aaaa',
        'children' => [
            3 => [
                'catname' => 'aaaa cccc',
                'name' => 'cccc',
                'children' => [
                    5 => [
                        'catname' => 'aaaa cccc eeee',
                        'name' => 'eeee',
                        'children' => [],
                    ],
                ],
            ],
        ],
    ],
    2 => [
        'catname' => 'bbbb',
        'name' => 'bbbb',
        'children' => [
            4 => [
                'catname' => 'bbbb dddd',
                'name' => 'dddd',
                'children' => [],
            ],
        ],
    ],
];
// 2つ目はこの結果が欲しい
$result2 = [
    1 => 'aaaa',
    2 => 'bbbb',
    3 => 'aaaa cccc',
    4 => 'bbbb dddd',
    5 => 'aaaa cccc eeee',
];

 追記

@mts10806さん

途中のソース

半端ですがこちらです。id => 5が出来ていません。また、catnameも出来ていません。
引数の参照渡しについて今ひとつ理解できていませんが、これがわかりにくくさせてる気もしています。
再帰処理は参照渡しが必要になってしまうものですか?returnで返したほうがわかりやすい気がしています。
子要素を作る処理が2回出てきている('children' => []を2箇所でしてる)ので、何か違うなとも思っています。

function recursive(&$result, $array) {
    if ($array['parent'] === 0) {
        $result[$array['id']] = [
            'name' => $array['name'],
            'children' => [],
        ];
    } else {
        if (isset($result[$array['parent']])) {
            $result[$array['parent']]['children'][$array['id']] = [
                'name' => $array['name'],
                'children' => [],
            ];
        } else {
            foreach ($result as $array2) {
                recursive($array2['children'], $array['parent']);
            }
        }
    }
}

$original = [
    ['id' => 1, 'parent' => 0, 'name' => 'aaaa'],
    ['id' => 2, 'parent' => 0, 'name' => 'bbbb'],
    ['id' => 3, 'parent' => 1, 'name' => 'cccc'],
    ['id' => 4, 'parent' => 2, 'name' => 'dddd'],
    ['id' => 5, 'parent' => 3, 'name' => 'eeee'],
];

$result = [];
foreach ($original as $array) {
    recursive($result, $array);
}
var_dump($result);
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • yambejp

    2017/06/27 15:44

    子供の配列はかならずparentの配列の後に出現すると担保されていますか?

    キャンセル

  • owqbpu

    2017/06/27 15:50

    はい。['id' => 6, 'parent' => 7, 'name' => 'ffff'], ['id' => 7, 'parent' => 0, 'name' => 'gggg'], の様なものはなく、絶対にparentが先に存在します。

    キャンセル

  • m.ts10806

    2017/06/27 15:51

    「うまく出来ずに」とのことなので苦労して組まれている途中のソースがあるかと思います。そのソースからアドバイスをもらえることもあるので、現在組まれているソースのご提示もお願いします。

    キャンセル

  • owqbpu

    2017/06/27 15:53

    parentが先に存在しない場合の方法も可能であれば見たいです。

    キャンセル

回答 3

+2

ちょっとゴテゴテしてて申し訳ないです。

<?php
function recursive($source, &$result1, &$result2, $parent, $categories = []) {
  foreach ($source as $s) {
    if ($s['parent'] == $parent) {
      $new_categories = array_merge($categories, [$s['name']]);
      $id = $s['id'];
      $category = implode(' ',$new_categories);
      $result1[$id] = [
        'catname'  => $category,
        'name'     => $s['name'],
        'children' => []
      ];
      $result2[$id] = $category;
      recursive($source, $result1[$id]['children'],$result2,$id,$new_categories);
    }
  }
}

$original = [
    ['id' => 1, 'parent' => 0, 'name' => 'aaaa'],
    ['id' => 2, 'parent' => 0, 'name' => 'bbbb'],
    ['id' => 3, 'parent' => 1, 'name' => 'cccc'],
    ['id' => 4, 'parent' => 2, 'name' => 'dddd'],
    ['id' => 5, 'parent' => 3, 'name' => 'eeee'],
];

$result1 = [];
$result2 = [];
recursive($original, $result1, $result2, 0);
ksort($result2);
var_dump($result1);
var_dump($result2);


結果

array(2) {
  [1]=>
  array(3) {
    ["catname"]=>
    string(4) "aaaa"
    ["name"]=>
    string(4) "aaaa"
    ["children"]=>
    array(1) {
      [3]=>
      array(3) {
        ["catname"]=>
        string(9) "aaaa cccc"
        ["name"]=>
        string(4) "cccc"
        ["children"]=>
        array(1) {
          [5]=>
          array(3) {
            ["catname"]=>
            string(14) "aaaa cccc eeee"
            ["name"]=>
            string(4) "eeee"
            ["children"]=>
            array(0) {
            }
          }
        }
      }
    }
  }
  [2]=>
  array(3) {
    ["catname"]=>
    string(4) "bbbb"
    ["name"]=>
    string(4) "bbbb"
    ["children"]=>
    array(1) {
      [4]=>
      array(3) {
        ["catname"]=>
        string(9) "bbbb dddd"
        ["name"]=>
        string(4) "dddd"
        ["children"]=>
        array(0) {
        }
      }
    }
  }
}
array(5) {
  [1]=>
  string(4) "aaaa"
  [2]=>
  string(4) "bbbb"
  [3]=>
  string(9) "aaaa cccc"
  [4]=>
  string(9) "bbbb dddd"
  [5]=>
  string(14) "aaaa cccc eeee"
}

result2がどうしてもキー順にならないので、関数外でソートしてあげないとダメです。
なかなか面白かったです。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

checkベストアンサー

+1

再帰で配列を使うとリファレンスが必要なので理解しづらいですね。

$headで定義したようにダミーの親を作ると短く書けるようになると思います。
print_r($head)すると0の下に全て追加されているのがわかります。

<?php
function transform(&$parent, $parentId, $catname, &$item) {
  if ($parentId == $item['parent']) {
    $parent['children'][$item['id']] = [
      'catname' => $catname . " " . $item['name'],
      'name' => $item['name'],
      'children' => [],
    ];
    return;
  }

  foreach ($parent['children'] as $id => &$child) {
    transform($child, $id, $catname . " " . $child['name'], $item);
  }
}

function categories($node)
{
  $cats = [];
  foreach ($node['children'] as $id => $child) {
    $cats[$id] = $child['catname'];
    $cats = $cats + categories($child);
  }
  ksort($cats);
  return $cats;
}

$original = [
        // id, 親id, 名前
    ['id' => 1, 'parent' => 0, 'name' => 'aaaa'],
    ['id' => 2, 'parent' => 0, 'name' => 'bbbb'],
    ['id' => 3, 'parent' => 1, 'name' => 'cccc'],
    ['id' => 4, 'parent' => 2, 'name' => 'dddd'],
    ['id' => 5, 'parent' => 3, 'name' => 'eeee'],
];

// $result1
$head = ['children' => []];
foreach ($original as &$item) {
  transform($head, 0, '', $item);
}
print_r($head['children']);

// $result2
print_r(categories($head));
Array
(
    [1] => Array
        (
            [catname] =>  aaaa
            [name] => aaaa
            [children] => Array
                (
                    [3] => Array
                        (
                            [catname] =>  aaaa cccc
                            [name] => cccc
                            [children] => Array
                                (
                                    [5] => Array
                                        (
                                            [catname] =>  aaaa cccc eeee
                                            [name] => eeee
                                            [children] => Array
                                                (
                                                )

                                        )

                                )

                        )

                )

        )

    [2] => Array
        (
            [catname] =>  bbbb
            [name] => bbbb
            [children] => Array
                (
                    [4] => Array
                        (
                            [catname] =>  bbbb dddd
                            [name] => dddd
                            [children] => Array
                                (
                                )

                        )

                )

        )

)
Array
(
    [1] =>  aaaa
    [2] =>  bbbb
    [3] =>  aaaa cccc
    [4] =>  bbbb dddd
    [5] =>  aaaa cccc eeee
)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/06/28 12:28

    みなさまありがとうございます。

    @kodai さん
    > $headで定義したようにダミーの親を作る
    この様な考えが全く無かったので、目からウロコでした!勉強になりました!

    キャンセル

+1

抽出項目は未調整ですがこんな感じで

$a=[
  ['id' => 1, 'parent' => 0, 'name' => 'aaaa'],
  ['id' => 2, 'parent' => 0, 'name' => 'bbbb'],
  ['id' => 3, 'parent' => 1, 'name' => 'cccc'],
  ['id' => 4, 'parent' => 2, 'name' => 'dddd'],
  ['id' => 5, 'parent' => 3, 'name' => 'eeee'],
  ['id' => 6, 'parent' => 3, 'name' => 'ffff'],
  ['id' => 7, 'parent' => 1, 'name' => 'gggg'],
];

$b=[];
foreach(array_reverse($a) as $data){$b[$data["id"]]=$data;}
foreach($b as $key=>$data){
  $p=$data["parent"];
  if(!isset($b[$key]["children"])) $b[$key]["children"]=[];
  if(array_key_exists($p,$b) ){
    if(!isset($b[$p]["children"])) $b[$p]["children"]=[];
    $b[$p]["children"]=array_replace([$key=>$b[$key]],$b[$p]["children"]);
    unset($b[$key]);
  }else{
    $b=array_replace([$key=>$data],$b);
  }
}
print_r($b);

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.93%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る