问两个算法题目，大家讨论一下，大文件排序和打印树边框
1. 大文件排序，1TB的文件，用来排序的机器只有1GB的内存，怎么排序？
A: 我能够知道的是每次读取1GB的数据，排序好后，放入一个文件中，比如00001.file, 然后依次做下去。但是这生成的1000个文件，怎么归并呢？
2. 打印一个树的外边框，如：
10
5 20
3 8 18 25
1 4 9 12 21
这里打印出来应该是
10, 5, 3, 1, 4, 8, 9, 12, 18, 21, 25, 20
我的理解是，最左边的节点，最右边的节点，和最“下面的节点”。
最下面的节点，我的理解是左，右节点有一个为NULL的节点
但这个程序不太好写
[解决办法]
生成的1000个文件，要分组归并，例如将50个文件分成一组，对每组归并后得到20个文件，再归并20个文件
归并50个文件时，将内存分成51份，1份做输出缓存，另外50份做输入缓存，对50个输入进行堆排序（比较第一个数据的大小），从堆顶的输入缓存中取走一个数据，在将该输入缓存重新插入到堆中（原来第二个数据变成第一个数据了），循环，输入缓存变空时读文件
[解决办法]
深度优先遍历整个树，遍历每个节点时，传几个参数进去，标明该节点的位置
isLeft：是否是左侧节点
isRight：是否是右侧节点
visit(node, isLeft, isRight)
{
if (isLeft) print(node);
visit(node.left, isLeft, false);
visit(node.right, false, isRight);
if (! isLeft && isRight) print(node);
if ( !isLeft && !isLeft )
if ( isLeaf(node) ) print(node);
}
visit(root_node, true, true);
[解决办法]
感觉需要一个全局的来标志根的特殊性。。。否则遍历一遍不能实现吧
一个根节点标志，然后加上左右节点标志。
（标志主要是用来改变遍历方式的，既是不同类型的子树用不同的遍历方法）
最先肯定判定是否为叶子，是则直接打印，否则继续下面
每次先判定是否为根，是则前序遍历，同时给左节点标志上左树标志，右节点标志上右树标志；
再判定是否为左节点，是则继续前序遍历，同时给左节点标志上左树标志，右节点无标志；
最后判定是否为右节点，是则进行后续遍历，同时给右节点标志上右树标志，左节点无标识；
大概思路就是这样子，具体效率的话很多条件判定可以优化下。。。不知道有没有更好的解
[解决办法]
分桶,他们已经说了.
树的边框,其实就是知道节点所在层的最左和最右,再加上叶子.
遍历标记深度,就可以知道了.O(n)逃避不了吧
