二叉树的遍历及其用途

喜欢ヅ旅行 2022-06-10 10:13 138阅读 0赞

### 最近在看《大话数据结构》这本书，看到了很早以前学习的前中后遍历，想到了面试的时候被问到了这三种遍历的用途，特地整理一下。 ###

--------------------

#### 首先就要先说前中后遍历 ####

> 这个东西网上百度一大堆，而且都很简单，其实就是一个口诀。  
> 根左右（前）  
> 左根右（中）  
> 左右根（后）  
> **有没有发现其实就是‘根’的位置发生了改变，前就是‘根’在前，中在中，后在后。**  
> 按照这个口诀遍历下来就是所谓的前中后遍历。

--------------------

### 下来我们说用途 ###

1.  输出某个文件夹下所有**文件名称**(可以有子文件夹)—用先序遍历实现。
2.  统计某个文件夹的大小（该文件夹下**所有文件的大小**）–用后序遍历实现。
3.  中缀表达式转为后缀表达式。

--------------------

**1输出文件名称的过程如下：**

如果是文件夹，先输出文件夹名，然后再依次输出该文件夹下的所有文件(包括子文件夹)，如果有子文件夹，则再进入该子文件夹，输出该子文件夹下的所有文件名。这是一个典型的先序遍历过程。

**2统计文件夹的大小过程如下：**

若要知道某文件夹的大小，必须先知道该文件夹下所有文件的大小，如果有子文件夹，若要知道该子文件夹大小，必须先知道子文件夹所有文件的大小。这是一个典型的后序遍历过程。

**3中缀表达式转为后缀表达式（逆波兰表达式）。**

中缀表达式是一个通用的算术或逻辑公式表示方法。符合人类的逻辑（例：3 + 4）  
后缀表达式是一种不需要括号的表达法。符合计算机的逻辑（例：3 4 +）  
如果有《大话数据结构》这本书的可以看看P105

--------------------

### 代码实现 ###

**1输出文件名称**

public void list(File f){
        list(f, 0);
    }
    public void list(File f, int depth){
        printName(f, depth);
        if(f.isDirectory()){
            File[] files = f.listFiles();
            for (File file : files) {
                list(file, depth + 1);
            }
        }
    }
    
     private void printName(File f, int depth){
        String name = f.getName();
        for(int i = 0; i < depth; i++)
            System.out.print("    ");
        if(f.isDirectory())
            System.out.println("Dir:" + name);
        else
            System.out.println(f.getName() + ":" + f.length()/1024 + "KB");
    }

**2统计文件夹的大小**

private long totalSize(File f){
        long size = 0;
        if(f.isFile())
        {
            size = f.length();
        }
        else
        {
            File[] files = f.listFiles();
            for (File file : files) {
                size += totalSize(file);
            }
        }
        return size;
    }

关于统计大小的详情可以参考[http://www.cnblogs.com/hapjin/p/5396877.html][http_www.cnblogs.com_hapjin_p_5396877.html]  
**3中缀表达式转为后缀表达式**

假设一个表达式，a+b\*c+d-e/f，利用将其存储在二叉树中，保持中序遍历得到中缀表达式。

![这里写图片描述][SouthEast]

其中序遍历是常见的，后序遍历是abc\*+d+ef/-

[http_www.cnblogs.com_hapjin_p_5396877.html]: http://www.cnblogs.com/hapjin/p/5396877.html
[SouthEast]: /images/20220610/52a7715721a3468a9ca1a30785e237b7.png