Làm cách nào để định dạng dữ liệu Mô hình Tập hợp lồng nhau thành một mảng?

Question

Hãy đào trong vấn đề chính ngay lập tức, tôi có đầu vào như thế này

$category = array(
    'A' => array('left' => 1, 'right' => 8), 
    'B' => array('left' => 2, 'right' => 3), 
    'C' => array('left' => 4, 'right' => 7), 
    'D' => array('left' => 5, 'right' => 6), 
    'E' => array('left' => 9, 'right' => 10), 
); 

Tôi muốn đầu ra được một cái gì đó như thế này

$tree = array(
    array('A', 'B'), 
    array('A', 'C', 'D'), 
    array('E'), 
); 

cái nào là chức năng tốt nhất và nhanh chóng để lặp mặc dù mảng đầu vào và tạo kết quả đầu ra như thế này?

Answer 1

Làm việc với bộ lồng nhau là trường hợp hoàn hảo để đệ quy.

Với dữ liệu của bạn:

$category = array(
    'A' => array('left' => 1, 'right' => 9), 
    'B' => array('left' => 2, 'right' => 4), 
    'C' => array('left' => 5, 'right' => 8), 
    'D' => array('left' => 6, 'right' => 7), 
    'E' => array('left' => 10, 'right' => 11), 
); 

Sau đây sẽ phá vỡ dữ liệu bộ lồng nhau của bạn xuống thành một mảng đúng lồng nhau trong PHP:

function createTree($category, $left = 0, $right = null) { 
    $tree = array(); 
    foreach ($category as $cat => $range) { 
     if ($range['left'] == $left + 1 && (is_null($right) || $range['right'] < $right)) { 
      $tree[$cat] = createTree($category, $range['left'], $range['right']); 
      $left = $range['right']; 
     } 
    } 
    return $tree; 
} 

$tree = createTree($category); 
print_r($tree); 

Output:

Array 
(
    [A] => Array 
     (
      [B] => Array 
       (
       ) 

      [C] => Array 
       (
        [D] => Array 
         (
         ) 

       ) 

     ) 

    [E] => Array 
     (
     ) 

) 

Sau đó, bạn có thể làm phẳng cây thích hợp của bạn thành định dạng bạn muốn với:

function flattenTree($tree, $parent_tree = array()) { 
    $out = array(); 
    foreach ($tree as $key => $children) { 
     $new_tree = $parent_tree; 
     $new_tree[] = $key; 
     if (count($children)) { 
      $child_trees = flattenTree($children, $new_tree); 
      foreach ($child_trees as $tree) { 
       $out[] = $tree; 
      } 
     } else { 
      $out[] = $new_tree; 
     } 
    } 
    return $out; 
} 

$tree = flattenTree($tree); 
print_r($tree); 

Output:

Array 
(
    [0] => Array 
     (
      [0] => A 
      [1] => B 
     ) 

    [1] => Array 
     (
      [0] => A 
      [1] => C 
      [2] => D 
     ) 

    [2] => Array 
     (
      [0] => E 
     ) 

) 

Answer 2

Nếu bạn không muốn sử dụng đệ quy:

foreach ($category as $name => $range) { 
    $line[$range['left']] = $name; 
    $line[$range['right']] = $name; 
} 

ksort($line); 
$count = 0; 

foreach($line as $name) { 
    if (! isset($open[$name])) { 
     $open[$name] = true; 
     $result[$name] = true; 
     $count++; 
    } else { 
     unset($open[$name]); 
     if ($count > 0) { 
      $count = 0; 
      $tree[] = array_keys($result); 
      $result = $open; 
     } else { 
      $result = array(); 
     } 
    } 
} 

Answer 3

Một giải pháp khác, mà không đệ quy (thử nghiệm xin vui lòng)

$result = array(); 

    foreach($category as $key => $value) { 

     /*Get current row index*/ 
     $i = count($result); 

     if($i == 0) { 
      $result[] = array($key); 
     } else { 

      $iParent = -1; 

      /*Find parent index*/ 
      for($j = count($result[$i-1]) - 1; $j >= 0; $j--) { 
       if($value['left'] > $category[$result[$i-1][$j]]['left'] 
        && $value['right'] < $category[$result[$i-1][$j]]['right']) { 
        $iParent = $j; 
        break; 
       } 
      } 

      if($iParent == -1) { $result[] = array($key);} 

      if($iParent == count($result[$i-1]) - 1) { 
       // append to last 
       $result[$i-1][] = $key; 
      } else { 
       // make new list 
       $result[$i] = array_slice($result[$i-1], 0, $iParent + 1); 
       $result[$i][] = $key; 
      } 
     } 
    } 

    print_r($result); 

Answer 4

Có một lỗi với hàm trên. Danh mục hàng đầu của mảng thứ hai của @tree bị xóa. Đây là bản sửa lỗi:

foreach ($category as $name => $range) { 
    $line[$range['left']] = $name; 
    $line[$range['right']] = $name; 
} 

ksort($line); 
$tree = array(); 
$count = 0; 

foreach ($line as $name) { 
    if (!isset($open[$name])) { 
     $open[$name] = true; 
     $count++; 
    } 
    else { 
     if ($count > 0) { 
      $count = 0; 
      $tree[] = array_keys($open); 
     } 
     unset($open[$name]); 
    } 
} 

Answer 5

Tôi ít sửa đổi mã của Stiven.

public function createTree($category, $left = 0, $right = null) { 
    $tree = array(); 
    foreach ($category as $cat => $range) { 
     if ($range['clf'] == $left + 1 && (is_null($right) || $range['crt'] < $right)) { 
      $tree[$cat]= array(); 
      $tree[$cat]['title']=$range['title']; 
      if($range['crt']-$range['clf']>1){ 
       $tree[$cat]['sub'] = $this->createTree($category, $range['clf'], $range['crt']); 
      } 
      $left = $range['crt']; 
     } 
    } 
    return $tree; 
}