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

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

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

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

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

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

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

非递归中序遍历算法：

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

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

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

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

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

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

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

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

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