横断Bツリー構造アルゴリズム

Question

子ノードの親ノードを出力する横断関数を作成しようとしています。

$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配列をしようとしている：

例Bツリーここ

を見ては、私が使用しているサンプルデータセットです親の関連付けを含むすべての子ノード配列。

例出力：

• ノード（D）の両親である（D、B、F）
• ノード（H両親が（B、F）
• ノード（c）は ' ）の親は（i、g、f）

私は直接の親ノードを通過する方法を理解できません。

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

唯一の欠点は、それが、戻りリストで元のノードを返すだろうということです。しかし、私はあなたがそれで生きることができると思います。

私は、ツリーのより良い表現が可能だと思う：

$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に直接行っていることが可能であるべきである）が、私は今、それを検討する時間がありません。