1

给定以下多维数组：

$family = array(
    "grandfather",
    "grandmother",    
    "father" => array(
        "parents" => array(
            "grandfather",
            "grandmother"
         )
    ),
    "mother" => array(
        "parents" => array(
            "grandfather",
            "grandmother"
         )
    ),
    "son" => array(
        "parents" => array(
            "father",
            "mother"
         )
    ),
    "daughter" => array(
        "parents" => array(
            "father",
            "mother"
         )
    ),
);

您可以想象扩展此数组以包括曾祖父母、曾孙子女等。

我确信这是一种常见且有据可查的数据结构，但我不是计算机科学专业的，我不知道如何描述或命名这种特殊类型的字典。

给定我们正在寻找的“子”节点和“祖先”节点的名称，是否有内置于 PHP 中的函数可以可靠地向上导航此树？

例如：

getAncestor($array, $child, $ancestor);

我已经尝试过了，它通常涉及嵌套在自身内部的 getAncestor() 函数的递归，但有时会遇到“死胡同”，它会一直导航到一个分支的末尾。

4

2 回答 2

0

您可以尝试一种更线性的方法，而不是将所有内容相互嵌套，您只需拥有一堆指向每个对象中所有祖先的指针。否则这对我来说听起来像是一个递归问题。

指针方法：

<?php

$person1 = new PersonObject( 'details' );
$person2 = new PersonObject( 'details' );

$person1->father =& $person2;

?>

如果您的数据集像您的示例一样给出，您可能会或可能不会从转换到这种系统中受益，这取决于您需要查找多少祖先。另外，在我看来，这种结构更干净=）。

于 2013-02-01T02:07:37.230 回答
0

对不起，但我无法想象你会如何在没有看到它的情况下添加曾祖父母。你说需要递归，但$family有 3 代成员，只有 2 级嵌套。如果您要像这样添加曾祖父母（我的最佳猜测是基于您的样本$family数组），那么仍然只有 2 级嵌套。

$family = array(
    "great-grandfather",
    "great-grandmother",    
    "grandmother" => array(
        "parents" => array(
            "great-grandmother",
            "great-grandfather"
         )
    ),
    // ...
);

然后甚至不需要递归。

虽然根据您的描述不清楚它应该做什么。当找到匹配项时，它会回显子项和祖先项并返回一个布尔结果。

function getAncestor($array, $child, $ancestor)
{
    foreach($array as $_child => $_ancestor) {
        // Bail if child is not a match or ancestor is not array
        if($child != $_child ||
           !is_array($_ancestor) || !count($_ancestor))
            continue;

        // see if cur ancestor is a match for searched ancestor
        if(in_array($ancestor, $_ancestor['parents'])) {
            echo 'Child: ' . $child . PHP_EOL;
            echo 'Ancestors: ' . implode(', ', $_ancestor['parents']) . PHP_EOL;
            return true;
        }
    }

    return false;
}

getAncestor($family, 'son', 'father');
getAncestor($family, 'father', 'grandmother');
getAncestor($family, 'father', 'mother');

输出

孩子：儿子

祖先：父亲、母亲

孩子：父亲

祖先：祖父、祖母

例子的另一个旁注$family，看起来爸爸和妈妈有同一个父母！

于 2013-02-03T05:01:10.060 回答