morris遍历

程序1:morris遍历

#include<iostream>  //morris遍历
using namespace std;
#include<string>
#include<typeinfo>
#include<deque>
#include<algorithm>
#include<stack>

struct Node
{
    int value;
    Node* left;
    Node* right;
    Node(int val)
    {
        value = val;
    }
};

void morrisPre(Node* head)   //先序遍历
{
    if(head==nullptr)
    {
        return;
    }
    Node* cur = head;
    Node* mostright = nullptr;
    while(cur!=nullptr)
    {
        mostright = cur->left;
        if(mostright!=nullptr)
        {
            while(mostright->right!=nullptr&&mostright->right!=cur)
            {
                mostright = mostright->right;
            }
            if(mostright->right==nullptr)  // 左子树的最右节点的右孩子指向空,表明第一次来到该节点,所以打印
            {
                mostright->right=cur;
                cout<<cur->value<<endl;
                cur = cur->left;
                continue;
            }
            else
            {
                mostright->right=nullptr;
            }    
        }
        else
        {
            cout<<cur->value<<endl;
        } 
        cur = cur->right;
    }
}

void morrisIn(Node* head)  //中序遍历
{
    if(head==nullptr)
    {
        return;
    }
    Node* cur = head;
    Node* mostright = nullptr;
    while(cur!=nullptr)
    {
        mostright = cur->left;
        if(mostright!=nullptr)
        {
            while(mostright->right!=nullptr&&mostright->right!=cur)
            {
                mostright = mostright->right;
            }
            if(mostright->right==nullptr)
            {
                mostright->right=cur;
                cur = cur->left;
                continue;
            }
            else
            {
                mostright->right=nullptr;
            }    
        }
        cout<<cur->value<<endl;  //打印放在最后一次来到这个节点的时机
        cur = cur->right;
    }
}

void printEdge(Node* head)
{

}
void morrisPos(Node* head)  //后序遍历
{
    if(head==nullptr)
    {
        return;
    }
    Node* cur = head;
    Node* mostright = nullptr;
    while(cur!=nullptr)
    {
        mostright = cur->left;
        if(mostright!=nullptr)
        {
            while(mostright->right!=nullptr&&mostright->right!=cur)
            {
                mostright = mostright->right;
            }
            if(mostright->right==nullptr)
            {
                mostright->right=cur;
                cur = cur->left;
                continue;
            }
            else
            {
                mostright->right=nullptr;
                printEdge(cur->left);
            }    
        }
        cur = cur->right;
    }
    printEdge(head);
}

void morris(Node* head)
{
    if(head==nullptr)
    {
        return;
    }
    Node* cur = head;
    Node* mostright = nullptr;
    while(cur!=nullptr)
    {
        mostright = cur->left;
        if(mostright!=nullptr)
        {
            while(mostright->right!=nullptr&&mostright->right!=cur)
            {
                mostright = mostright->right;
            }
            if(mostright->right==nullptr)
            {
                mostright->right=cur;
                cur = cur->left;
                continue;
            }
            else
            {
                mostright->right=nullptr;
            }    
        }
        cur = cur->right;
    }
}

int main()
{
    Node* head;
    head=new Node(1);
    head->left=new Node(2);
    head->right=new Node(3);
    head->left->left = new Node(5);
    morrisPre(head);
    morrisIn(head);
    morrisPos(head);

    return 0;
}