[数据结构与算法]二叉树中序遍历的非递归实现

（复习快打一些自己的理解以帮助记忆，有误之处劳烦指出）

先上代码，参考王道21年数据结构讲义

void InOrder2(BiTree T){
	InitStack(k);	//初始化栈
	BiTree p = T;		//p是遍历指针
	while(p || !IsEmpty(S)){
		if(p){	//一路向左
			Push(S, p);
			p = p->lchild;	//左孩子非空，一路向左
		}else{	//出栈，访问栈顶结点右子树
			Pop(S, p);
			visit(p);
			p = p->rchild
		}
	}//while
}

首先明确：

1. 栈帮助确定访问顺序，visit才是访问输出。
2. 根节点三个作用：访问本身、转向左子结点、转向右子结点。路过了但三个功能未全部完成的都在栈里，只有全完成了才可出栈。（三种遍历都适用）
3. 树从上往下遍历是入栈过程，从下往上是出栈过程。
4. 遍历过程中：左孩子为空说明再无左子树，可访问根节点（visit），再访问右子树。右子树不空则遍历之；右子树为空则说明当前结点及以下已全部遍历完，可返回上一级结点。

Q1：中序遍历的第一个结点？
A：二叉树的最左下结点。因为中序遍历只有访问完左子树才能访问根节点，in other word，不先把左边的访问了轮不到中间的。

Q2：为什么栈顶元素就是要回溯的上一元素？
A：由Q1可知虽然先经过了根节点，但只是路过不访问，先访问的是左孩子。所以栈里放的是经过但未访问的根节点（祖先结点）。且入栈顺序是从树顶到树根，也就是低优先级到高优先级，所以栈顶元素是最高优先级的根结点（注意：不一定是当前节点的父结点，只是所有经过但未访问中的根节点中具有最高优先级（也即高度最低）的结点）。

Q3：为什么结束条件？
A：因为栈非空代表当前仅在处理左子树，栈里的根节点和右子树还未访问；遍历指针非空是当前手头处理的还没完，这个是比较好想到的循环终止条件。

一个思考：
代码聚焦过程是NL的先后顺序，至于右子树的遍历仍可理解为递归，只不过递归函数是对NL的处理过程（相当于只处理NL，遇到R也当成新的NL，这样总能遍历完）。
————此适用于中序、前序遍历