PHP-php多维数组如何根据值获取所有上一级的key值链

Question

有多维数组，数组的维度不定。如下：

$a = array(
    'k1' => array(
    'kk1' => 'v1',
    ),
    'k2' => array(
    'kk2' => 'v2',
    ),
    'k3' => array(
    'kk3' => array(
    'kkk3' => 'v3',
    ),
    ),
    'k4' => array(
    'kk2' => 'v2',
    ),
);

Answer 1

本质上来讲，这个问题是一个多叉树的查找问题。
树的每个节点包含两个属性，key 和 value, 非叶节点的value值为null。例如：{key：'kk1', value:'v1'} 就是叶节点，对应 'kk1'=>'v1', 它的父节点就是 {key:'k1', value:null}，是非叶节点。
这个问题的常规解法就是遍历，有深度优先遍历，广度优先遍历等。
维度不定对应的就是树的高度不定，用递归就可以很好的解决。常规遍历算法也都是要用到递归的，所以不用纠结究竟要用几个foreach的问题。
为了提高速度，我们可以考虑一些非常规的解法。
1. 递归意味着有多层函数调用，需要把多次执行的上下文压栈，是比较慢的。我们可以考虑把递归转化成迭代来实现。这个也有定式的。具体到这个问题，可以利用一个队列Q，把所有初次访问到的节点放入队列，从队列取节点，访问取出节点的所有子节点，并把它们放入队列。如是循环，直至队列为空。
2. 不管怎么样，遍历整棵树，就意味着要把所有的节点访问一遍。速度不可能再提高了。为了查询速度更快，我们必须要转换数据结构，显然如果把树转换成hash，我们就能得到理论上的最快速度。具体到这个题目，我们来申请一个数组$b，通过遍历$a，我们得到这样的数组:
$b = array(
'v1'=>array('kk1','k1'),
'v2'=>array(array('kk2','k2'),array('kk2','k4')),
'v3'=>array('kkk3','kk3','k3')
)
以后在数组$b上来查找，速度应该就再也不是问题了。

Answer 2

参考

function GetPath(&$node, $value, &$return)
{
if(!is_array($node))
return $node === $value;
else
{
foreach($node as $k=>&$v)
{
if(GetPath($v, $value, $return))
{
$return[] = $k;
return true;
}
unset($v); //据说有助于防止内存泄露，虽然我一般不加……
}
}
return false;
}

$retv = array();
$r = GetPath($root, 'v2', $retv);

上面的是返回第一个。如果需要返回全部：

function GetPath(&$node, $value, &$return)
{
if(!is_array($node))
{
if($node === $value)
{
$return[] = array();
return true;
}
else
{
return false;
}
}
else
{
$hasv = false
foreach($node as $k=>&$v)
{
$r = array();
if(GetPath($v, $value, $r))
{
foreach($r as &$rv)
{
$rv[] = $k;
unset($rv);
}
$return = array_merge($return, $r);
$hasv = true;
}
unset($v); //据说有助于防止内存泄露，虽然我一般不加……
}
return $hasv;
}
}

$retv = array();
$r = GetPath($root, 'v2', $retv);

如果嫌效率不够可以修改数据结构：
为每个array增加'__parent'用来记录父节点，'__path'用来记录当前路径，并且规定这些键名保留不允许使用。可以用一次遍历为数组加上这些信息：

function InsertMultiDic(&$publicDic, $key, $v)
{
if(isset($publicDic[$key]))
{
$publicDic[$key][] = $v;
}
else
{
$publicDic[$key] = array($v);
}
}

function AddInfo(&$node, &$parent, $key, &$publicDic)
{
if(!is_array($node))
{
InsertMultiDic($publicDic, $node, array_merge(array($key),$parent['__path']));
return;
}
if($parent != null)
{
$node['__parent'] = &$parent;
}
if($parent != null)
{
$path = array_merge(array($key), $parent['__path']);
}
else
{
$path = array();
}
foreach($node as $k=>&$v)
{
if($k != '__parent' && $k != '__path')
{
AddInfo($v, $node, $k, $publicDic);
unset($v);
}
}
}

$publicDic = array();
AddInfo($root, null, null, $publicDic);

这段代码同时还为所有的值建立了索引。
以后修改数组的时候：

$someNode['newkey'] = 'newvalue';
InsertMultiDic($publicDic, 'newvalue', array_merge(array('newkey'),$someNode['__path']));
//要注意，如果原来已经有'newkey'了，这里会有问题。这段代码还缺少删除的功能。

Answer 3

N叉 交叉树 寻分支 返回路径问题？

多叉树蚁群算法

你一句维度不定 这个问题就太复杂了

Answer 4

我封装了两个函数来实现的：

 <?php
$a = array(
'k1' => array(
'kk1' => 'v1',
),
'k2' => array(
'kk2' => 'v2',
),
'k3' => array(
'kk3' => array(
'kkk3' => 'v3',
),
),
'k4' => array(
'kk2' => 'v2',
),
);
function makeRecursive(array &$out, $key, array $in){
foreach($in as $k=>$v){
if(is_array($v)){
makeRecursive($out, $key . $k . '_', $v);
}else{
$out[$key . $k] = $v;
}
}
}

function getKeys(array $in,$value){
$out = $k_array = array();
makeRecursive($out, '', $in);
$k = array_keys($out,$value);
if(!empty($k[0])){
$k_array = array_reverse(explode('_',$k[0]));
}
return $k_array;
}

$keys = getKeys($a,'v3');
print_r($keys);

?>

结果：
Array
(
[0] => kkk3
[1] => kk3
[2] => k3
)