二叉树有多种遍历方法，有层次遍历、深度优先遍历、广度优先遍历等。
本文只涉及二叉树的先序、中序、后序的递归和非递归遍历。
涉及到的代码都用Java编写。
首先给出二叉树节点类：
树节点：
无论是哪种遍历方法，考查节点的顺序都是一样的(思考做试卷的时候，人工遍历考查顺序)。只不过有时候考查了节点，将其暂存，需要之后的过程中输出。
如图1所示，三种遍历方法(人工)得到的结果分别是：
三种遍历方法的考查顺序一致，得到的结果却不一样，原因在于：
先序：考察到一个节点后，即刻输出该节点的值，并继续遍历其左右子树。(根左右)
中序：考察到一个节点后，将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树。(左根右)
后序：考察到一个节点后，将其暂存，遍历完左右子树后，再输出该节点的值。(左右根)
递归先序遍历
递归先序遍历很容易理解，先输出节点的值，再递归遍历左右子树。中序和后序的递归类似，改变根节点输出位置即可。
非递归先序遍历
因为要在遍历完节点的左子树后接着遍历节点的右子树，为了能找到该节点，需要使用栈来进行暂存。中序和后序也都涉及到回溯，所以都需要用到栈。
遍历过程参考注释
先序遍历结果：
递归中序遍历
过程和递归先序遍历类似
非递归中序遍历
和非递归先序遍历类似，唯一区别是考查到当前节点时，并不直接输出该节点。
而是当考查节点为空时，从栈中弹出的时候再进行输出(永远先考虑左子树，直到左子树为空才访问根节点)。
中序遍历结果
递归后序遍历
过程和递归先序遍历类似
非递归后序遍历
后续遍历和先序、中序遍历不太一样。
后序遍历在决定是否可以输出当前节点的值的时候，需要考虑其左右子树是否都已经遍历完成。
所以需要设置一个lastVisit游标。
若lastVisit等于当前考查节点的右子树，表示该节点的左右子树都已经遍历完成，则可以输出当前节点。
并把lastVisit节点设置成当前节点，将当前游标节点node设置为空，下一轮就可以访问栈顶元素。
否者，需要接着考虑右子树，node = node.right。
以下考虑后序遍历中的三种情况：
如图3所示，从节点1开始考查直到节点4的左子树为空。
注：此时的游标节点node = 4.left == null。
此时需要从栈中查看 Peek()栈顶元素。
发现节点4的右子树非空，需要接着考查右子树，4不能输出，node = node.right。
如图4所示，考查到节点7(7.left == null，7是从栈中弹出)，其左右子树都为空，可以直接输出7。
此时需要把lastVisit设置成节点7，并把游标节点node设置成null，下一轮循环的时候会考查栈中的节点6。
如图5所示，考查完节点8之后(lastVisit == 节点8)，将游标节点node赋值为栈顶元素6，节点6的右子树正好等于节点8。表示节点6的左右子树都已经遍历完成，直接输出6。
此时，可以将节点直接从栈中弹出Pop()，之前用的只是Peek()。
将游标节点node设置成null。
后序遍历结果
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/1476.html