489 字
1 分钟
二叉树遍历简单介绍
二叉树的遍历
根据节点的访问顺序，分为广度优先和深度优先。他们是一种通用的遍历，后面的图也会用到。
我们先来看广度优先。
一、广度优先
是层序遍历，正好利用树的深度的概念。
广度优先是层序遍历，我们会首先访问节点的孙子再访问孩子，一层一层往下访问。
上面的二叉树用广度优先遍历的结果就是：F,D,J,B,E,G,K,A,C,I,H
二、深度优先
深度优先则不同，它不是一种遍历，而是 3 种遍历方式的统称——前序、中序、后序。
我们会先来到一个孩子，然后完成它所有的孩子节点。换句话说就是会访问路径上所有F（上图根节点）的孙子节点。
<root><left><right>——preorder前序，采用（DLR——data，left，right）的模式<left><root><right>——inorder中序，采用(LDR)<left><right><root>——postorder后序,(LRD)
可以看到，节点所处的位置决定是哪种遍历方式。
我们来模拟一下前序遍历
前序遍历
DLR:即data，left，right
碰到data就输出当前节点的值，碰到left就访问左子树，碰到right就右子树
根据DLR顺序，先根，再搞完左子树，最后搞右子树
这边展示了左子树的遍历，右子树也是一样的。
中序遍历
LDR，我们来模拟一下。
先走左子树，接着L碰到NULL后开始D（输出节点），然后走右边（R），R碰到NULL后完成当前节点遍历，开始往回走。
ok,左边就这么水灵灵完成了。右边也是一个道理。
后序遍历和上面两个差不多，再此不做演示了！纯纯偷懒😋
部分信息可能已经过时