我有一堆名称-父名称对，我希望将它们变成尽可能少的层次树结构。例如，这些可能是配对:

Child : Parent
    H : G
    F : G
    G : D
    E : D
    A : E
    B : C
    C : E
    D : NULL

需要转化为(a)层次树:

D
├── E
│   ├── A
│   │   └── B
│   └── C   
└── G
    ├── F
    └── H

我想要的最终结果是 <ul> 的嵌套集元素，每个 <li>包含 child 的名字。

配对中没有不一致( child 是它自己的 parent ， parent 是 child 的 child 等)，因此可能可以进行一系列优化。

在 PHP 中，我如何从包含子 => 父对的数组转到一组嵌套 <ul> s?

我感觉涉及到递归，但我还没有清醒到想通。

最佳答案

这需要一个非常基本的递归函数将子/父对解析为树结构，并需要另一个递归函数将其打印出来。只有一个函数就足够了，但为了清楚起见，这里有两个(可以在这个答案的末尾找到一个组合函数)。

首先初始化子/父对数组:

$tree = array(
    'H' => 'G',
    'F' => 'G',
    'G' => 'D',
    'E' => 'D',
    'A' => 'E',
    'B' => 'C',
    'C' => 'E',
    'D' => null
);

然后是将该数组解析为层次树结构的函数:

function parseTree($tree, $root = null) {
    $return = array();
    # Traverse the tree and search for direct children of the root
    foreach($tree as $child => $parent) {
        # A direct child is found
        if($parent == $root) {
            # Remove item from tree (we don't need to traverse this again)
            unset($tree[$child]);
            # Append the child into result array and parse its children
            $return[] = array(
                'name' => $child,
                'children' => parseTree($tree, $child)
            );
        }
    }
    return empty($return) ? null : $return;    
}

还有一个函数遍历该树以打印出无序列表:

function printTree($tree) {
    if(!is_null($tree) && count($tree) > 0) {
        echo '<ul>';
        foreach($tree as $node) {
            echo '<li>'.$node['name'];
            printTree($node['children']);
            echo '</li>';
        }
        echo '</ul>';
    }
}

以及实际用法:

$result = parseTree($tree);
printTree($result);

这是$result的内容:

Array(
    [0] => Array(
        [name] => D
        [children] => Array(
            [0] => Array(
                [name] => G
                [children] => Array(
                    [0] => Array(
                        [name] => H
                        [children] => NULL
                    )
                    [1] => Array(
                        [name] => F
                        [children] => NULL
                    )
                )
            )
            [1] => Array(
                [name] => E
                [children] => Array(
                    [0] => Array(
                        [name] => A
                        [children] => NULL
                    )
                    [1] => Array(
                        [name] => C
                        [children] => Array(
                            [0] => Array(
                                [name] => B
                                [children] => NULL
                            )
                        )
                    )
                )
            )
        )
    )
)

如果您想要更高的效率，您可以将这些功能合二为一并减少迭代次数:

function parseAndPrintTree($root, $tree) {
    $return = array();
    if(!is_null($tree) && count($tree) > 0) {
        echo '<ul>';
        foreach($tree as $child => $parent) {
            if($parent == $root) {                    
                unset($tree[$child]);
                echo '<li>'.$child;
                parseAndPrintTree($child, $tree);
                echo '</li>';
            }
        }
        echo '</ul>';
    }
}

在这么小的数据集上，您只能保存 8 次迭代，但在更大的数据集上，它可能会有所作为。

关于php - 将一系列父子关系转化为层次树？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2915748/