非递归的反向遍历算法

设计在一棵中序线索二叉树中查找中序序列的最后一个结点和任一结点中序前驱结点的算法，并在此基础上设计非递归的中序反向遍历算法。 

1. 查找中序序列的最后一个节点：

• 从根节点开始，一直向右走，直到遇到RTag为线索的节点为止。这个节点就是中序序列的最后一个节点。

2. 查找任一节点的中序前驱节点：

• 若该节点的LTag为指针，则其左子节点为中序前驱节点。
• 若该节点的LTag为线索，则其左指针指向的节点为中序前驱节点。

接下来，基于这两个算法，我们可以设计非递归的中序反向遍历算法。具体步骤如下：

1. 找到中序序列的最后一个节点。可以使用上述步骤1中的算法实现。
2. 从最后一个节点开始，进行反向遍历。

• 在每个节点上，首先输出节点的数据。
• 如果节点的LTag为线索，则向左移动到前驱节点。
• 如果节点的LTag为指针，则将当前节点更新为其左子节点，并继续向右移动到尽头。

下面是非递归的中序反向遍历算法的示例代码：

void InOrderReverseTraversal(BiThrTree Thrt) {
    BiThrTree p = Thrt;
    
    // 找到中序序列的最后一个节点
    while (p->RTag == Link) {
        p = p->rchild;
    }

    // 反向遍历
    while (p != Thrt) {
        printf("%c ", p->data);  // 输出节点数据

        if (p->LTag == Thread) {
            p = p->lchild;  // 移动到前驱节点
        } else {
            p = p->lchild;
            while (p->RTag == Link) {
                p = p->rchild;
            }
        }
    }
}