问答题
已知指针p指向带表头的中根次序线索二又树中的某结点，试写一算法FFAp，q)，该算法寻找结点p的父亲结点g。设线索二叉树的结点结构、表头结点结构和空树结构分别为(LTAGLLINK，INFO，RLINK，RTAG)，且规定线索树的最左下结点的LLNK域和最右下结点的RLINK域指向表头。【吉林大学1999二、1(16分)】
【正确答案】正确答案：在中序线索树中找结点的双亲，最简单情况是结点有左右子女，且左右子女都是叶子。结点的左子女的右线索和右子女的左线索都指向双亲。对于有左右子女且左右子女不是叶子的结点来说，则要利用中序线索树中线索“向上”指向祖先的特点：若结点P是结点q右子树中中序遍历最左下的结点，P的左线索指向q；若结点P是结点q左子树上中序遍历最右下的结点，P的右线索指向是q。反过来，通过祖先找子女就容易了。另外，若结点q的后继是中序线索树的头结点，则应特殊考虑。
【答案解析】