平面数组到树结构的问题

Question

我有以下数组：

Array
(
    [1] => 0
    [2] => 1
    [3] => 2
    [4] => 3
    [5] => 1
    [6] => 0
)

此数组的键是唯一的，并且值显示键的父级。就像1和6的双亲是0，2的双亲是1，因为3是2.

我正在编写一个递归函数，它将查找给定子id的父代。(4->3->2->1->0)下面是我的代码:但不返回任何结果

$child_node = 4;

function find_parents($child_node){
    global $tree, $mark;

    $mark[$child_node] = TRUE;

    $ans = array(); //blank array for result

    foreach($tree[$child_node]->children as $child)

        if(!$mark[$child]){
            $ans[$child]=$child;
            find_parents($ans[$child],$child);
        }
     }

下面是我如何创建树的方法

class node {

    var $children;
    var $parents;

    public function __construct(){
        $this->children = array();
        $this->parents = array();
    }

}

$tree = array();

foreach ($a as $q => $p){

    if(!isset($tree[$p]))
        $tree[$p] = new node;
    if(!isset($tree[$q]))
        $tree[$q] = new node;

    $mark[$p]=FALSE;
    $mark[$q]=FALSE;
    array_push($tree[$p]->children,$q);

}

Answer 1

为此，您实际上不需要递归函数。一个简单的循环应该足够了：

如下所示：

function find_parents($child, $tree) {
    $parents = array();
    while (isset($tree[$child])) {
        $child = $tree[$child]; // move to the immediate parent
        $parents[] = $child;    // and add that parent to the list
    }
    return $parents;
}

然后，您可以这样调用它：

$tree = array(1 => 0, 2 => 1, 3 => 2, 4 => 3, 5 => 1, 6 => 0);
find_parents(4, $tree);   // returns array(3, 2, 1, 0)
find_parents(5, $tree);   // returns array(1, 0)

如果您想在返回列表中包含该子对象，只需将其添加到函数开头的行即可，如下所示：

$parents = array($child);