当前位置:首页 » 《资源分享》 » 正文

二叉树遍历高级算法之Morris---莫里斯算法_m0_53157173的博客

9 人参与  2021年05月07日 16:23  分类 : 《资源分享》  评论

点击全文阅读


莫里斯算法与线索二叉树有异曲同工之妙,建议先了解线索二叉树,再来学习


Morris算法

  • 莫里斯算法思想
    • 前序遍历
    • 中序遍历
    • 后序遍历


莫里斯算法思想

  • mirror遍历用到了线索二叉树的思想,在Morris方法中不需要为每个节点额外分配指针指向其前(predecessor)和后继节点(successor),只需要利用叶子节点中的左右空指针指向某种顺序遍历下的前驱节点或后继节点就可以了 。
    在这里插入图片描述
    Morris的整体思路就是将 以某个根结点开始,找到它左子树的最右侧节点之后与这个根结点进行连接
    我们可以从 图2 看到,如果这么连接之后,cur 这个指针是可以完整的从一个节点顺着下一个节点遍历,将整棵树遍历完毕,直到 7 这个节点右侧没有指向。
    代码整体模板演示:
  • 如果可以建议大家反复对照上图与代码,和我给出关于自己的详细思考,好好想想。
  • 我尽可能做到对每条代码都做出详细解释
class Solution {
public: 
    void preOrderMorris(TreeNode* root) {
        if (root == NULL)
            return;
        TreeNode* curr = root;  // 当前的结点
        TreeNode* currLeft = NULL;  // 当前结点的左子树
        while (curr != NULL) 
        {
            currLeft = curr->left;
            // 当前结点的左子树存在即可建立连接
            if (currLeft != NULL) 
            {
                // 找到当前左子树的最右侧节点,并且不能沿着连接返回上层
                while (currLeft->right != NULL && currLeft->right != curr)
                    currLeft = currLeft->right;
                //最右侧节点的右指针没有指向根结点,创建连接并往下一个左子树的根结点进行连接操作
                if (currLeft->right == NULL) 
                {
                    currLeft->right = curr;
                    curr = curr.left;
                    continue;  // 这个continue很关键
                } 
                else 
                //当左子树的最右侧节点有指向根结点,此时说明我们已经进入到了返回上层的阶段,不再是一开始的建立连接阶段,同时在回到根结点时我们应已处理完下层节点,直接断开连接即可。
                    currLeft->right = NULL;
            } 
            // 返回上层的阶段不断向右走
            curr = curr.right;
        }
    }
}
  • 上面的代码和解释可能看完后依旧糊涂,没关系,下面我通过图来演示cur1和cur2指针移动的过程:
    在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

  • 到此为止,左子树部分就已经处理完毕了,下面右子树

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

总结:

  • 连接过程:先连接后左移
  • 复原过程:先右移后斩断,若斩断位置到位,立刻执行斩断,如果位置不到位,通过while循环到达指定位置

前序遍历

  • Morris建立连接时是给每个根结点寻找其左子树的最右侧结点建立连接,因此“从根结点开始”这一特性很符合前序遍历“中左右”的遍历方式,因此在给结点建立连接的同时输出此根结点即可完成前序遍历。

特殊处理:

  • 建立连接的同时输出此根结点
  • 到达一些没有子节点的叶子节点直接输出并向右走返回上层或向此节点的右子树前进
  • 判断出某节点已有连接,则不用输出,直接断开走过的连接后继续向右走
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (root == NULL)
            return ans;
        TreeNode* cur1 = root;  // 当前的结点
        TreeNode* cur2 = NULL;  // 当前结点的左子树
        while (cur1 != NULL)
        {
            cur2 = cur1->left;
            // 当前结点的左子树存在即可建立连接
            if (cur2 != NULL)
            {
                // 找到当前左子树的最右侧节点,并且不能沿着连接返回上层
                while (cur2->right != NULL && cur2->right != cur1)
                    cur2 = cur2->right;
                //最右侧节点的右指针没有指向根结点,创建连接并往下一个左子树的根结点进行连接操作
                if (cur2->right == NULL)
                {
                    cur2->right = cur1;
                    ans.push_back(cur1->val);
                    cur1 = cur1->left;
                    continue;  // 这个continue很关键
                }
                else
                    // 当左子树的最右侧节点有指向根结点,此时说明我们已经进入到了返回上层的阶段,不再是一开始的建立连接阶段,同时在回到根结点时我们应已输出过下层节点,直接断开连接即可
                    cur2->right = NULL;
            }
            else
                // 当前节点的左子树为空,说明左侧到头,直接输出
                ans.push_back(cur1->val);
            // 返回上层的阶段不断向右走
            cur1 = cur1->right;
        }
        return ans;
    }
};

在这里插入图片描述

中序遍历

思路:
类似迭代,整个二叉树中输出的第一个节点是最左侧结点因此在建立连接的时候是不能够直接输出的,必须在建立连接阶段完成,到达最左侧结点之后返回上层的阶段,才能开始输出,此时正好符合“左中右”的遍历方式。
特殊处理:

  • 在建立连接阶段并不输出结点。
  • 在找到最左侧结点(即根结点的左子树为空)时,开始向右走返回上层并同时输出当前结点。
  • 对右子树也进行同样的处理。
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (root == NULL)
            return ans;
        TreeNode* cur1 = root;  // 当前的结点
        TreeNode* cur2 = NULL;  // 当前结点的左子树
        while (cur1 != NULL)
        {
            cur2 = cur1->left;
            // 当前结点的左子树存在即可建立连接
            if (cur2 != NULL)
            {
                // 找到当前左子树的最右侧节点,并且不能沿着连接返回上层
                while (cur2->right != NULL && cur2->right != cur1)
                    cur2 = cur2->right;
                //最右侧节点的右指针没有指向根结点,创建连接并往下一个左子树的根结点进行连接操作
                if (cur2->right == NULL)
                {
                    cur2->right = cur1;
                    cur1 = cur1->left;
                    continue;  // 这个continue很关键
                }
                else
                    // 当左子树的最右侧节点有指向根结点,此时说明我们已经进入到了返回上层的阶段,不再是一开始的建立连接阶段,同时在回到根结点时我们应已输出过下层节点,直接断开连接即可
                    cur2->right = NULL;
            }
                // 当前节点的左子树为空,说明左侧到头,直接输出
                ans.push_back(cur1->val);
            // 返回上层的阶段不断向右走
            cur1 = cur1->right;
        }
        return ans;
    }
};

在这里插入图片描述

后序遍历

思路:
后序遍历又双叒叕是最难搞的情况。举个例子:
在这里插入图片描述

  • 打印顺序:打印 4 打印 5 2 打印 6 打印 7 3 1
  • 我们将一个节点的连续右节点当成一个单链表来看待,可以发现,输出顺序是将此单链表翻转后输出。
  • 当我们返回上层之后,也就是将连线断开的时候,输出下层的单链表。
  • 比如返回到 2,此时打印 4
  • 比如返回到 1,此时打印 5 2
  • 比如返回到 3,此时打印 6
  • 那么我们只需要将这个单链表逆序输出即可。
  • note:这里不应该打印当前层,而是之前的一层,否则根结点会先与右边输出。
class Solution {
public: 
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (root == NULL)
            return ans;
        TreeNode* curr = root;  // 当前的结点
        TreeNode* currLeft = NULL;  // 当前结点的左子树
        while (curr != NULL) {
            currLeft = curr->left;
            // 当前结点的左子树存在即可建立连接
            if (currLeft != NULL) 
            {
                // 找到当前左子树的最右侧节点,并且不能沿着连接返回上层
                while (currLeft->right != NULL && currLeft->right != curr)
                    currLeft = currLeft->right;
                //最右侧节点的右指针没有指向根结点,创建连接并往下一个左子树的根结点进行连接操作
                if (currLeft->right == NULL) 
                {
                    currLeft->right = curr;
                    curr = curr->left;
                    continue;  // 这个continue很关键
                } 
                // 当左子树的最右侧节点有指向根结点,此时说明我们已经进入到了返回上层的阶段,断开连接同时对之前的一层进行翻转并输出
                else 
                {
                    currLeft->right = NULL;
                    postMorrisPrint(curr->left, ans);
                }
                    
            }
            // 返回上层的阶段不断向右走
            curr = curr->right;
        }
        // 最后一轮循环结束时,从root结点引申的右结点单链表并没有输出,这里补上
        postMorrisPrint(root, ans);
        return ans;
    }
    //输出函数
    void postMorrisPrint(TreeNode* head, vector<int>& ans) {
        TreeNode* newhead = postMorrisReverseList(head);  // newhead为翻转后的新头部
        TreeNode* curr = newhead;
        while (curr != NULL) 
        {
            ans.push_back(curr->val);
            curr = curr->right;
        }
        postMorrisReverseList(newhead);  // 遍历结束后再次翻转恢复原链表
    }
    //翻转单链表函数
    TreeNode* postMorrisReverseList(TreeNode* head) {
        TreeNode* curr = head;
        TreeNode* pre = NULL;  // 哨兵结点
        while (curr != NULL) 
        {
            TreeNode* next = curr->right;
            curr->right = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
}

在这里插入图片描述


点击全文阅读


本文链接:http://zhangshiyu.com/post/18550.html

子树  结点  节点  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • (此去经年无故人)南初陆南城:结局+番外精品选集起点章节+阅读即将发布预订
  • 沈凝夏叶晚怡附加完整在线阅读(归雁不栖故人枝)最近更新列表
  • 剧情人物是时初,白浩雄的玄幻言情小说《召诸神,踏万界,天命帝女逆乾坤》,由网络作家&ldquo;海鸥&rdquo;所著,情节扣人心弦,本站TXT全本,欢迎阅读!本书共计381345字,185章节,:结局+番外免费品鉴:结局+番外评价五颗星
  • 凤青禾,江明远,***枢小说(别人修仙我捡漏,卷王们破防了)最近更新(凤青禾,江明远,***枢)整本无套路阅读
  • 薛梨小说无删减+后续(曾经亲情似草芥)畅享阅读
  • 沈南栀小说(穿越时空,我要修补时空裂缝)章节目录+起点章节(沈南栀)全篇清爽版在线
  • 未婚妻被巨蟒缠身,我该吃就吃该喝就喝前言+后续_阿豪林月周然后续+番外_小说后续在线阅读_无删减免费完结_
  • 陆骁,陆本初小说(陆骁,陆本初)(癫!睁眼穿成老太太挥鞭***逆子)前传+阅读全新作品预订
  • 姐姐含冤而死后冥王另娶,我杀穿整个地府在线阅读_阎罗殿殷红别提一口气完结_小说后续在线阅读_无删减免费完结_
  • (书荒必看)毒后重生:疯王的神医小娇妻沈清歌,萧绝:+后续热血十足
  • 重生后我和太监联手灭了敌国喻辰,林雪续集(重生后我和太监联手灭了敌国)终极反转(喻辰,林雪)全篇一口气阅读
  • 我不做灵媒后,自称灵媒摆渡人的养妹害怕了内容精选_苏晓霍老阿姐无广告_小说后续在线阅读_无删减免费完结_

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1