问答题设中序线索二又树的结点由五个域构成：info：给出结点的数据场之值。LL：当LT为1时，则给出该结点的左儿子之地址，当LT为0时，则给出按中序遍历的前驱结点的地址。LT：标志域，为1或为0。RL：当RT为1时，则给出该结点的右儿子的地址；当RT为0时，则给出按中序遍历的后继结点地址。RT：标志域为0或为l。请编写程序，在具有上述结点结构的中序线索二叉树上，求某一结点p的按后序遍历次序的后继结点的地址q，设该中序线索二叉树的根结点地址为r。另外，请注意必须满足：(1)额外空间的使用只能为O(1)，(2)程序为非递归。【上海交通大学2000十(20分)】

【正确答案】正确答案：在中序线索二叉树中，求某结点P的后序后继g，需要知道P的双亲结点f的信息。(中序线索树的性质；若P是f的左子女，DJf是p的最右子孙的右线索；若p是f的右子女，则f是p的最左子孙的左线索。)找到f后，若p是f的右子女，则p的后继是f若p是f的左子女，且f无右子女，则p的后继也是f;若p是f的左子女，且f有右子女，则f的右子树中最左边的叶子结点是p的后继。因此，算法思路是，先找p的双亲f,根据p是f的左／右子女再确定p的后序后继。

【答案解析】