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

Question

我有一堆名称-父母名对，我想将其变成尽可能少的分层树结构。因此，例如，这些可能是配对：

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

需要将其转换为一个或多个分层树：

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

我想要的最终结果是一组嵌套<ul>元素，每个元素都<li>包含孩子的名字。

配对中没有不一致的地方（子代是它自己的父代，父代是子代的子代，等等），因此可以进行大量优化。

在PHP中，如何从包含child => parent对的数组转到一组Nested <ul>？

我感觉涉及到递归，但是我还没有足够清醒地思考它。

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