投稿
  1. 极客之音首页
  2. 后端笔记

Morris前序、中序、后序遍历

Java光头强 • • 后端笔记 • 阅读 200

导读：本篇文章讲解 Morris前序、中序、后序遍历，希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com

Morris前序遍历

算法过程

1.如果cur无左孩子，cur向右移动（cur=cur.right）
2.如果cur有左孩子，找到cur左子树上最右的节点，记为mostright

1.如果mostright的right指针指向空，让其指向cur，cur向左移动（cur=cur.left）
2.如果mostright的right指针指向cur，让其指向空，cur向右移动（cur=cur.right）

代码

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

struct TreeNode
{
    int val=0;
    TreeNode *left=NULL;
    TreeNode *right=NULL;
};

void createTreeNode(TreeNode *root,int Num) {
    queue<TreeNode *> Q;
    Q.push(root);
    int data=1;
    while(data<Num){
        TreeNode *curr_node =Q.front();
        Q.pop();
        curr_node->left=new TreeNode;
        curr_node->left->val=data++;
        Q.push(curr_node->left);

        curr_node->right=new TreeNode;
        curr_node->right->val=data++;
        Q.push(curr_node->right);
    }
}

// 所有的代码都需要写在 Algo 类内，自行定义其他需要的变量或函数
class Algo
{
public:
    Algo()
    {
        cout << "algo ok" << endl;
    }

void morrisPos(TreeNode*head)//后序遍历
    {
        if (head == NULL)
            return;
        TreeNode *cur = head;
        TreeNode *pre = NULL;
        while (cur != NULL)
        {
            pre = cur->left;
            if (pre != NULL)
            {
                while (pre->right != NULL && pre->right != cur)
                    pre = pre->right;//左子树的最右结点
                if (pre->right == NULL)//第一次到达左子树的最右子树
                {
                    pre->right = cur;
                    cur = cur->left;
                    continue;
                }
                else    //第二次到达左子树的最右子树 pre->right == cur
                {
                    pre->right = NULL;
                    prnode(cur->left);//逆序打印左子树的右边界
                }
            }
            cur = cur->right;
        }
        prnode(head);
        cout<<endl;
    }

    void  prnode(TreeNode *head)//逆序打印左孩子的右边界
    {
        TreeNode *tail=renode(head);
        while(tail!=NULL){
            cout<<tail->val<<" ";
            tail=tail->right;
        }
        renode(tail);
    }

    TreeNode*renode(TreeNode*head)//右孩子指向上一个节点
    {
        TreeNode*pre=NULL;
        TreeNode*next =NULL;
        while (head != NULL)
        {
        next = head->right;
        head->right = pre;
        pre = head;
        head = next;
    }
    return pre;
    }

    int run(TreeNode *head)
    {
        //在此写入你的代码
        preorderTree(head); //普通前序遍历方法示例
        class Solution{
public:
    vector<int> preorderTraversal(TreeNode* root){
        vector<int> res;
        if(root==nullptr)
        return res;
        TreeNode* cur=root, *pre=nullptr;
        while(cur!=nullptr){
            if(cur->left==nullptr){//当前节点左子树为空则遍历右子树
                res.push_back(cur->val);
                cur=cur->right;
            }//当到达最左节点时，也是用此回退。
            else{
                pre=cur->left;//前驱节点
                while(pre->right!=nullptr && pre->right!=cur){
                    pre=pre->right;
                }//找到前驱节点的最右节点
                if(pre->right==nullptr){
                    pre->right=cur;
                    res.push_back(cur->val);
                    cur=cur->left;
                }//遍历左节点
                if(pre->right==cur){
                    pre->right=nullptr;
                    cur=cur->right;
                }//遍历右节点
            }
        }
        return res;
    }
};

        return 0; //修改为返回正确的结果
    }
    void preorderTree(TreeNode *Node)
    {
        if (Node != NULL)
        {
            cout << Node->val << endl;
            preorderTree(Node->left);
            preorderTree(Node->right);
        }
    }
};
int main()
{
    Algo algo;
    TreeNode head;
    createTreeNode(&head,10);    // 10为生成的二叉树结点的数量，根据需要自行调整
    time_t start = clock();
    algo.run(&head);
    time_t end = clock();
    cout << "程序耗时: " << double(end - start) / CLOCKS_PER_SEC << " ms" << endl;
    cout << "占用内存：" << sizeof(algo) << " byte" << endl;
    return 0;
}

Morris中序遍历

算法过程

中序遍历和前序遍历基本相同，就是输出的值的位置有点不同

代码

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

struct TreeNode
{
    int val=0;
    TreeNode *left=NULL;
    TreeNode *right=NULL;
};

void createTreeNode(TreeNode *root,int Num) {
    queue<TreeNode *> Q;
    Q.push(root);
    int data=1;
    while(data<Num){
        TreeNode *curr_node =Q.front();
        Q.pop();
        curr_node->left=new TreeNode;
        curr_node->left->val=data++;
        Q.push(curr_node->left);

        curr_node->right=new TreeNode;
        curr_node->right->val=data++;
        Q.push(curr_node->right);
    }
}

// 所有的代码都需要写在 Algo 类内，自行定义其他需要的变量或函数
class Algo
{
public:
    Algo()
    {
        cout << "algo ok" << endl;
    }

void morrisIn(TreeNode *head)
    {
        if (head == NULL)
            return;
        TreeNode *cur = head;
        TreeNode *pre = NULL;
        while (cur != NULL)
        {
            pre = cur->left;
            if (pre != NULL)
            {
                while (pre->right != NULL && pre->right != cur)
                    pre = pre->right;//左子树的最右结点
                if (pre->right == NULL)
                {
                    pre->right = cur;
                    cur = cur->left;
                    continue;
                }
                else
                {
                    pre->right = NULL;
                }
            }
            cout << cur->val << " ";
            cur = cur->right;
        }
        cout << endl;
    }

    int run(TreeNode *head)
    {
        //在此写入你的代码
        preorderTree(head); //普通前序遍历方法示例
        morrisIn(head);
        return 0; //修改为返回正确的结果
    }
    void preorderTree(TreeNode *Node)
    {
        if (Node != NULL)
        {
            cout << Node->val << endl;
            preorderTree(Node->left);
            preorderTree(Node->right);
        }
    }
};

int main()
{
    Algo algo;
    TreeNode head;
    createTreeNode(&head,10);    // 10为生成的二叉树结点的数量，根据需要自行调整
    time_t start = clock();
    algo.run(&head);
    time_t end = clock();
    cout << "程序耗时: " << double(end - start) / CLOCKS_PER_SEC << " ms" << endl;
    cout << "占用内存：" << sizeof(algo) << " byte" << endl;
    return 0;
}

结果

在这里插入图片描述

Morris后序遍历

算法过程

后序遍历的顺序是左右中，想通过之前这样一个一个直接有cur指针遍历过去可不行了，但可以通过回退倒上一层把下一个左节点的右边节点一次全遍历过去再将结果翻转，因为回退到上一层节点意味着你这一层已经走过了一遍了。

代码

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

struct TreeNode
{
    int val=0;
    TreeNode *left=NULL;
    TreeNode *right=NULL;
};

void createTreeNode(TreeNode *root,int Num) {
    queue<TreeNode *> Q;
    Q.push(root);
    int data=1;
    while(data<Num){
        TreeNode *curr_node =Q.front();
        Q.pop();
        curr_node->left=new TreeNode;
        curr_node->left->val=data++;
        Q.push(curr_node->left);

        curr_node->right=new TreeNode;
        curr_node->right->val=data++;
        Q.push(curr_node->right);
    }
}

// 所有的代码都需要写在 Algo 类内，自行定义其他需要的变量或函数
class Algo
{
public:
    Algo()
    {
        cout << "algo ok" << endl;
    }

void morrisPos(TreeNode*head)//后序遍历
    {
        if (head == NULL)
            return;
        TreeNode *cur = head;
        TreeNode *pre = NULL;
        while (cur != NULL)
        {
            pre = cur->left;
            if (pre != NULL)
            {
                while (pre->right != NULL && pre->right != cur)
                    pre = pre->right;//左子树的最右结点
                if (pre->right == NULL)//第一次到达左子树的最右子树
                {
                    pre->right = cur;
                    cur = cur->left;
                    continue;
                }
                else    //第二次到达左子树的最右子树 pre->right == cur
                {
                    pre->right = NULL;
                    prnode(cur->left);//逆序打印左子树的右边界
                }
            }
            cur = cur->right;
        }
        prnode(head);
        cout<<endl;
    }

    void  prnode(TreeNode *head)//逆序打印左孩子的右边界
    {
        TreeNode *tail=renode(head);
        while(tail!=NULL){
            cout<<tail->val<<" ";
            tail=tail->right;
        }
        renode(tail);
    }

    TreeNode*renode(TreeNode*head)//右孩子指向上一个节点
    {
        TreeNode*pre=NULL;
        TreeNode*next =NULL;
        while (head != NULL)
        {
        next = head->right;
        head->right = pre;
        pre = head;
        head = next;
    }
    return pre;
    }

    int run(TreeNode *head)
    {
        //在此写入你的代码
         //普通前序遍历方法示例
        morrisPos(head);
        return 0; //修改为返回正确的结果
    }
    void preorderTree(TreeNode *Node)
    {
        if (Node != NULL)
        {
            cout << Node->val << endl;
            preorderTree(Node->left);
            preorderTree(Node->right);
        }
    }
};

int main()
{
    Algo algo;
    TreeNode head;
    createTreeNode(&head,10);    // 10为生成的二叉树结点的数量，根据需要自行调整
    time_t start = clock();
    algo.run(&head);
    time_t end = clock();
    cout << "程序耗时: " << double(end - start) / CLOCKS_PER_SEC << " ms" << endl;
    cout << "占用内存：" << sizeof(algo) << " byte" << endl;
    return 0;
}

结果

在这里插入图片描述

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/115404.html

赞 (0)
Java光头强的头像Java光头强
0 0

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！