遍历 B-Tree 结构算法

Question

我很难尝试编写输出 child-node 的 parent-nodes 的遍历函数。

看例子b-tree

这是我使用的示例数据集：

$nodes = array(
  array('f','b'),
  array('f','g'),
  array('b','a'),
  array('b','d'),
  array('g','i'),
  array('d','c'),
  array('d','e'),
  array('i','h')
);

我正在尝试输出一个 results 数组，其中包含所有 child 个节点数组，这些节点数组包含 parent 个关联。

示例输出：

节点(d)的parent是(b,f)
节点(c)的parent是(d,b,f)
节点(h)的parent是(i,g,f)

我不知道如何遍历直接 parent 节点。

foreach($nodes as $node){
    //CHECK IF NODE EXISTS
    if(array_key_exists($node[1],$results)){
        //DO NOTHING
        array_push($results[$node[1]],$node[0]);
    }
    else{
        //CREATE NEW CHILD ARRAY
        $results[$node[1]] = [];
        //PUSH PARENT INTO CHILD ARRAY
        array_push($results[$node[1]],$node[0]);
    }
}
foreach($results as $k => $v){
    echo "child[$k] parents(" . implode($v,', ').")" ; 
    echo "</br>";
}

问题：如何在最高效的庄园里实现这个输出？

Answer 1

处理这种情况的最好方法是使用递归函数。

echo findParents('h',$nodes);

function findParents($find,$btree){
      $parents;
        foreach($btree as $node){
            if($node[1]===$find){
                $parents .=$find.',';
                return $parents .= findParents($node[0], $btree);
            }
        }
     return $find;
    }

在此处查看实时代码：https://www.tehplayground.com/ElTdtP61DwFT1qIc

唯一的缺点是它会return return 列表中的原始节点。但我认为你可以接受。

我认为树的更好表示是：

$nodes = array(
  'f'=>array('d','g'),
  'b'=>array('a','d'),
  'g'=>array('i'),
  'd'=>array('c','e'),
  'i'=>array('h')
);

但这需要对上面的代码稍作修改。

获取数组作为响应：

function findParentsArray($find,$btree){
  $parentsArray = explode(',',findParents($find,$btree));
  array_shift($parentsArray);
  return $parentsArray;
}

应该可以直接在 findParents() 中完成，但我现在没有时间研究它。

遍历 B-Tree 结构算法

Traversing B-Tree Structure Algorithm

php

algorithm

b-tree

b-tree-index