二叉树遍历

定义：

二叉树遍历是指从根结点开始，按照一定的路径顺序，依次访问二叉树中的所有结点。

特点：

每个结点仅且被访问一次。

遍历类型：

前序遍历中序遍历后序遍历层序遍历

遍历规则：

从上往下：先跟结点后其子代及后裔

从左往右：先左子树后右子树

前序遍历

定义：

从二叉树的根结点出发，当第一次到达结点时就输出结点数据。

访问规则：

从左到右访问

特点：

不加子树，第一次访问即输出。

输出结果格式：

根左右

访问过程图解：

输出结果：

ABDHIEJCFG

应用场景：

用来实现目录结构的显示（实现输出某个文件夹下所有文件名称）中序遍历

定义：

从二叉树的根结点出发，当第二次到达结点时就输出结点数据。

访问规则：

从左到右访问

特点：

加子树，第二次访问即输出。

输出结果格式：

左根右

访问过程图解：

输出结果：

HDIBJEAFCG

应用场景：

用来做编译器底层实现的表达式树，实现基本的加减乘除（a+b*c）后序遍历

定义：

从二叉树的根结点出发，当第二次到达结点时就输出结点数据。

访问规则：

从左到右访问

特点：

加子树，第二次访问即输出。

输出结果格式：

左根右

访问过程图解：

输出结果：

HIDGEBFGCA

应用场景：

用来统计某个文件夹占据数据的大小（所有子文件的内存之和）层序遍历

定义：

从二叉树的根结点出发，按层从低到高遍历输出。

访问规则：

从左到右，从上到下访问。

特点：

层序之间，首尾相连。

输出结果格式：

层次顺序，数据输出

访问过程图解：

应用场景：

判断是否是完全二叉树；判断二叉树的宽度 ；非递归二叉树的深度 ；删除以x为根的子树；求二叉树的带权路径长度 ；之字形遍历二叉树 ；

本文部分内容参考至网络，如有错误，敬请指正，如有侵权，请联系修改。