摆地摊必考知识点-数据结构之树的遍历

      今天，带大家复习IT大厂面试必考知识点——数据结构之树的遍历。摆地摊之前务必掌握，这道是地摊上的送分题！

      二叉树是什么？

      二叉树是一种非常重要的数据结构，很多数据结构都是基于二叉树的基础演变而来的。二叉树有两种，深度遍历和广度遍历：

      深度遍历有前序、中序以及后序三种遍历方法，广度遍历即寻常所说的层次遍历。由于树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历，不仅容易理解，而且代码非常简洁。

      广度遍历则需要其他数据结构的支撑，比方堆。所以，对一段代码而言，可读性往往比代码本身的效率要重要得多。

      二叉树遍历的应用：

      （1）前序遍历：可以用来实现目录结构的显示。

      （2）中序遍历：可以用来做表达式树，在编译器底层实现的时候用户可以实现基本的加减乘除，比如 a*b+c。

      （3）后序遍历可以用来实现计算目录内的文件占用的数据大小。

      （4）层次遍历可用来解决计算机游戏中找寻路径的问题，如解谜宫。

      四种基本的遍历思想为：

      前序遍历：根结点 ---> 左子树 ---> 右子树

      中序遍历：左子树---> 根结点 ---> 右子树

      后序遍历：左子树 ---> 右子树 ---> 根结点

      层次遍历：仅仅需按层次遍历就可以

      新建节点

      初始化界节点

      1. 前序遍历

      递归

      非递归

      2.中序遍历

      递归

      非递归

      3.后序遍历

      递归

      非递归

      4. 层次遍历