PHP에서이 MPTT 배열을 트리 구조로 변환하는 방법?

Question

데이터베이스에 계층 적 데이터가 있으며 Modified Preorder Tree Traversal 형식으로 저장되어 있습니다. "SELECT ID, Left, Right, 이름 등에서 테이블 주문 ORDER BY Left;"와 같은 쿼리에서 데이터를 가져옵니다. " 이 데이터를 PHP에서 json_encode 함수를 사용하여 JSON으로 출력 할 트리 구조로 데이터베이스가 제공하는 플랫 배열에서이 데이터로 변환하려고합니다.

하지만 트리 구조 코드가 첫 번째 수준 이상으로 작동하는 데 문제가 있습니다.

<pre><?php 

function projectListToTree($projects) { 
    $stack = Array(); 
    for($x =0; $x < count($projects); $x++) { 
     $project = $projects[$x]; 
     $project['Children'] = Array(); 

     while(count($stack) > 0 && $stack[count($stack) - 1]['Right'] < $project['Right']) { 
      array_pop($stack); 
     } 

     if(count($stack) > 0) { 
      $stack[count($stack) - 1]['Children'][] = $project; 
      echo "Adding " . $project['Name'] . " to " . $stack[count($stack) - 1]['Name'] . " for a total of " 
       . count($stack[count($stack) - 1]['Children']) . " kids\n"; 
     } else { 
      echo "No parent\n"; 
     } 

     echo "stack count: " . count($stack) . "\n"; 

     array_push($stack, $project); 
    } 

    echo "Left in stack: " . count($stack) . "\n"; 

    return $stack[0]; 
} 

/* 
This is basically what comes from the DB. 
Should be: 
    Parent 
    First Child 
    Second Child 
     Grand Child 
*/ 
$projects = Array(
    Array(
     "ID" => "2", 
     "Left" => "2", 
     "Right" => "9", 
     "ParentID" => "1", 
     "Name" => "Parent" 
    ), 
    Array(
     "ID" => "3", 
     "Left" => "3", 
     "Right" => "4", 
     "ParentID" => "2", 
     "Name" => "First Child" 
    ), 
    Array(
     "ID" => "4", 
     "Left" => "5", 
     "Right" => "8", 
     "ParentID" => "2", 
     "Name" => "Second Child" 
    ), 
    Array(
     "ID" => "5", 
     "Left" => "6", 
     "Right" => "7", 
     "ParentID" => "4", 
     "Name" => "Grand Child" 
    ) 
); 


$tree = projectListToTree($projects); 
echo "-----\n\n\n\n"; 
var_dump($tree); 

?></pre> 

그리고 여기가 출력지고있어 무엇 : 여기에 최소한의 테스트 케이스이다

No parent 
stack count: 0 
Adding First Child to Parent for a total of 1 kids 
stack count: 1 
Adding Second Child to Parent for a total of 2 kids 
stack count: 1 
Adding Grand Child to Second Child for a total of 1 kids 
stack count: 2 
Left in stack: 3 
----- 



array(6) { 
    ["ID"]=> 
    string(1) "2" 
    ["Left"]=> 
    string(1) "2" 
    ["Right"]=> 
    string(1) "9" 
    ["ParentID"]=> 
    string(1) "1" 
    ["Name"]=> 
    string(6) "Parent" 
    ["Children"]=> 
    array(2) { 
    [0]=> 
    array(6) { 
     ["ID"]=> 
     string(1) "3" 
     ["Left"]=> 
     string(1) "3" 
     ["Right"]=> 
     string(1) "4" 
     ["ParentID"]=> 
     string(1) "2" 
     ["Name"]=> 
     string(11) "First Child" 
     ["Children"]=> 
     array(0) { 
     } 
    } 
    [1]=> 
    array(6) { 
     ["ID"]=> 
     string(1) "4" 
     ["Left"]=> 
     string(1) "5" 
     ["Right"]=> 
     string(1) "8" 
     ["ParentID"]=> 
     string(1) "2" 
     ["Name"]=> 
     string(12) "Second Child" 
     ["Children"]=> 
     array(0) { 
     } 
    } 
    } 
} 

비록 당신이 어딘가에 "손자"길을 잃지되어 볼 수 있듯이 projectListToTree의 출력 기능이 있어야한다는 것을 나타내는 것 같습니다. 내가 던지는 나무 구조가 두 번째 수준 아래로 떨어지는 것처럼 보입니다. 무슨 일이 일어날 지에 대한 통찰력?

감사합니다.

Answer 1

배열을 할당해도 참조가 복사되지는 않지만 배열 복사본이 만들어지는 것이 문제입니다. 즉, "Parent"노드의 "children"에있는 "Second Child"배열은 "Grandchild"를 추가하는 배열이 아니라 복사본입니다.

이 문제를 해결하려면, 당신은 명시 적으로 복사하는 대신 참조 할당을 사용해야합니다 :

function projectListToTree($projects) { 
    $stack = Array(); 
    for($x =0; $x < count($projects); $x++) { 
     $project = &$projects[$x]; 
     $project['Children'] = array(); 

     while(count($stack) > 0 && $stack[count($stack) - 1]['Right'] < $project['Right']) { 
       array_pop($stack); 
     } 

     if(count($stack) > 0) { 
       $stack[count($stack) - 1]['Children'][] = &$project; 

       echo "Adding " . $project['Name'] . " to " . $stack[count($stack) - 1]['Name'] . " for a total of " 
         . count($stack[count($stack) - 1]['Children']) . " kids\n"; 

       echo "\n"; 
     } else { 
       echo "No parent\n"; 
     } 

     echo "stack count: " . count($stack) . "\n"; 

     $stack[] = &$project; 
    } 

    echo "Left in stack: " . count($stack) . "\n"; 

    return $stack[0]; 
} 

주, 앰퍼샌드는 세 곳에서 추가 된.

이 문제 때문에 PHP에서 중첩 배열과 대입 연산자를 사용할 때 특히주의해야합니다.

이렇게하면 중첩 된 배열에서 많은 양의 데이터를 사용할 때 프로세서 사용량과 메모리 공간이 많이 소모됩니다. 예를 들어 위의 예제에서 projectListToTree()가 반환되면 전체 배열 트리가 로컬 변수 $ tree에 복사되고 (PHP 가비지 컬렉터가 빠져 나오기 때문에) 메모리에 두 번 저장됩니다.

Answer 2

array_pop()을 호출 할 때 echo 문을 넣었습니까? 테스트없이 이것을 읽는 것으로부터, 당신은 스택에서 레코드를 튕겨 버리고 멀리 내 버리고 있다고 생각합니다.