树的遍历与递归

Java基础

浏览数:534

2019-5-10

最近做一个统计工作,需要遍历一些文件,一个文件夹下面有很多层的小文件,如何算出这个文件夹下面有多少文件?相信很多人第一时间都能想到递归遍历,这是最直接,最简单的办法。在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以,递归调用的次数过多,可能会导致栈溢出。当文件夹深度足够深,递归的反复调用会导致方法一直无法释放,造成jvm的栈溢出。那我们该怎么办?

如何遍历文件夹

学过数据结构的都知道,文件夹就类似于数据结构的中的树,遍历文件夹就如同遍历树。常见的遍历思想有深度优先遍历和广度优先遍历,其中递归遍历就属于深度优先遍历的一种。

一、递归遍历

public void traverseFile_recursion(File root) {
    if (root != null) {
        if (root.isDirectory()) {
            File[] files = root.listFiles();
            for (File f : files) {
                traverseFile_recursion(f);
            }
        } else {
            System.out.println(root.getPath());
        }
    }
}

递归方法遍历很容易看懂,递归函数的优点是定义简单,逻辑清晰。这里不细说了,看上面代码就OK了。

二、非递归的深度优先遍历

public void traverseFile_depth(File root) {
    Stack<File> fileStack = new Stack<>();
    File file;
    if (root != null && root.isDirectory()) {
        fileStack.push(root);
    }
    while (!fileStack.isEmpty()) {
        file = fileStack.pop();
        File[] files = file.listFiles();
        for (File f : files) {
            if (f.isDirectory()) {
                fileStack.push(f);
            } else {
                System.out.println(f.getPath());
            }
        }
    }
}

深度优先遍历,借助了一个栈,然后按次序读取文件夹的元素,并判断如果是文件夹则把该文件夹入栈。然后栈顶的文件夹再出栈,遍历,以此类推,直到所有的文件夹都出栈,再也没有文件夹入栈。

三、广度优先遍历

public void traverseFile_Width(File root) {
    Queue<File> fileQueue = new ArrayDeque<>();
    File file;
    if (root != null && root.isDirectory()) {
        fileQueue.add(root);
    }
    while (!fileQueue.isEmpty()) {
        file = fileQueue.remove();
        File[] files = file.listFiles();
        for (File f : files) {
            if (f.isDirectory()) {
                fileQueue.add(f);
            } else {
                System.out.println(f.getPath());
            }
        }
    }
}

广度优先遍历,借助了一个队列,然后按次序读取文件夹的元素,并判断如果是文件夹则把该文件夹加入队尾,然后队首的文件夹再出队,遍历,以此类推,直到所有的文件夹都出队,再也没有文件夹入队。

关于递归的性能问题

虽然递归方法在解决一些问题时,逻辑思路很清晰,在很多情况下递归还是不建议使用的,效率偏低,严重的情况下,会造成栈溢出。解决办法是使用尾递归或者使用循环方式。理论上,所有的递归函数都可以写成循环的方式,但循环的逻辑不如递归清晰。下面,举例子说明一下

一、斐波拉契数列

斐波拉契数列指的是这样一个数列:1、1、2、3、5、8、13、21、34、……第1个和第2个数是1,从第3个位置起,每个数等于它前面两个数的和。求第 n 个位置的数是多少?
使用递归方法实现很简单,方法如下:

public long fun1(int x) {
    if (x == 1)
        return 1;
    else if (x == 2)
        return 1;
    else {
        return fun1(x - 1) + fun1(x - 2);
    }
}

测试代码如下:

public static void main(String[] args) {
    long start_time = System.currentTimeMillis();
    long result = new Fibo().fun1(46);
    System.out.println("结果:  " + result);
    long end_time = System.currentTimeMillis();
    System.out.println("耗时: " + (end_time - start_time));
}

以下是基于我的PC(i7-7700,16G-DDR4-2400)的执行结果:
位置:46

结果:  1836311903
耗时: 5170

位置:47

结果:  2971215073
耗时: 8355

位置:48

结果:  4807526976
耗时: 13377

位置:49

结果:  7778742049
耗时: 21941

位置:50

结果:  12586269025
耗时: 34915

位置:51

结果:  20365011074
耗时: 57158

看这个时间增加,你还想用递归求吗?求位置51的用时接近一分钟。
下面用循环来实现:

public long fun2(int x) {
    long num1 = 1;
    long num2 = 1;
    long result = 0;
    if (x == 1) {
        return 1;
    } else if (x == 2) {
        return 1;
    } else {
        for (int i = 3; i <= x; i++) {
            result = num1 + num2;
            num1 = num2;
            num2 = result;
        }
        return result;
    }
}

同样测试位置 51 的结果:

结果:  20365011074
耗时: 0

几乎是秒算出结果。再看看100位置:

结果:  3736710778780434371
耗时: 1

同样几乎是秒出结果。这说明,用循环的方式,时间几乎是常数级的。若要用递归方式求100位置的,我想我可以让程序执行,然后去睡觉了。

二、遍历打印 List 元素

上面关于递归使用,由于迭代层次还没到一定级别,所以只能时间长,还没到栈溢出的地步,下面我们测试一下遍历上万元素的了 List ,来说明,上代码:

public static void printElement(Iterator<Integer> iterator) {
    if (!iterator.hasNext()) {
        return;
    } else {
        System.out.println(iterator.next());
        printElement(iterator);
    }
}

测试代码:

public static void main(String[] args) {
    List<Integer> list = new ArrayList();
    for (int i = 0; i < 20000; i++) {
        list.add(i);
    }
    long start_time = System.currentTimeMillis();
    printElement(list.iterator());
    long end_time = System.currentTimeMillis();
    System.out.println("耗时: " + (end_time - start_time));
}

我们用递归的方式遍历 List ,运行结果部分截图:

程序崩了,报的错,正是栈溢出。下面用循环方式遍历:

public static void printElement2(Iterator<Integer> iterator) {
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}

测试结果部分截图如下:

方法调用时的内存情况

下面摘录《数据结构预算法分析-Java语言描述》中的几段话:
说明了方法调用的过程,由此也解释了深层次递归性能低的原因。

当调用一个新方法时,主调例程的所有局部变量需要由系统存储起来,否则被调用的新方法将会重写由主调例程的变量所使用的内存。不仅如此,该主调例程的当前位置也必须要存储,以便在新方法运行完后知道向哪里转移。这些变量一般由编译器指派给机器的寄存器,但存在某些冲突(通常所有的方法都是获取指定给1号寄存器的某些变量),特别是涉及到递归的时候。该问题类似于平衡符号的原因在于,方法调用和方法返回基本上类似于开括号和闭括号。

当存在方法调用的时候,需要存储的所有重要信息,诸如寄存器的值(对应变量的名字)和返回地址 (它可从程序计数器得到,一般情况是在一个寄存器中)等, 都要以抽象的方法存在“一张纸上”并被置于一个堆(pile)的顶部。然后控制转移到新方法,该方法自由地用它的一些值替代这些寄存器。如果它又进行其它的方法调用,那么它也遵循相同的过 程。当该方法要返回时,它查看堆顶部的那张“纸”并复原所有的寄存器,然后进行返回转移。

显然,所有全部工作均可由一个栈来完成,而这正是在实现递归的每一种程序设计语言中实际发生的事实。所储存的信息或称为活动记录(activation record),或叫做帧栈(stack frame)。

在实际计算机中的栈常常是从内存分区的高端向下增长,而在许多非Java系统中是不检测溢出的。失控递归可能导致栈溢出。

作者:SharpCJ