樹排序未做樹

我需要寫一些東西，需要的數據，看起來像這樣：樹排序未做樹

而且這樣的排序是：

的數據看起來究竟如何我在上面介紹它（除了字母）。它是一個多行字符串，其中選項卡的數量決定樹中層次結構的級別。

我希望能夠對自己的每個層次進行排序。

我一直有麻煩提出一個體面的算法，所以我在這裏問。

我正在做這個在PHP中，但是任何僞代碼方法將不勝感激。

此外，我意識到我可以先構建一棵樹，然後排序並輸出該樹，但我試圖找到一個更優雅的解決方案。

謝謝。

來源

2012-07-17 chaimp

我實際上解決了這個問題，因爲我在詢問過程中，所以我會回答我自己的問題，這可能對這裏的其他人有幫助。可能有其他很好的答案，以及...

class TreeLineSorter { 
    function sort($tree_lines) { 
     $sorted_line_groups = $this->group_and_sort_lines($tree_lines); 

     return $this->get_sorted_lines($sorted_line_groups); 
    } 

    private function cmp_line_groups($a, $b) { 
     return strcasecmp($a[0], $b[0]); 
    } 

    private function get_line_level($line) { 
     return strspn($line, "\t"); 
    } 

    private function get_line_groups($lines) { 
     $curr_level = $this->get_line_level($lines[0]); 
     $line_groups = array(); 
     $idx = -1; 

     foreach($lines as $line) { 
      $level = $this->get_line_level($line); 

      if ($level == $curr_level) { 
       $idx++; 
      } 

      $line_groups[$idx][] = $line; 
     } 

     return $line_groups; 
    } 

    private function group_and_sort_lines($lines) { 
     $line_groups = $this->get_line_groups($lines); 

     usort($line_groups, array($this,'cmp_line_groups')); 

     foreach($line_groups as $key=>$group) { 
      if (sizeof($group) > 1) { 
       $new_group = array(array_shift($group)); 
       $new_group = array_merge($new_group, $this->group_and_sort_lines($group)); 

       $line_groups[$key] = $new_group; 
      } 
     } 

     return $line_groups; 
    } 

    private function get_sorted_lines($sorted_line_groups) { 
     $lines = array(); 

     foreach($sorted_line_groups as $group) { 
      if (is_array($group)) { 
       if (sizeof($group) > 1) { 
        $lines = array_merge($lines, $this->get_sorted_lines($group)); 
       } 
       else { 
        $lines[] = $group[0]; 
       } 
      } 
      else { 
       $lines[] = $group; 
      } 
     } 

     return $lines; 
    } 
}

這裏是使用例子：

$sample_text = <<<QES 
B 
\tb 
\tc 
\ta 
A 
\tb 
\ta 
D 
\ta 
\t\tb 
\t\ta 
C 
QES; 

    $tree_lines = explode("\n",$sample_text); 

    $tree_line_sorter = new TreeLineSorter(); 

    $sorted_tree_lines = $tree_line_sorter->sort($tree_lines); 

    print_r($tree_lines); 
    print_r($sorted_tree_lines);

來源

2012-07-17 02:30:08 chaimp

樹排序未做樹

回答

相關問題