彻底理解二叉树三种遍历[数据结构与算法]

所谓遍历（Traversal）是指沿着某条搜索路线，依次对树中每个结点均做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其他运算的基础。

二叉树遍历

所谓遍历（Traversal）是指沿着某条搜索路线，依次对树中每个结点均做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其他运算的基础。

在二叉树的遍历中存在三种较为常用的遍历方式：前序遍历，中序遍历，后序遍历。

二叉树的结构

前序遍历

  • 先访问根节点
  • 在序遍历左子树
  • 最后序遍历右子树

前序遍历

从gif图上我们可以看出，前序遍历是从根结点开始从左边遍历各个点，当遍历到一个结点的前辅助点的时候，我们将这个数取出，最后我们得出前序遍历。

中序遍历

  • 先中序遍历左子树
  • 在访问根节点
  • 最后中序遍历左子树

中序遍历

后序遍历

  • 先后序遍历左子树
  • 在后续遍历右子树
  • 最后访问根节点

后序遍历

参考：

https://www.jianshu.com/p/45d75aeb3b01