先序遍历中序遍历后序遍历层序遍历数据结构

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

文章图片

前序/中序/后序的递归结构遍历：是根据访问结点操作发生位置命名,遍历的路径都相同，只是访问的顺序不同。 【先序遍历中序遍历后序遍历层序遍历】
文章图片

NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
首先访问根节点，再访问左子树，再访问右子树，是一个递归调用的过程。
先访问根节点A，然后访问左子树B，此时B由是根节点，再访问B的左子树D，此时D的左子树为NULL，然后访问D的右子树，D的右子树为NULL，此时返回D节点，此时D节点作为B的左子树已经访问完成，下来我们该访问B的右子树E，此时E为根节点，我们再访问E的左子树G，此时G为根节点，G的左右子树为NULL，我们返回上一层，访问E的右子树，右子树为空，我们回到B，B的左右子树也访问完成了，我们回到A节点，A节点的左子树访问完成，该访问右子树C，此时C为根节点，访问它的左子树，和右子树F，然后F为根节点，再访问F的左右子树，左右子树为空，返回上一层，此时A的左右子树全部遍历完成。

先序遍历的结果为：A B D NULL NULL E G NULL NULL NULL C NULL F NULL NULL.