问答题
给出中序线索树的结点结构并画出一个具有头结点的中序线索树，使其树结点至少应有6个。写一算法在不使用栈和递归的情况下前序遍历一中序线索树，并分析其时间复杂性。【东南大学1993三(20分)1997三(1 8分)1998六(14分)】【东北大学2003三(20分)】
【正确答案】正确答案：带头结点的中序线索树，其头结点的lchild指向二叉树的根结点，头结点的rchild域指向中序遍历的最后一个结点。而二叉树按中序遍历的第一个结点的lchild和最后一个结点的rchild指向头结点。故从头结点找到根结点后，顺“后继”访问二叉树。在中序线索树中，找前序的后继，已在第78题进行了详细的讨论，这里不再赘述。
【答案解析】