根據(jù)中序遍歷的順序，對(duì)于任一結(jié)點(diǎn)昌罩，優(yōu)先訪問(wèn)其左孩子，而左孩子結(jié)點(diǎn)又可以看做一根結(jié)點(diǎn)灾馒，然后繼續(xù)訪問(wèn)其左孩子結(jié)點(diǎn)茎用，直到遇到左孩子結(jié)點(diǎn)為空的結(jié)點(diǎn)才進(jìn)行訪問(wèn)，然后按相同的規(guī)則訪問(wèn)其右子樹(shù)。因此其處理過(guò)程如下：

對(duì)于任一結(jié)點(diǎn)root绘搞，引入一個(gè)輔助節(jié)點(diǎn)p彤避，其作用是：標(biāo)記已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)，

1)將root壓入棧中夯辖，只有有左孩子琉预，就壓入棧中

  if(p!=null &&  p.left!=null) {
                stk.add(p.left);
                p = p.left;
            }

2)對(duì)棧頂元素 q 進(jìn)行出棧操作，訪問(wèn)該棧頂結(jié)點(diǎn)蒿褂。

如果 q 沒(méi)有右孩子圆米，將輔助節(jié)點(diǎn) p 設(shè)置為null。表示下一步還是進(jìn)行2）操作啄栓，出棧操作

如果 q 有右孩子娄帖，將右孩子壓棧中，p = q的右孩子

     p = stk.pop();//彈出棧頂節(jié)點(diǎn)  左孩子--->根節(jié)點(diǎn)
                System.out.print(p.val+" ");//訪問(wèn)
                if(p!=null && p.right!=null) {//如果棧點(diǎn)元素有右孩子的話昙楚，將有節(jié)點(diǎn)壓入棧中
                    stk.add(p.right);
                    p = p.right;
                }else
                    p = null;//p=stk.pop;已經(jīng)訪問(wèn)過(guò)p了近速，p設(shè)置為null

3)直到棧為空，遍歷結(jié)束堪旧。

代碼重點(diǎn)是削葱，2先訪問(wèn)出棧，然后將5節(jié)點(diǎn)呀入棧中

import java.util.Stack;
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class Main {
    //中序遍歷 遞歸算法
    public static void InOrder(TreeNode root) {
        if(root==null)return;
        InOrder(root.left);
        System.out.print(root.val+" ");
        InOrder(root.right);
    }
    // 中序遍歷 非遞歸算法
    public static void InOrder2(TreeNode root) {
        if(root==null)return;
        Stack<TreeNode> stk = new Stack<TreeNode>();
        TreeNode p = root;//輔助節(jié)點(diǎn)
        stk.add(p);
        while(stk.isEmpty() == false) {
            //只要你有左孩子淳梦，就將左孩子壓入棧中
            if(p!=null &&  p.left!=null) {
                stk.add(p.left);
                p = p.left;
            }else {
                p = stk.pop();//彈出棧頂節(jié)點(diǎn)  左孩子--->根節(jié)點(diǎn)
                System.out.print(p.val+" ");//訪問(wèn)
                if(p!=null && p.right!=null) {//如果棧點(diǎn)元素有右孩子的話析砸，將有節(jié)點(diǎn)壓入棧中
                    stk.add(p.right);
                    p = p.right;
                }else
                    p = null;//p=stk.pop;已經(jīng)訪問(wèn)過(guò)p了，p設(shè)置為null
            }
        }
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
         root.left = new TreeNode(2);
         root.right = new TreeNode(3);
         
         root.left.left = new TreeNode(4);
         root.left.right = new TreeNode(5);
 
         root.right.left = new TreeNode(6);
         root.right.right = new TreeNode(7);    
         
         InOrder2(root);
    }
 
}