| 二叉树的前序中序和后续遍历及应用场景 | 您所在的位置：网站首页 › 先序遍历顺序是什么 › 二叉树的前序中序和后续遍历及应用场景 |
二叉树的前序中序和后续遍历及应用场景
|
二叉树的结构定义 public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } }二叉树的遍历通常有前序，中序和后续三种。遍历算法通常使用递归实现。 先序遍历就是先访问树的根节点，再访问树的左子节点，再访问右子节点。 中序遍历就是先访问树的左子节点，再访问树的根节点，再访问右子节点。 先序遍历就是先访问树的左子节点，再访问树的右子节点，再访问根节点。 测试的二叉树的结构如下： 遍历算法如下： public class Solution { public static void main(String[] args) { //构造链表结构测试用 TreeNode a = new TreeNode(1); TreeNode b = new TreeNode(2); TreeNode c = new TreeNode(3); TreeNode d = new TreeNode(4); TreeNode e = new TreeNode(5); TreeNode f = new TreeNode(6); TreeNode g = new TreeNode(7); a.left = b; a.right = c; b.right = d; c.left = e; c.right = f; f.left = g; System.out.print("recursivePreOrder: "); recursivePreOrder(a); System.out.print('\n' + "recursiveInOrder: "); recursiveInOrder(a); System.out.print('\n' + "recursivePostOrder: "); recursivePostOrder(a); System.out.print('\n' + "iterativePreOrder: "); } public static void visit(TreeNode p) { System.out.print(p.val + " "); } //**********递归的先序遍历********** public static void recursivePreOrder(TreeNode p) { if (p == null) return; visit(p); recursivePreOrder(p.left); recursivePreOrder(p.right); } //**********递归的中序遍历********** public static void recursiveInOrder(TreeNode p) { if (p == null) return; recursiveInOrder(p.left); visit(p); recursiveInOrder(p.right); } //**********递归的后序遍历********** public static void recursivePostOrder(TreeNode p) { if (p == null) return; recursivePostOrder(p.left); recursivePostOrder(p.right); visit(p); } }程序运行结果： 上述三种递归遍历方式时间复杂度和空间复杂度分析：时间复杂度0(n)，空间复杂度O(n) 。 对于具有n个结点的二叉树,不论其形态如何,进行先序，中序或后序遍历的时间复杂度均为O（n）。 因为对二叉树的遍历访问且仅访问所有结点一次，所以时间复杂度为O(n)。 二叉树遍历的应用： （1）前序遍历：可以用来实现目录结构的显示。 （2）中序遍历：可以用来做表达式树，在编译器底层实现的时候用户可以实现基本的加减乘除，比如 a*b+c。 （3）后序遍历可以用来实现计算目录内的文件占用的数据大小~非常有用。 表达式求值也可以使用后缀表达式。后缀表达式求值比中缀表达式更方便，可以先把中缀表达式变成后缀表达式，然后再根据后缀表达式求值。 1.对于前序遍历，可以用来实现输出某个文件夹下所有文件名称(可以有子文件夹)，就是目录结构的显示。 输出文件名称的过程如下： 如果是文件夹，先输出文件夹名，然后再依次输出该文件夹下的所有文件(包括子文件夹)，如果有子文件夹，则再进入该子文件夹，输出该子文件夹下的所有文件名。这是一个典型的先序遍历过程。 2.对于前序遍历，可以用来统计某个文件夹的大小（该文件夹下所有文件的大小） 统计文件夹的大小过程如下： 若要知道某文件夹的大小，必须先知道该文件夹下所有文件的大小，如果有子文件夹，若要知道该子文件夹大小，必须先知道子文件夹所有文件的大小。这是一个典型的后序遍历过程。 学以致用,知道一个算法的用途才可以更好的学习他,更愿意深入学习这个算法。 参考：（1）https://blog.csdn.net/wayne566/article/details/79106372 （2）https://blog.csdn.net/zlklove1234/article/details/42496617 （3）https://www.cnblogs.com/hapjin/p/5396877.html |
【本文地址】