在多维数组中递归搜索键/值对并返回路径
我正在研究导航结构.我正在使用父模型，因此我将所有子导航节点放入一个数组并将它们附加到父导航.
i am working on a navigation structure. i am using the parent-model, so i put all the child-navigation-nodes into a array and append them to the parent navigation.
数组结构如下:
$navigation = array(
0 =>
array(
'id' => '2',
'parent_id' => '0',
'name' => 'abouts us',
'subNavigation' =>
array(
0 => array(
'id' => '3',
'parent_id' => '2',
'name' => 'Foo',
'subNavigation' =>
array(
0 => array(
'id' => '4',
'parent_id' => '3',
'name' => 'test',
'subNavigation' =>
array(),
),
1 => array(
'id' => '5',
'parent_id' => '3',
'name' => 'bar',
'subNavigation' =>
array(),
),
),
),
),
),
1 =>
array(
'id' => '6',
'parent_id' => '0',
'name' => 'Foobar',
'subNavigation' =>
array(
0 => array(
'id' => '7',
'parent_id' => '6',
'name' => 'ASDF',
'subNavigation' =>
array(),
),
),
),
);
现在我想搜索一个导航 ID，例如 ID = 5 (Navigation-Name = bar)，结果应该是这个子导航的数组.
now i want to search for a navigation-ID for example ID = 5 (Navigation-Name = bar) and the result should be a array to this child navigation.
结果:
$result = array(
0 =>
array(
'id' => '2',
'parent_id' => '0',
'name' => 'abouts us',
'subNavigation' =>
array(
0 => array(
'id' => '3',
'parent_id' => '2',
'name' => 'Foo',
'subNavigation' =>
array(
0 => array(
'id' => '5',
'parent_id' => '3',
'name' => 'bar',
'subNavigation' =>
array(),
),
),
),
),
),
);
最快的方法是什么，哪个递归函数可以完成这项工作?
what is the fastest way and which recursive function will do this job?
我编辑了导航节点 5 的 parent_id ......哪里是错误的 parent_id
i edit the parent_id of the navigation-node 5 ... where was a wrong parent_id
非常有趣的问题.这是一个解决方案:
Very interesting question. Here's a solution:
function search($navitation_tree, $id, $temp_branch = array()) {
for ($i = 0; $i < sizeof($navitation_tree); $i++) {
$nav_element = $navitation_tree[$i];
if($nav_element['parent_id'] === '0') {
$temp_branch = array();
} else if($i > 0) {
for ($y = 0; $y < 1; $y++) {
array_pop($temp_branch);
}
}
$cloned_nav_element = array('id' => $nav_element['id'],
'parent_id' => $nav_element['parent_id'],
'name' => $nav_element['name'],
'subNavigation' => array());
$temp_branch[] = $cloned_nav_element;
if($nav_element['id'] === $id) {
return $temp_branch;
}
if(sizeof($nav_element['subNavigation'] > 0)) {
$result = search($nav_element['subNavigation'], $id, $temp_branch);
}
if($result != null) {
return $result;
}
}
}
function getNavigationBranch($navitation_tree, $id) {
$branch = search($navitation_tree, $id);
if($branch !== null) {
$final_nav_element = array();
foreach($branch as $temp_nav_element) {
if(empty($final_nav_element)) {
$final_nav_element = array(array_pop($branch));
} else {
$temp_nav_element = array_pop($branch);
$temp_nav_element['subNavigation'] = $final_nav_element;
$final_nav_element = array($temp_nav_element);
}
}
return $final_nav_element;
}
}
$result = getNavigationBranch($navigation, '5');
search 函数执行深度优先搜索(DFS) 进入导航树.一旦它找到所需的 id，它就会将路径(由导航元素的有序数组表示)返回到 getNavigationBranch，后者将数据重新构造为您在问题中请求的格式，并且返回它们(如果找不到 id，它将返回 null.
The search function performs a depth-first search (DFS) into the navigation tree. As soon as it locates the desired id, it returns the path (represented by an ordered array of navigation elements) to the getNavigationBranch, which re-constructs the data to the format you requested in your question, and returns them (it will return null if the id is not found.
顺便说一句，虽然 DFS 在大图中搜索时可能会出现问题，但我认为它适用于(如果不是全部)导航树的大多数情况.
By the way, although DFS can have issues when searching in large graphs, but I think it will work fine for (if not all then) most of the cases of a navigation tree.
为了测试它，我使用了以下数据:
To test it, I used the following data:
$navigation = array(
0 =>
array(
'id' => '2',
'parent_id' => '0',
'name' => 'abouts us',
'subNavigation' =>
array(
0 => array(
'id' => '3',
'parent_id' => '2',
'name' => 'Foo',
'subNavigation' =>
array(
0 => array(
'id' => '4',
'parent_id' => '3',
'name' => 'test',
'subNavigation' =>
array(),
),
1 => array(
'id' => '5',
'parent_id' => '3',
'name' => 'bar',
'subNavigation' =>
array(),
),
),
),
1 => array(
'id' => '8',
'parent_id' => '2',
'name' => 'Foo',
'subNavigation' =>
array(
0 => array(
'id' => '9',
'parent_id' => '8',
'name' => 'test',
'subNavigation' =>
array(),
),
1 => array(
'id' => '10',
'parent_id' => '8',
'name' => 'bar',
'subNavigation' =>
array(),
),
),
),
2 => array(
'id' => '11',
'parent_id' => '2',
'name' => 'Foo',
'subNavigation' =>
array(
0 => array(
'id' => '12',
'parent_id' => '8',
'name' => 'test',
'subNavigation' =>
array(),
),
1 => array(
'id' => '13',
'parent_id' => '8',
'name' => 'bar',
'subNavigation' =>
array(),
),
),
),
),
),
1 =>
array(
'id' => '6',
'parent_id' => '0',
'name' => 'Foobar',
'subNavigation' =>
array(
0 => array(
'id' => '7',
'parent_id' => '6',
'name' => 'ASDF',
'subNavigation' =>
array(),
),
),
),
);
以下是几个测试结果:
$result = getNavigationBranch($navigation, '5');
var_dump($result);
以上产生:
array(1) {
[0]=>
array(4) {
["id"]=>
string(1) "2"
["parent_id"]=>
string(1) "0"
["name"]=>
string(9) "abouts us"
["subNavigation"]=>
array(1) {
[0]=>
array(4) {
["id"]=>
string(1) "3"
["parent_id"]=>
string(1) "2"
["name"]=>
string(3) "Foo"
["subNavigation"]=>
array(1) {
[0]=>
array(4) {
["id"]=>
string(1) "5"
["parent_id"]=>
string(1) "3"
["name"]=>
string(3) "bar"
["subNavigation"]=>
array(0) {
}
}
}
}
}
}
}
还有一个:
$result = getNavigationBranch($navigation, '13');
var_dump($result);
以上产生:
array(1) {
[0]=>
array(4) {
["id"]=>
string(1) "2"
["parent_id"]=>
string(1) "0"
["name"]=>
string(9) "abouts us"
["subNavigation"]=>
array(1) {
[0]=>
array(4) {
["id"]=>
string(2) "11"
["parent_id"]=>
string(1) "2"
["name"]=>
string(3) "Foo"
["subNavigation"]=>
array(1) {
[0]=>
array(4) {
["id"]=>
string(2) "13"
["parent_id"]=>
string(1) "8"
["name"]=>
string(3) "bar"
["subNavigation"]=>
array(0) {
}
}
}
}
}
}
}