트래 버블 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에서 직접 수행()하지만 지금은 그것으로 볼 시간이없는 가질 수 있어야한다.