树排序而不生成树

Question

我需要写一些东西来获取如下数据：

B
    b
    c
    a
A
    b
    a
D
    a
        b
        a   
C

然后这样排序：

A
    a
    b
B
    a
    b
    c
C
D
    a
        a
        b

这些数据看起来正是我上面所说的（除了字母）。它是一个多行字符串，其中选项卡的数量决定了树中的层次结构级别。

我希望能够对层次结构的每个级别进行自己的排序。

我一直很难想出一个像样的算法，所以我在这里问。

我是用PHP做这件事的，但是任何伪代码方法都会非常感激。

此外，我意识到我可以先构建一个树，然后对该树进行排序和输出，但我正在努力寻找一个更优雅的解决方案。

谢谢。

Answer 1

事实上，我在提问的过程中解决了这个问题，所以我会回答我自己的问题，这可能对这里的其他人有帮助。可能还有其他好的答案。。。

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
ttb
tta   
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);