二叉树遍历的几种概念

二叉树遍历
从根节点往下查找，先找左子树、直至左子树为空(左子节点逐个入栈、直至左子节点为空)，再找右子树(出栈找右子节点)
四种顺序：按照排序时根节点所在的位置分为以下几种。
前序遍历：根左右，第一次经过节点即打印，直到打印null，往回溯，打印右子树，打印顺序：A->B->D->E->C->F->G

中序遍历：左根右，第二次经过该节点时进行打印，即左边回溯时，打印顺序：D->B->E->A->F->C->G

后序遍历：左右根，第三次经过该节点时进行打印，即右边回溯时，打印顺序：D->E->B->F->G->C->A

层序遍历：按照层级，从上往下，从左到右。使用广度优先搜索算法。
三种方法论:
1、递归遍历：使用递归方法遍历
2、迭代遍历：使用迭代方法实现递归函数，与递归等价
3、morris遍历
再来看一个图形，说出他的遍历顺序：

前序遍历（中左右）：5 4 1 2 6 7 8
中序遍历（左中右）：1 4 2 5 7 6 8
后序遍历（左右中）：1 2 4 7 8 6 5