logo标签列表

PHP中遍历树的最优雅方法

phptree
3
我有这样的树：
$tree = array("A", array(
            array("B", 1),
            array("C", 2),
            array("D",
                array("E",
                    array("F")),
                array("G")),
            array("H", 3)));

每个节点都是一个数组，节点类型是它的第一个元素，其他元素是节点的参数（它们可以是其他节点的列表、单个节点、某些值等；节点可以没有参数、一个参数或多个参数）。
你认为遍历这种类型的树最优雅的方式是什么？
我想到了两种可能性：
1）使用 switch 语句。
/*
 * + shorter
 * + fall-througs (easy way to handle more nodes with same code)
 *
 * - worse readability
 */
function my_tree_walker($tree)
{
    switch ($tree[0]) {
        case 'A':
            list($_, $subnodes) = $tree;
            $ret = '';

            foreach ($subnodes as $subnode) {
                $ret .= my_tree_walker($subnode);
            }

            return $ret;

        break;
        case 'B': /*...*/ break;
        case 'C': /*...*/ break;
        case 'D': /*...*/ break;
        case 'E': /*...*/ break;
        case 'F': /*...*/ break;
        case 'G': /*...*/ break;
        case 'H': /*...*/ break;
    }
}

2) 每种节点类型都有对应方法的对象

/*
 * + better readability
 * + more declarative
 *
 * - longer
 * - `new static` is PHP >=5.3 only
 */

abstract class TreeWalker
{
    protected function __construct(){}

    final protected function walk($node)
    {
        $nodetype = array_shift($node);
        return call_user_func_array(array($this, 'walk' . $nodetype), $node);
    }

    public static function w($tree)
    {
        $instance = new static;
        return $instance->walk($tree);
    }
}

final class MyTreeWalker extends TreeWalker
{
    protected function __construct()
    {
        // initialize
    }

    private function walkA($subnodes)
    {
        $ret = '';

        foreach ($subnodes as $subnode) {
            $ret .= $this->walk($subnode);
        }

        return $ret;
    }

    private function walkB($n) { /*...*/ }
    private function walkC($n) { /*...*/ }
    private function walkD($subnode) { /*...*/ }
    private function walkE() { /*...*/ }
    private function walkF() { /*...*/ }
    private function walkG() { /*...*/ }
    private function walkH($n) { /*...*/ }
}

你是否建议更加优雅的遍历树的方式？

我也考虑过将节点作为对象，而不是使用单独的树遍历器，每个节点都有用于内部遍历的方法。然而，我认为这会使代码更难维护，因为遍历器的部分代码将被放置在不同的位置，并且更难将同一代码用于多个节点。

5个回答
4
问题在于不是所有节点都会被相同地处理。仍然需要使用开关或其他东西。或者我有所遗漏吗？ - Jakub Kulhan
你能提供一个你期望用这些节点做什么的示例，以便我们更好地了解你试图完成的目标吗？ - Anthony Forloney
我正在尝试重构我的PEG生成器中的树遍历器（例如：http://github.com/jakubkulhan/phpeg/blob/master/lib/phpgen.php#L506，http://github.com/jakubkulhan/phpeg/blob/master/lib/phpgen.php#L551，http://github.com/jakubkulhan/phpeg/blob/master/lib/phpgen.php#L195以及以'g'开头的方法）。我想将它们分离出来（独立的类/函数），并使用相同的语言结构。 - Jakub Kulhan
3
1
问题在于所有节点不会被同样处理。仍然需要开关或其他东西。或者我错过了什么？ - Jakub Kulhan
@Jak 遍历本身与数据结构无关，只要它们是可迭代的。如果您想以不同的方式处理元素，则仍需要使用 switch 语句，或者您可以使用对象而不是数组，并利用动态分派。 - Artefacto
正如我在问题中所写的，我考虑了对象，但我认为它们会带来更多的麻烦而不是好处。 - Jakub Kulhan
0
我写了一个简单的递归函数，可以有效地遍历一棵树。以下是代码：
   function deep_cetegories($categories){
     foreach($categories as $category)
  {
    print_r((json_encode($category['category_name'])));
    if(isset($category['children']))
    {
        deep_cetegories($category['children']);
    }

  }
}
0

我推荐这个库：https://packagist.org/packages/lukascivil/treewalker

TreeWalker是一个简单而小巧的库，可以帮助您更快地处理PHP中的结构操作。

  • getdiff() - 获取json差异
  • walker() - 编辑json（递归）
  • structMerge() - 合并两个结构
  • createDynamicallyObjects() - 通过动态键创建嵌套结构
  • getDynamicallyValue() - 动态获取结构属性
  • setDynamicallyValue() - 动态访问结构属性以设置值
0

我将两种方法结合起来，创建了DSL：

A ($subnodes) {
    $ret = '';
    foreach ($subnodes as $subnode) {
        $ret .= WALK($subnode);
    }

    return $ret;
}
B ($n) { /*...*/ }
C ($n) { /*...*/ }
D ($subnode) { /*...*/ }
E () { /*...*/ }
F () { /*...*/ }
G () { /*...*/ }
H ($n) { /*...*/ }

这是翻译成 PHP 的。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接