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

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

结点访问过程：

参靠左神代码编写：

#include 
#include 
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 &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()
{
    
    int arr[] = {1, 2, 4, -1, 8, -1, -1, 5, -1, -1, 3, 6, 9, -1, -1, -1, 7, -1, -1};
    queue 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