如何在Morris中序遍历进行时实现二叉搜索查找？

Morris中序遍历是二叉搜索树的一种中序遍历方法，仅使用*O(1)*内存（无需递归），但会临时修改（后续恢复）树的部分->right指针。

示例C代码：

#include <stdio.h>  /* printf(). */
#include <stdlib.h>  /* NULL. */
struct node {
    struct node *left, *right;
    int data;
};
void traverse(struct node *root) {
    struct node *current = root;
    struct node *pre;
    while (current != NULL) { 
        if (current->left == NULL) goto process_node;
        /* 找到current的中序前驱节点 */
        pre = current->left;
        while (pre->right != NULL && pre->right != current) {
            pre = pre->right;
        }
        if (pre->right == NULL) {
            /* 将current设为其中序前驱的右子节点 */
            pre->right = current;  /* 临时修改树结构 */
            current = current->left;
        } else {
            /* 恢复之前修改的指针，还原树结构 */
            pre->right = NULL;
          process_node:
            printf("%d ", current->data);
            /* find(root, current->data + 2); */
            /* find(root, current->data - 2); */
            current = current->right;
        }
    }
}

但由于这种临时修改，额外的二叉树值查找无法正常工作。比如取消上述代码中find(...)调用的注释后，下面的普通find实现会在遍历期间陷入无限循环：

int datacmp(int a, int b) {  /* 升序规则：返回-1表示a < b */
    return a < b ? -1 : a > b;
}

struct node *find(struct node *root, int data) {
    struct node *explore = root;
    int c;
    while (explore != NULL) {
        c = datacmp(data, explore->data);
        if (c == 0) {
            return explore;
        } else if (c < 0) {
            explore = explore->left;
        } else {
            explore = explore->right;
        }
    }
    return NULL;
}

请问是否存在可在Morris中序遍历进行时正常工作的find实现？

当然存在可行的find实现，核心思路是在查找过程中识别出Morris遍历创建的临时right指针，避免陷入循环。

方法1：修改find函数，检测临时指针 #

由于Morris遍历中，临时right指针总是指向某个祖先节点（当前节点的后继），我们可以在查找时跟踪路径，避免回到已经访问过的祖先节点：

struct node *find_morris_safe(struct node *root, int data) {
    struct node *explore = root;
    struct node *prev = NULL;
    int c;
    while (explore != NULL) {
        // 检测是否是临时指针：当前节点的右指针指向祖先，且不是正常的BST右子树
        if (explore->right == prev) {
            // 遇到了Morris临时指针，直接终止这条路径的查找
            break;
        }
        c = datacmp(data, explore->data);
        if (c == 0) {
            return explore;
        } else if (c < 0) {
            prev = explore;
            explore = explore->left;
        } else {
            prev = explore;
            explore = explore->right;
        }
    }
    return NULL;
}

这个实现通过记录上一个访问的节点prev，如果当前节点的right指针指向prev，说明这是Morris遍历创建的临时指针，此时这条路径不存在目标值，直接退出循环。

方法2：遍历期间维护树的状态标记 #

如果可以修改节点结构，我们可以给每个节点添加一个标记位，标识当前right指针是否是临时修改的：

struct node {
    struct node *left, *right;
    int data;
    int is_temp_right; // 1表示right是临时指针，0表示原始指针
};

然后在Morris遍历的修改和恢复步骤中更新这个标记：

// 修改临时指针时
pre->right = current;
pre->is_temp_right = 1;

// 恢复时
pre->right = NULL;
pre->is_temp_right = 0;

对应的find函数就可以根据这个标记跳过临时指针：

struct node *find_morris_safe(struct node *root, int data) {
    struct node *explore = root;
    int c;
    while (explore != NULL) {
        c = datacmp(data, explore->data);
        if (c == 0) {
            return explore;
        } else if (c < 0) {
            explore = explore->left;
        } else {
            // 如果是临时指针，说明这条路径没有目标值
            if (explore->is_temp_right) {
                break;
            }
            explore = explore->right;
        }
    }
    return NULL;
}

方法3：遍历期间延迟查找操作 #

另一种思路是把需要执行的查找操作缓存起来，等Morris遍历完成、树结构完全恢复后再批量执行。这种方法不需要修改find函数，但会牺牲实时性：

// 定义缓存结构体
#define MAX_QUERIES 100
struct query {
    int data;
    struct node **result;
};
struct query query_cache[MAX_QUERIES];
int query_count = 0;

// 修改traverse函数，缓存查询
void traverse(struct node *root) {
    struct node *current = root;
    struct node *pre;
    while (current != NULL) { 
        if (current->left == NULL) goto process_node;
        pre = current->left;
        while (pre->right != NULL && pre->right != current) {
            pre = pre->right;
        }
        if (pre->right == NULL) {
            pre->right = current;
            current = current->left;
        } else {
            pre->right = NULL;
          process_node:
            printf("%d ", current->data);
            // 缓存查询，而不是立即执行
            if (query_count < MAX_QUERIES) {
                query_cache[query_count].data = current->data + 2;
                query_cache[query_count].result = malloc(sizeof(struct node*));
                query_count++;
                query_cache[query_count].data = current->data - 2;
                query_cache[query_count].result = malloc(sizeof(struct node*));
                query_count++;
            }
            current = current->right;
        }
    }
    // 遍历完成后执行所有查询
    for (int i = 0; i < query_count; i++) {
        *query_cache[i].result = find(root, query_cache[i].data);
        // 处理查询结果...
    }
}

这三种方法各有优缺点：方法1不需要修改节点结构，实现简单；方法2逻辑更清晰，但需要修改树的节点定义；方法3完全复用原find函数，但无法实时获取查询结果。

内容的提问来源于stack exchange，提问作者pts