Рекурсия глубины дерева PHP-массив

Question

У меня есть следующий массив и вы хотите найти max. глубина его древовидной структуры. Но мой код возвращает 12, когда это должно быть 4 ... Я не очень хорош в рекурсии, так что это отчасти сводит меня с ума!

массив Декларация:

Array (
    [relation] => Array (

     [parent.item] => Array (
       [0] => cs 
       [1] => ls 
      ) 

     [cs.item] => Array (
       [0] => business 
       [1] => sporting_cultural 
       [2] => tourism 
       [3] => family 
       [4] => friend 
       [5] => student_family 
       [6] => transit 
       [7] => other_cases 
      ) 

     [business.item] => Array (
       [0] => short_stay_business 
       [1] => short_stay_business_tourism 
       [2] => short_stay_german_company 
       [3] => short_stay_german_company_tourism 
       [4] => short_stay_work_training 
       [5] => short_stay_work 
       [6] => short_stay_student_internship 
       [7] => exhibition 
       [8] => scientific_research_all 
      ) 

     [exhibition.item] => Array (
       [0] => short_stay_visitor_fair 
       [1] => short_stay_visitor_fair_tourism 
       [2] => short_stay_exhibitor 
       [3] => short_stay_exhibitor_tourism 
      ) 

     [scientific_research_all.item] => Array (
       [0] => short_stay_scientific_research 
       [1] => short_stay_scientific_research_spouse 
       [2] => short_stay_scientific_research_child 
      ) 

     [sporting_cultural.item] => Array (
       [0] => short_stay_sporting_or_cultural 
      ) 

     [tourism.item] => Array (
       [0] => short_stay_tourism 
       [1] => medical_treatment 
      ) 

     [medical_treatment.item] => Array (
       [0] => short_stay_medical_treatment 
       [1] => short_stay_medical_treatment_tourism_friend_family_visit 
       [2] => short_stay_accompanying_person_of_a_medical_patient 
      ) 

     [friend.item] => Array (
       [0] => short_stay_friends 
      ) 

     [family.item] => Array (
       [0] => short_stay_family 
       [1] => short_stay_german_family_in_germany 
       [2] => short_stay_german_family_in_china 
       [3] => short_stay_non_german_family 
      ) 

     [student_family.item] => Array (
       [0] => short_stay_student 
       [1] => short_stay_entrance_exam 
       [2] => short_stay_scholar_exchange 
       [3] => short_stay_student_internship 
      ) 

     [transit.item] => Array (
       [0] => transit_transit 
       [1] => airport_transit_airport_transit 
      ) 

     [other_cases.item] => Array (
       [0] => short_stay_seaman 
      ) 

     [ls.item] => Array (
       [0] => ls_notification 
      ) 

     [children] => Array() 

    ) 
) 

рекурсии функция:

function plotTree($arr, $indent=0, $mother_run=true){ 

    global $ini_array; 
    global $depth; 
    global $maxDepth; 

    if ($mother_run) { 
     // the beginning of plotTree. We're at rootlevel 
     echo "start\n"; 
    } 

    foreach ($arr as $key => $value) { 
     if (is_array($value)) { 
      foreach ($value as $subKey => $subValue) { 
       if(in_array($subValue.".item", array_keys($ini_array['relation']))) { 
        $depth +=1; 
        plotTree($ini_array['relation'][$subValue.".item"],0,false); 
       } 
      } 
      $maxDepth = $maxDepth < $depth ? $depth : $maxDepth; 
     } 
    }  

    if ($mother_run) { 
     echo "end\n"; 
    } 
} 

[Update} Я не хочу, чтобы найти число измерений. В приведенном выше примере древовидная структура выглядит следующим образом: parent => cs => business => exhibition

Answer 1

Итак, я вижу, что вы пытаетесь измерить глубину, основанную на «отношениях» в плоском массиве, а не на фактической глубине дерева.

Так вот что я смог придумать с некоторыми пояснениями ниже:

<?php 

function getMaxDepth(array $arr, array $relations = array()) { 
    if (empty($relations)) { 
     return array_reduce($arr, function ($result, $elem) use ($arr) { 
      return max($result, getMaxDepth($elem, $arr)); 
     }); 
    } 

    // Return 1 + the depth of the deepest nested tree 
    return 1 + array_reduce($arr, function ($max, $elem) use ($relations) { 
     // If the field is not related to another field return the current max 
     if (!in_array($elem . '.item', array_keys($relations))) { 
      return $max; 
     } 

     // Return maximum of current maximum and the depth of related tree 
     return max($max, getMaxDepth($relations[$elem . '.item'], $relations)); 
    }, 0); 
} 

Использование так:

getMaxDepth($yourArray['relation']); // returns 4 

Итак, прежде всего, следует избегать использования глобальной или статические переменные, особенно при работе с рекурсией. Вместо этого мы хотим сохранить все, что нужно в стеке, передав его как аргументы функции.

В первом заявлении ifgetMaxDepth() применяется к каждому поддереву отдельно, так как мы хотим убедиться, что мы покрыли все их.

Затем мы просто возвращаем глубину самого глубокого «вложенного» дерева, если есть один или 0, и добавляем один для текущего элемента.

Надеюсь, это поможет вам в будущем.