将一系列父子关系转换为分层树？

php tree recursion hierarchical-data

2022-08-30 07:29:05

我有一堆名字 -父名对，我想把它们变成尽可能少的分层树结构。例如，这些可能是配对：

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>

配对中没有不一致（子是自己的父项，父项是子项的子项等），因此可以进行一系列优化。

在 PHP 中，我如何从包含 child=> 父对的数组变成一组嵌套的 s？<ul>

我有一种感觉，递归是其中的，但我还不够清醒，无法仔细思考。

答案 1

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

首先初始化子/父对的数组：

$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 次迭代，但在较大的数据集上，它可能会有所作为。

答案 2

另一个函数来制作树（不涉及递归，而是使用引用）：

$array = array('H' => 'G', 'F' => 'G', ..., 'D' => null);

function to_tree($array)
{
    $flat = array();
    $tree = array();

    foreach ($array as $child => $parent) {
        if (!isset($flat[$child])) {
            $flat[$child] = array();
        }
        if (!empty($parent)) {
            $flat[$parent][$child] =& $flat[$child];
        } else {
            $tree[$child] =& $flat[$child];
        }
    }

    return $tree;
}

返回一个分层数组，如下所示：

Array(
    [D] => Array(
        [G] => Array(
            [H] => Array()
            [F] => Array()
        )
        ...
    )
)

它可以使用递归函数轻松打印为HTML列表。