【C++ Morris算法遍历二叉树】

Morris遍历二叉树：

指针建立：左子树最右结点指向当前结点，第二次访问该结点时还原，指向null

结点访问过程：

Morris算法流程：

1.如果当前结点没有左树，则当前结点右移，如果也没有右树，则右移后当前结点为空，直接退出

2.当前结点有左树时，遍历到左树的最右结点.

2.1 如果是第一次来到左子树最右结点，则将其右指针指向cur结点，cur左移（一次性将左子树上的回溯指针建立好）

2.2 如果第二次来到左子树最右结点，则将指针还原为空。cur右移（该左树已访问完成，继续到右树上遍历）

---

代码：

参靠左神代码编写：

#include <iostream>
#include <queue>
using namespace std;

struct Node
{
    int value;
    Node *left;
    Node *right;
    Node() : value(0), left(nullptr), right(nullptr) {}
    Node(int a) : value(a), left(nullptr), right(nullptr) {}
    Node(int a, Node *p1, Node *p2) : value(a), left(p1), right(p2) {}
};

//初始化二叉树
Node *Initial_Tree(queue<int> &qu)
{
    int data = qu.front();
    qu.pop();
    if (data == -1)
    {
        return nullptr;
    }
    Node *head = new Node(data);
    head->left = Initial_Tree(qu);
    head->right = Initial_Tree(qu);
    return head;
}

//先序遍历
void morris_pre(Node *head)
{
    if (head == nullptr)
    {
        return;
    }
    Node *cur = head;           //当前结点
    Node *most_right = nullptr; //左子树最右结点
    while (cur != nullptr)
    {
        most_right = cur->left;
        if (most_right != nullptr) //有左子树
        {
            while (most_right->right != nullptr && most_right->right != cur) //遍历至左子树上的最右结点
            {
                most_right = most_right->right;
            }
            if (most_right->right == nullptr) //左子树上的最右结点指向空(第一次来到此节点)
            {
                most_right->right = cur;
                cout << cur->value << " ";
                cur = cur->left;
                continue;
            }
            else //左子树上最右结点指向当前结点
            {
                most_right->right = nullptr; //第二次到达此节点后还原左子树最右结点的右指针
            }
        }
        else
        {
            cout << cur->value << " ";
        }
        cur = cur->right;
    }
    cout << endl;
}

//中序遍历
void morris_inorder(Node *head)
{
    if (head == nullptr)
    {
        return;
    }
    Node *cur = head;
    Node *most_right = nullptr;

    while (cur != nullptr)
    {
        most_right = cur->left;
        if (most_right != nullptr) //有左子树
        {
            while (most_right->right != nullptr && most_right->right != cur)
            {
                most_right = most_right->right;
            }
            if (most_right->right == nullptr)
            {
                most_right->right = cur;
                cur = cur->left;
                continue;
            }
            else // most_right -> right == cur
            {
                most_right->right = nullptr;
            }
        }
        cout << cur->value << " ";
        cur = cur->right;
    }
    cout << endl;
}

Node *reverse_edge(Node *first) //反转链表
{
    Node *pre = nullptr;
    Node *next = nullptr;
    while (first != nullptr)
    {
        next = first->right;
        first->right = pre;
        pre = first;
        first = next;
    }
    return pre; //当前值为空，则pre指向原链表结尾
}

void print_edge(Node *head)
{
    Node *temp = reverse_edge(head);
    Node *cur = temp;
    while (cur != nullptr)
    {
        cout << cur->value << " ";
        cur = cur->right;
    }
    reverse_edge(temp);
}

//后序遍历
void morris_pos(Node *head)
{
    if (head == nullptr)
    {
        return;
    }
    Node *cur = head;
    Node *most_right = nullptr;
    while (cur != nullptr)
    {
        most_right = cur->left;
        if (most_right != nullptr)
        {
            while (most_right->right != nullptr && most_right->right != cur)
            {
                most_right = most_right->right;
            }
            if (most_right->right == nullptr)
            {
                most_right->right = cur;
                cur = cur->left;
                continue;
            }
            else
            {
                most_right->right = nullptr;
                print_edge(cur->left); //逆序打印左树的右边界
            }
        }
        cur = cur->right;
    }
    print_edge(head);
    cout << endl;
}

int main()
{
    /*                  1
                    /       \
                   2         3
                  / \       / \
                 4   5     6   7
                  \       /
                   8     9
    */
    int arr[] = {1, 2, 4, -1, 8, -1, -1, 5, -1, -1, 3, 6, 9, -1, -1, -1, 7, -1, -1};
    queue<int> qu;
    for (int data : arr)
    {
        qu.push(data);
    }
    Node *head = Initial_Tree(qu);
    cout << "先序遍历:" << endl;
    morris_pre(head); //先序遍历
    cout << "中序遍历:" << endl;
    morris_inorder(head); //中序遍历
    cout << "后序遍历:" << endl;
    morris_pos(head); //后序遍历
    return 0;
}

结果：

---

参靠：

Morris 二叉树神级遍历–yindarui
https://blog.csdn.net/qq_38684427/article/details/107708469

---