二叉树的遍历及其用途

梦里梦外; 2022-05-30 04:58 89阅读 0赞

先序遍历：在第一次遍历到节点时就执行操作，一般只是想遍历执行操作（或输出结果）可选用先序遍历；  
中序遍历：对于二分搜索树，中序遍历的操作顺序（或输出结果顺序）是符合从小到大（或从大到小）顺序的，故要遍历输出排序好的结果需要使用中序遍历;  
后序遍历：后续遍历的特点是执行操作时，肯定已经遍历过该节点的左右子节点，故适用于要进行破坏性操作的情况，比如删除所有节点.

作者：Entronad  
链接：[https://www.zhihu.com/question/22031935/answer/153859490][https_www.zhihu.com_question_22031935_answer_153859490]  
来源：知乎  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

最近在看《大话数据结构》这本书，看到了很早以前学习的前中后遍历，想到了面试的时候被问到了这三种遍历的用途，特地整理一下。  
首先就要先说前中后遍历  
这个东西网上百度一大堆，而且都很简单，其实就是一个口诀。  
根左右（前）  
左根右（中）  
左右根（后）  
有没有发现其实就是‘根’的位置发生了改变，前就是‘根’在前，中在中，后在后。  
按照这个口诀遍历下来就是所谓的前中后遍历。

下来我们说用途  
输出某个文件夹下所有文件名称(可以有子文件夹)—用先序遍历实现。  
统计某个文件夹的大小（该文件夹下所有文件的大小）–用后序遍历实现。  
中缀表达式转为后缀表达式。  
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，利用将其存储在二叉树中，保持中序遍历得到中缀表达式。

这里写图片描述

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

[https_www.zhihu.com_question_22031935_answer_153859490]: https://www.zhihu.com/question/22031935/answer/153859490
[http_www.cnblogs.com_hapjin_p_5396877.html]: http://www.cnblogs.com/hapjin/p/5396877.html