将一系列父子关系转换为层次树? [英] Convert a series of parent-child relationships into a hierarchical tree?

问题描述

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

I have a bunch of name-parentname pairs, that I'd like to turn into as few heirarchical tree structures as possible. So for example, these could be the pairings:

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

需要转换为(一个或多个)分层树:

Which needs to be transformed into (a) heirarchical tree(s):

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

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

The end result that I want is a nested set of <ul> elements, with each <li> containing the child's name.

配对中没有不一致的地方(孩子是它的父母，孩子是孩子的父母，等等)，因此可以进行很多优化.

There are no inconsistencies in the pairings (child is it's own parent, parent is child's child, etc), so a bunch of optimizations can probably be made.

在PHP中，如何从包含child => parent对的数组过渡到一组嵌套的<ul> s?

How, in PHP, would I go from an array containing child=>parent pairs, to a set of Nested <ul>s?

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

I have a feeling that recursion is involved, but I'm not quite awake enough to think it through.

推荐答案

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

This requires a very basic recursive function to parse the child/parent pairs to a tree structure and another recursive function to print it out. Only one function would suffice but here's two for clarity (a combined function can be found at the end of this answer).

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

First initialize the array of child/parent pairs:

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

然后将数组解析为分层树结构的函数:

Then the function that parses that array into a hierarchical tree structure:

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;    
}

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

And a function that traverses that tree to print out an unordered list:

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
                            )
                        )
                    )
                )
            )
        )
    )
)

---

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

---

If you want a bit more efficiency, you can combine those functions into one and reduce the number of iterations made:

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

You'll only save 8 iterations on a dataset as small as this but on bigger sets it could make a difference.

这篇关于将一系列父子关系转换为层次树?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！