2016-11-09 12:46

# 在数组中反向递归以查找父ID

Trying to figure out a way of getting the parent ID of an item in a multi dimensional array:

``````\$Arr = array(
array(
"Id" => 1,
"Parent" => 0,
"Children" => array(
array(
"Id" => 2,
"Parent" => 1,
"Children" => array(),
),
array(
"Id" => 3,
"Parent" => 1,
"Children" => array(
array(
"Id" => 4,
"Parent" => 3,
"Children" => array(),
),
),
),
),
),
array(
"Id" => 5,
"Parent" => 0,
"Children" => array(
array(
"Id" => 6,
"Parent" => 5,
"Children" => array(),
),
),
)
);
``````

I need to get the "Id" for the top element where "Parent" = 0. I.e. for the item with Id 4 it should return 1 as result, or a search for 6 would return 5. I have tried various ways of recursive function but only manage to get the correct result when the depth is 2.

I have found this function but it seems to return the name of the key rather than the value:

``````function find_parent(\$array, \$needle, \$parent = null) {
foreach (\$array as \$key => \$value) {

if (is_array(\$value)) {
\$pass = \$parent;
if (is_string(\$key)) {
\$pass = \$key;
}
\$found = find_parent(\$value, \$needle, \$pass);
if (\$found !== false) {
return \$found;
}
} else if (\$key === 'Id' && \$value === \$needle) {
return \$parent;
}
}

return false;
}
``````

## Edit

The following only works on the 1st level/depth:

``````function GetParent(\$Data = array(), \$Needle = 0){
foreach(\$Data as \$Key => \$Item){
if(\$Item['Id'] === \$Needle && \$Item['Parent'] == 0){
return \$Item['Id'];
}
if(sizeof(\$Item['Children']) !== 0)
GetParent(\$Item['Children'], \$Item['Parent']);

}
return false;
}
``````

I don't understand what I'm doing wrong.

• 写回答
• 好问题 提建议
• 追加酬金
• 关注问题
• 收藏
• 邀请回答

#### 1条回答默认 最新

• doufang1954 2016-11-09 13:56
已采纳

While it is not usually speed efficient, but PHP has a really great feature in the Standard PHP Library (SPL) called Iterators. Anong them you can find RecursiveArrayIterator which saves you from writing the recursive functions for yourself. In you case, you have to redefine two of its methods:

``````class CustomRecursiveIterator extends RecursiveArrayIterator
{
public function hasChildren() {
return !empty(\$this->current()['Children']) && is_array(\$this->current()['Children']);
}

public function getChildren()
{
return new static(\$this->current()['Children']);
}
}
``````

Doing so, you can be sure that you will loop over children, but not all array elements.

Given this class you can write function that will suit your needs:

``````function getParentId(\$id, array \$array)
{
\$iterator = new RecursiveIteratorIterator(
new CustomRecursiveIterator(\$array),
RecursiveIteratorIterator::CHILD_FIRST
);

\$childFound = false;
foreach (\$iterator as \$item) {
if (
\$childFound
&& isset(\$item['Parent'])
&& \$item['Parent'] === 0
&& isset(\$item['Id'])
) {
return \$item['Id'];
}

if (isset(\$item['Id']) && \$item['Id'] === \$id) {
\$childFound = true;
}
}

return null;
}
``````

Pay attention to this flag `RecursiveIteratorIterator::CHILD_FIRST`.

Be aware that this implementation will not work if your array structure is invalid. For example, if there is a child with given id, but it doesn't have an ancestor with zero-parent, it will return the next element with zero-parent.

Here is working demo.

评论
解决 无用
打赏 举报