如何将非递归的反向遍历算法改写成长尾？

本文共计811个文字，预计阅读时间需要4分钟。

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

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

1.从根节点开始，一直向右走，直到到达最右边的叶子节点。

查找任意节点中序前驱节点：

1.从根节点开始，向左走，直到找到第一个左子树不为空的节点，该节点的左子树即为目标节点的中序前驱节点。

非递归中序遍历算法：

1.初始化一个栈和一个指针指向根节点。

2.当栈不为空或指针不为空时，执行以下步骤：

a. 将指针指向的节点入栈，并将指针移动到该节点的左子节点。 b. 重复步骤a，直到指针为空。 c. 将栈顶节点出栈，访问该节点。 d. 将指针设置为该节点的右子节点，回到步骤2。

中序遍历输出：从根节点开始，按照左-根-右的顺序访问每个节点，直到所有节点访问完毕。

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

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; } } } }