递归算法：二叉树前序、中序、后序遍历解析与递归思想深度剖析_先序、中序和后序遍历递归算法

文章目录

• 一、二叉树的遍历
• 二、 前序遍历
• 三、中序遍历
• 四、后序遍历
• 五、二叉树的层序遍历

一、二叉树的遍历

学习二叉树链式结构，最简单的方式就是遍历。所谓 二叉树遍历(Traversal) 是按照某种特定的规则，依次对二叉树中的结点进行相应的操作，并且每个结点只操作一次。

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

1. 前序遍历( Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历( Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历( Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后

访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

1.1 链式结构二叉树的创建

这里只是模拟创建一下链式二叉树真正的结构并不是这样创建的：