C++如何实现二叉树的Morris前序遍历-C++-PHP中文网

morris前序遍历的核心逻辑是：在首次抵达节点时立即访问，且访问必须发生在建立左子树线索之后、向左移动之前；若无左子树则直接访问并右移；若有左子树，则找其最右节点，为空时建线索并访问当前节点后左移，为当前节点时拆线索后右移。

c++如何实现二叉树的morris前序遍历

Morris前序遍历的核心逻辑是什么

Morris遍历的本质是用叶子节点的空右指针“临时”指向中序后继，避免递归或栈的空间开销。前序遍历的关键在于：**在建立线索时立即访问节点，而不是等到回溯时**。这和中序遍历不同——中序是在左子树为空或线索被拆除后才访问；前序则必须在首次到达某节点、且准备向左走之前就输出它。

容易踩的坑：root->right 被复用作线索指针，所以一旦修改了它的指向，就不能再靠 root->right == nullptr 判断是否为叶子；必须严格按「当前节点是否有左子树」来分支。

如何写出不漏节点、不重复访问的代码

标准实现需要两个关键判断点：一是当前节点无左子树，直接访问并跳向右子节点；二是有左子树，则找其「最右节点」（即左子树的中序最后一个节点），并据此决定建线索还是拆线索。

实操建议：

找前驱节点时，用 pred = cur->left 后循环 while (pred->right && pred->right != cur)，确保不陷入已建好的线索环
当 pred->right == nullptr：说明第一次到 cur，此时访问 cur，然后建线索 pred->right = cur，再 cur = cur->left
当 pred->right == cur：说明左子树已处理完，此时要恢复树结构（pred->right = nullptr），然后向右走（cur = cur->right）——注意：这里不再访问 cur，因为前序已在第一次到达时访问过了

C++实现中要注意的指针细节

原生指针操作稍有不慎就会导致段错误或无限循环。尤其注意三类边界：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

cur 为 nullptr 时必须跳出循环，否则 cur->left 访问非法
找前驱过程中，pred->right 可能为 nullptr 或 cur，但绝不能是其他值；若误判会漏访问或重复访问
恢复线索时只清 pred->right，不要动 cur->right——后者可能是真实右子树，也可能是上层建的线索，但都不是当前该处理的对象

一个最小可运行片段：

void morrisPreorder(TreeNode* root) {
    TreeNode* cur = root;
    while (cur) {
        if (!cur->left) {
            cout val right;
        } else {
            TreeNode* pred = cur->left;
            while (pred->right && pred->right != cur) pred = pred->right;
            if (!pred->right) {
                cout val right = cur;
                cur = cur->left;
            } else {
                pred->right = nullptr;
                cur = cur->right;
            }
        }
    }
}