使用php计算关联数组中元素的深度

Question

我一直在尝试编写一个递归函数来给出给定元素的深度，但没有成功。我似乎无法理解递归。这就是我所拥有的，但它无法正常工作：

function getDepth($a, $e, $depth = 0) {
  foreach ($a as $key => $val) {
    if (is_array($val)) {
      if ($key == $e) {
        return $depth;
      }
      return getDepth($val, $e, $depth + 1);
    }
    else {
      if ($val == $e) {
        return $depth;
      }
      else {
        return 1;
      }
    }
  }
}

任何人都可以帮助指出我在这里做错了什么吗？预先感谢您的帮助。

编辑：

@Brad @Amber @Viktor 谢谢，但这似乎也不起作用。这就是我想要的......我有一个看起来像这样的数组：

[antonio] => Array
(
    [ian] => Array
        (
            [molly] => Array
                (
                    [blake] => blake
                )

        )

    [shonda] => Array
        (
            [dana] => dana
            [james] => james
        )

    [nels] => Array
        (
            [jason] => jason
            [danny] => danny
        )

    [molly] => Array
        (
            [blake] => blake
        )

    [blake] => blake
    [travis] => travis
)

它是一棵树，我希望找到给定名称的深度级别。所以，我需要传递一个名字，比如布莱克。然后，每当我发现布莱克可能（在本例中确实如此）在不同级别的树中时，我都会想要遍历整个树，跟踪布莱克的深度。假设最顶层深度级别为0，则blake在antonio下的级别 =>伊恩=>莫莉=>布莱克是3，但他在安东尼奥手下的水平=> blake 是 1，所以我想返回 1。我必须遍历整个树（幸运的是这个函数不会经常被调用）以确保我找到了给定用户的树中最浅的深度。再次感谢您的帮助。

Answer 1

基本上，为了获得正确的递归，如果您知道函数中有一个数组，请在其上运行相同的函数。我们添加迄今为止最深的路径+1。最终，您会得到您想要的东西。

function getDepth($a) {
    $max=0;
    foreach ($a as $val) {
        if (is_array($val)) {
            $tmp_depth=getDepth($val);
            if ($max<($tmp_depth)) {
                $max=$tmp_depth;
            }
        }
    }
    return $max+1;
}

我还没有对这个或任何东西进行基准测试。毫无疑问，如果速度很重要的话，速度是可以提高的。

Answer 2

function getDepth($a, $e, $depth = 0) {
  $lower  = false;   //  meaning 'not found'
  // as you are looking for the less deep value, first check for values and then for arrays
  // so there are chances when you do not traverse all the tree for a match
  foreach ($a as $key => $val) if ($val == $e) return $depth;
  foreach ($a as $key => $val) {
    if (is_array($val)) {
      $tmp = getDepth($val, $e, $depth + 1);
      if($tmp) if ($lower === false || $tmp < $lower) $lower = $tmp;
    }
  }
  return $lower;
}

$x=array( 
  antonio => Array(
    ian => Array(
       molly => Array(
          blake => blake,
          jhonyDeep => jhonyDeep
       )
    ),
    shonda => Array(
       dana => dana,
       james => james
    ),
    nels => Array (
       jason => jason,
       danny => danny
    ),
    molly => Array(
       blake => blake
    ),
    blake => blake,
    travis => travis
  )
);


echo getDepth($x, blake);      // gives 1
echo getDepth($x, danny);      // gives 2
echo getDepth($x, jhonyDeep);  // gives 3

Answer 3

与我之前的答案类似，但针对性能进行了优化（并且要小心，未经测试）

function getDepth($a, $e, $depth = 0, $lower = false) {
  // $lower = false means 'not found'
  // as you are looking for the less deep value, first check for values and then for arrays
  // so there are chances when you do not traverse all the tree for a match
  foreach ($a as $key => $val) if ($val == $e) return $depth;
  foreach ($a as $key => $val) {
    if (is_array($val)) {
      $tmp = false;
      if($lower===false || $lower > $depth) $tmp = getDepth($val, $e, $depth + 1, $lower);  // to do not recurse innecesary
      if($tmp) {
        if($tmp==$depth+1) return $tmp;  //optimization: $depth+1 can't be beat by other values
        if ($lower === false || $tmp < $lower) $lower = $tmp;
      }
    }
  }
  return $lower;
}

$x=array( 
  antonio => Array(
    ian => Array(
       molly => Array(
          blake => blake,
          jhonyDeep => jhonyDeep
       )
    ),
    shonda => Array(
       dana => dana,
       james => james
    ),
    nels => Array (
       jason => jason,
       danny => danny
    ),
    molly => Array(
       blake => blake
    ),
    blake => blake,
    travis => travis
  )
);


echo getDepth($x, blake);      // gives 1
echo getDepth($x, danny);      // gives 2
echo getDepth($x, jhonyDeep);  // gives 3