EA4-Morris遍历¶

以下是 Morris 遍历 的核心 C 语言实现（前序和中序），它是一种 O(1) 空间复杂度 的二叉树遍历方法，不使用递归也不使用栈，通过临时修改树的空指针（线索化） 来实现。

✅ Morris 遍历核心思想¶

利用叶子节点的 null 指针（尤其是右指针）指向其中序后继，形成线索，遍历完成后恢复原结构。

关键角色：当前节点 curr 和它的 前驱（predecessor）

一、Morris 中序遍历（Inorder）¶

C
void morrisInorder(TreeNode* root) {
    TreeNode* curr = root;

    while (curr) {
        // 情况1：没有左子树 → 直接访问并进入右子树
        if (curr->left == NULL) {
            printf("%d ", curr->data);  // 访问根（此时是中序位置）
            curr = curr->right;         // 转向右子树
        }
        // 情况2：有左子树 → 找左子树的最右节点（即中序前驱）
        else {
            TreeNode* predecessor = curr->left;
            // 找到左子树的最右节点（注意：不能等于 curr）
            while (predecessor->right && predecessor->right != curr) {
                predecessor = predecessor->right;
            }

            // 子情况2.1：前驱的右指针为空 → 第一次到达，建立线索
            if (predecessor->right == NULL) {
                predecessor->right = curr;  // 指向当前节点（线索）
                curr = curr->left;          // 继续遍历左子树
            }
            // 子情况2.2：前驱右指针已指向 curr → 第二次到达，拆除线索
            else {
                predecessor->right = NULL;  // 恢复原结构
                printf("%d ", curr->data);  // 访问根（中序位置）
                curr = curr->right;         // 遍历右子树
            }
        }
    }
}

二、Morris 前序遍历（Preorder）¶

与中序几乎相同，仅在 第一次建立线索时访问根节点

C
void morrisPreorder(TreeNode* root) {
    TreeNode* curr = root;

    while (curr) {
        if (curr->left == NULL) {
            printf("%d ", curr->data);  // 无左子树，直接访问
            curr = curr->right;
        } else {
            TreeNode* predecessor = curr->left;
            while (predecessor->right && predecessor->right != curr) {
                predecessor = predecessor->right;
            }

            if (predecessor->right == NULL) {
                predecessor->right = curr;
                printf("%d ", curr->data);  // ✅ 第一次到此，前序访问根
                curr = curr->left;
            } else {
                predecessor->right = NULL;  // 恢复
                curr = curr->right;         // 不再访问根
            }
        }
    }
}

三、Morris 后序遍历（较复杂，非常少见）¶

通常不推荐手写。可通过反转路径方式实现，此处略过。

🔍 难点与记忆技巧¶

难点	讲解与记忆方法
1. 为什么要修改指针？	利用空指针“借道”返回父节点，避免用栈记录路径。遍历完立即恢复，不影响原树。
2. 什么是前驱（predecessor）？	在中序序列中，`curr` 的前一个是其左子树的最右节点。记住：“左子树的最右” = 中序前驱。
3. 如何判断是第一次还是第二次？	通过 `predecessor->right == NULL` 表示第一次（建线索），`== curr` 表示第二次（拆线索）。这是 Morris 的“握手标志”。
4. 前序 vs 中序的访问时机？	前序：在 `predecessor->right == NULL` 时访问（第一次）中序：在 `predecessor->right == curr` 时访问（第二次） ✅ 记忆口诀：“前序早访问，中序晚访问”
5. 为什么只改右指针？	因为左子树遍历完要返回根，所以用 `right` 指向根。这正是“线索二叉树”的思想。

📌 Morris 遍历特点总结¶

项目	说明
时间复杂度	O(n) — 每条边最多走两次
空间复杂度	O(1) — 无栈无递归
是否修改树？	是（临时），但最终恢复
适用场景	嵌入式、内存受限环境；面试高频考点
缺点	代码较难理解；并发环境下不安全（修改了结构）

✅ 记忆口诀（背下来）¶

“有左找前驱，无左直输出；
空则建线索，回则拆并访；
前序早访问，中序晚一步。”

✅ 总结：Morris 遍历是算法设计的精妙体现 —— 用时间换空间，用线索化替代栈。掌握前序和中序即可，重点理解“两次访问 + 线索建立与拆除”机制。