递归树遍历 - 如何跟踪递归层级？

Question

我基本上想从表示树形结构的多维数组中构建一个html ul/li嵌套列表。

以下代码可以正常工作，但我想要改进它：

我需要一种方法来跟踪递归级别，以便可以对不同级别应用不同的类，添加缩进到生成的输出等。

function buildTree($tree_array, $display_field, $children_field, $class='', $id='') {

  echo "<ul>\n";

  foreach ($tree_array as $row) {

    echo "<li>\n";
    echo $row[$display_field] . "\n";

    if (isset($row[$children_field])) {

      $this->buildTree($row[$children_field]);
    }
    echo "</li>\n";
  }
  echo "</ul>\n";
} 

$tree_array看起来像这样：

Array
(
    [0] => Array
        (
            [category_id] => 1
            [category_name] => calculatoare
            [parent_id] => 0
            [children] => Array
                (
                    [0] => Array
                        (
                            [category_id] => 4
                            [category_name] => placi de baza
                            [parent_id] => 1
                        )

                    [1] => Array
                        (
                            [category_id] => 5
                            [category_name] => carcase
                            [parent_id] => 1
                            [children] => Array
                                (
                                    [0] => Array
                                        (
                                            [category_id] => 6
                                            [category_name] => midi-tower
                                            [parent_id] => 5
                                        )

                                )

                        )

                )

        )

    [1] => Array
        (
            [category_id] => 2
            [category_name] => electronice
            [parent_id] => 0
        )

    [2] => Array
        (
            [category_id] => 3
            [category_name] => carti
            [parent_id] => 0
        )

)

我将此标记为作业，因为我想利用这个机会来提高我对递归的（薄弱）理解，所以我希望得到指导解决方法的答案，而不是完整的工作示例 :)

- Bogdan

Answer 1

快速且简单的方法（请参见下面的“剧透”块以获得实现方式）：

在函数声明中添加一个额外的变量$recursionDepth，默认为0。

在每次递归时，使用$recursionDepth + 1调用您的函数。

由于函数变量仅对函数实例“可见”（作用域），因此您将获得当前迭代深度的指示器。

此外，将函数的第12行

$this->buildTree();

在我看来，这似乎行不通——因为您没有将变量传递给下一个buildTree实例。

它可能应该像这样：

$this->buildTree($row[$children_field], $display_field, $children_field, $class, $id)

以下是我对您的代码所做的更改，以实现您想要的效果：

function buildTree($tree_array, $display_field, $children_field, $class='', $id='', $recursionDepth = 0, $maxDepth = false)
{
    if ($maxDepth && ($recursionDepth == $maxDepth)) return;

    echo "<ul>\n";

    foreach ($tree_array as $row)
    {
        echo "<li>\n";
        echo $row[$display_field] . "\n";

        if (isset($row[$children_field]))
            $this->buildTree($row[$children_field], $display_field, $children_field, $class, $id, $recursionDepth + 1, $maxDepth);

        echo "</li>\n";
    }
    echo "</ul>\n";
}

- vzwick

---

这不仅仅是一种好习惯，每当您使用递归时，都应该提供一种机制来限制递归深度，以避免...堆栈溢出。 - symcbean

很棒的答案！正是我想要的。 - Bogdan

Answer 2

你正在让生活变得比必要的更加困难。SPL 提供了多个 迭代器 以方便您使用。使用 RecursiveArrayIterator 类 遍历多维数组非常容易。它不仅可以处理任何层级深度的数组，还会跟踪深度。

$iterator = new RecursiveIteratorIterator(
    new RecursiveArrayIterator($array)
);

for($iterator; $iterator->valid(); $iterator->next())
{
    printf(
        "Key: %s Value: %s Depth: %s\n",
        $iterator->key(),
        $iterator->current(),
        $iterator->getDepth()
    );
}

在 codepad 上的示例

正如您所看到的，有一个方法 getDepth()，它将始终告诉您当前迭代深度。这是RecursiveIteratorIterator的方法，用于递归迭代器中遍历子级。

如果您需要影响迭代开始或访问子项时发生的情况，请查看我的答案多维数组迭代，其中显示了一个自定义的RecursiveIteratorIterator，它将多维数组的值包装成 XML 元素，并按当前迭代的深度进行缩进（应该很容易适应 ul/li 元素）。

还可以查看迭代器的维基百科文章以获取一般介绍。

- Gordon

---

今天我学到了新东西 :) 我之前不知道RecursiveArrayIterator类。谢谢！ - Bogdan

Answer 3

public virtual int GetLevelById(int id)
        {
            int i = GetParentById(id);
            if (i == 0)
                return 1;
            else
                return (1 + GetLevelById(i));
        }

公共虚拟整数 GetParentById(int t) { var ret = this._list.FirstOrDefault((f) => f.Id == t); if (ret != null) return ret.ParentId; return -1; }

- Mohamed.Abdo

---

使用getParentById，如下所示： public virtual int GetParentById(int t) { var ret = this._list.FirstOrDefault((f) => f.Id == t); if (ret != null) return ret.ParentId; return -1; } - Mohamed.Abdo