二叉树的7种遍历算法
一、先根递归遍历算法
思路：
1.若二叉树为空则退出，否则进行以下步骤
2.访问当前的根节点
3.先根顺序遍历访问左子树
4.先根顺序遍历访问右子树
5.退出
代码（java版）：
public static void proOrder(Node T) {if (T != null) {// 获取当前树的根结点System.out.println(T);// 先序遍历左子树proOrder(T.getLeft());// 先序遍历右子树proOrder(T.getRight());}}
二、中根递归遍历算法
思路：
1.若二叉树为空则退出，否则进行以下步骤
2.中根顺序遍历访问左子树
3.访问当前的根节点
4.中根顺序遍历访问右子树
5.退出
代码（java版）：
public static void inOrder(Node T) {if (T != null) {// 中根顺序遍历左子树inOrder(T.getLeft());// 访问当前根节点数据System.out.println(T);// 中根顺序遍历右子树inOrder(T.getRight());}}
三、后根递归遍历算法
思路：
1.若二叉树为空则退出，否则进行以下步骤
2.后根顺序遍历访问左子树
3.后根顺序遍历访问右子树
4.访问当前的根节点
5.退出
代码(java版)
public static void postOrder(Node T) {if (T != null) {// 后根顺序遍历左子树postOrder(T.getLeft());// 后根顺序遍历右子树postOrder(T.getRight());// 访问当前根结点System.out.println(T);}}
任何一个递归算法，我们都可以借助栈将其改造成非递归算法！这里我们对以上三个递归算法进行非递归改造，*即不会出现自己调用自己的现象*。
四、先根非递归遍历算法
思路：
1.当前结点不为null*或*栈不空时，判断当前结点是否为空
(1)不为空：访问当前结点，然后将其入栈，并且将当前结点置为其左孩子结点
(2)为空：栈顶结点出栈（但不去访问该节点），然后将当前结点置为出栈结点的右孩子结点
2.直到当前结点为null并且栈空时，遍历结束并退出循环
代码(java版)：
public static void proOrder2(Node T) {Stack<Node> stack = new Stack<>();Node cur = T;// 当前结点为null并且栈空时，遍历结束退出循环while (cur != null || !stack.empty()) {if (cur != null) {System.out.println(cur);stack.push(cur);cur = cur.getLeft();} else {// 出栈Node stackTop = stack.pop();cur = stackTop.getRight();}}}
五、中根非递归遍历算法
思路：
1.当前结点不为null*或*栈不空时，判断当前结点是否为空
(1)不为空：将其入栈，并且将当前结点置为其左孩子结点
(2)为空：栈顶结点出栈，并去访问出栈的结点，然后将当前结点置为出栈结点的右孩子结点
2.直到当前结点为null并且栈空时，遍历结束并退出循环
代码(java版)：
public static void inOrder2(Node T) {Stack<Node> stack = new Stack<>();Node cur = T;// 当前结点为null并且栈空时，遍历结束退出循环while (cur != null || !stack.empty()) {if (cur != null) {stack.push(cur);cur = cur.getLeft();} else {// 出栈Node stackTop = stack.pop();System.out.println(stackTop);cur = stackTop.getRight();}}}
六、后根非递归遍历算法
思路：
1.当前结点不为null*或*栈不空时，判断当前结点是否为空
(1)不为空：将其入栈，并且将当前结点置为其左孩子结点
(2)为空：当栈顶元素的右孩子结点为null或者右子树已经遍历过时栈顶结点出栈并输出，否则将当前结点置为栈顶结点的右孩子结点
2.直到当前结点为null并且栈空时，遍历结束并退出循环
代码(java版)：
public static void postOrder2(Node T) {Stack<Node> stack = new Stack<>();Node cur = T;Node lastPop = null; // 最近一次出栈的结点// 当前结点为null并且栈空时，遍历结束退出循环while (cur != null || !stack.empty()) {if (cur != null) {stack.push(cur);cur = cur.getLeft();} else {// 当栈顶元素的右孩子结点为null或者右子树已经遍历过时出栈并输出，否则将当前结点置为栈顶结点的右孩子结点Node stackTop = stack.peek();if (stackTop.getRight() == null || stackTop.getRight() == lastPop) {lastPop = stackTop;stackTop = stack.pop();System.out.println(stackTop);} else {cur = stackTop.getRight();}}}}
七、层序遍历算法
思路：
1.创建一个队列，并将根节点排队
2.当队列非空时，从队列里取出一个结点并从队列里删除，然后访问该结点，最后若该节点的左孩子结点非空则排队，右孩子结点非空则排队。
3.当队列为空时，退出循环，遍历结束。
代码(java版)：
public static void layerOrder(Node T) {// LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用Queue<Node> queue = new LinkedList<>();Node cur = T;queue.add(cur);// 当队列为空时退出循环while (!queue.isEmpty()) {// 取出并删除队列头部元素Node poll = queue.poll();System.out.println(poll);// 当左孩子结点非空时排队if (poll.getLeft() != null) {queue.add(poll.getLeft());}// 当右孩子结点非空时排队if (poll.getRight() != null) {queue.add(poll.getRight());}}}
但行好事，莫问前程！只争朝夕，做好现在！