问答题 假设在表示一棵二叉树的二叉链表上增加两个域：双亲域用于指示其双亲结点，标志域flag（可取0，…，2）的值，用以区分在遍历过程中到达该结点时继续向右或向左或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。

问答题 编写对二叉树进行中序遍历的非递归算法，并对算法执行如图所示的二叉树的情况进行跟踪（即给出各阶段栈的变化及输出的结点序列）。 栈已经定义：InitStack（S）（初始化）、Empty（S）（判栈空）、Push（S，p）（入栈）、Pop（S，p）（出栈）等操作。

问答题 己知中序线索二叉树采用二叉链表存储结构，链结点的构造为： 其中若ltag为0，则lchild指向结点的前驱，否则lchild指向左孩子结点；若rtag为0，则rchild指向结点的后继，否则rchild指向右孩子结点。下面的算法返回x所指结点的直接后继结点的位置。若该算法有错，则请改正错误；若无错，请写“正确”二字。