• 数据库
  • Mysql
  • Nosql
  • 技术框架
  • Spring
  • Kafka
  • ibatis
  • 分布式
  • Linux
  • 关于我们
  • 注册
  • 登录
  • 欧宝安德拉-二叉树遍历-morris遍历

    2022-5-10 diaba 欧宝安德拉

    package com.jiucaiyuan.net.question;
    
    import com.jiucaiyuan.net.algrithm.tree.Node;
    
    /**
     * 【Morris遍历】
     * 一种遍历二叉树的方式,时间复杂度是O(N),额外空间复杂度是O(1)
     * 通过利用原树中大量空闲指针的方式,达到节省空间的目的
     * 遍历过程中,更改了底层叶子结点指针,完成遍历后,恢复了指针指向
     *
     * @Author jiucaiyuan  2022/5/10 22:45
     * @mail services@jiucaiyuan.net
     */
    public class Morris {
        /**
         * <pre>
         * 【Morris遍历】
         * 一种遍历二叉树的方式
         * 通过利用原树中大量空闲指针的方式,达到节省空间的目的
         * 二叉树的遍历欧宝安德拉
         * 【Morris遍历细节】
         * 假设来到当前节点curr,开始时curr来到头结点位置
         * 1)如果curr没有左孩子,curr向右移动(curr=curr.right)
         * 2)如果curr有左孩子,找到左子树上最右的节点mostRight:
         *      a.如果mostRight右指针指向null,让其指向curr,然后curr向左移动(curr = curr.left)
         *      b.如果mostRight右指针指向curr,让其指向null,然后curr向右移动(curr = curr.right)
         * 3)curr为空时遍历停止
         * 【复杂度分析】
         *      时间复杂度是O(N)
         *      额外空间复杂度是O(1)
         *  节点有左子树,会访问两次,如果没有左子树,只访问一次
         * </pre>
         *
         * @param head
         */
        public static void morris(Node<Integer> head) {
            if (head == null) {
                return;
            }
            Node curr = head;
            Node mostRight = null;
            while (curr != null) {
                System.out.print(curr.value + ",");  //morris 遍历序
                mostRight = curr.left;
                if (mostRight != null) {
                    //最右指向不为空,且指向的不是自己,一直找左子树的最右节点
                    while (mostRight.right != null && mostRight.right != curr) {
                        mostRight = mostRight.right;
                    }
                    //截止到这里,mostRigt找到了左子树的最右侧节点
                    if (mostRight.right == null) { //第一次访问最右侧节点
                        mostRight.right = curr;
                        curr = curr.left;
                        continue;
                    } else {  //否则,右指针一定指向当前节点的(判断是第二次访问当前节点
                        mostRight.right = null;//恢复左子树最右侧节点的默认值
                    }
                }
                curr = curr.right;
            }
        }
    
        /**
         * morris遍历(前序遍历二叉树)
         * 由morris遍历序改成先序遍历,morris遍历时
         * 只访问一次的节点,直接打印
         * 访问两次的节点,第一次打印
         *
         * @param head
         */
        public static void morrisPre(Node head) {
            if (head == null) {
                return;
            }
    
            Node curr = head;
            Node mostRight = null;
            while (curr != null) {
                mostRight = curr.left;
                if (mostRight != null) {
                    while (mostRight.right != null && mostRight.right != curr) {
                        mostRight = mostRight.right;
                    }
                    //截止到这里,mostRigt找到了左子树的最右侧节点
                    if (mostRight.right == null) { //第一次访问最右侧节点
                        System.out.print(curr.value + ",");
                        mostRight.right = curr;
                        curr = curr.left;
                        continue;
                    } else {
                        mostRight.right = null;//恢复左子树最右侧节点的默认值
                    }
                } else {
                    System.out.print(curr.value + ",");
                }
                curr = curr.right;
            }
        }
    
        /**
         * morris遍历(中序遍历二叉树)
         *
         * @param head
         */
        public static void morrisMid(Node head) {
            if (head == null) {
                return;
            }
            Node curr = head;
            Node mostRight = null;
            while (curr != null) {
                mostRight = curr.left;
                if (mostRight != null) {
                    while (mostRight.right != null && mostRight.right != curr) {
                        mostRight = mostRight.right;
                    }
                    //截止到这里,mostRigt找到了左子树的最右侧节点
                    if (mostRight.right == null) { //第一次访问最右侧节点
                        mostRight.right = curr;
                        curr = curr.left;
                        continue;
                    } else {
                        System.out.print(curr.value + ",");
                        mostRight.right = null;//恢复左子树最右侧节点的默认值
                    }
                } else {
                    System.out.print(curr.value + ",");
                }
                curr = curr.right;
            }
        }
    
        /**
         * morris遍历(中序遍历二叉树)
         * 由morris遍历序改成中序遍历,morris遍历时
         * 只访问一次的节点,直接打印
         * 访问两次的节点,第二次打印
         *
         * @param head
         */
        public static void morrisIn(Node head) {
            if (head == null) {
                return;
            }
            Node curr = head;
            Node mostRight = null;
            while (curr != null) {
                mostRight = curr.left;
                if (mostRight != null) {
                    while (mostRight.right != null && mostRight.right != curr) {
                        mostRight = mostRight.right;
                    }
                    //截止到这里,mostRigt找到了左子树的最右侧节点
                    if (mostRight.right == null) { //第一次访问最右侧节点
                        mostRight.right = curr;
                        curr = curr.left;
                        continue;
                    } else {
                        mostRight.right = null;//恢复左子树最右侧节点的默认值
                    }
                }
                System.out.print(curr.value + ",");
                curr = curr.right;
            }
        }
    
        /**
         * morris遍历(后序遍历二叉树)
         * 由morris遍历序改成中序遍历,morris遍历时
         * 只访问一次的节点,不打印
         * 访问两次的节点,第一次访问时,不打印
         * 访问两次的节点,第二次访问时,逆序打印自己左树的右边界
         * 最后再统一逆序打印整棵树的右边界
         *
         * @param head
         */
        public static void morrisPost(Node head) {
            if (head == null) {
                return;
            }
            Node curr = head;
            Node mostRight = null;
            while (curr != null) {
                mostRight = curr.left;
                if (mostRight != null) {
                    while (mostRight.right != null && mostRight.right != curr) {
                        mostRight = mostRight.right;
                    }
                    //截止到这里,mostRigt找到了左子树的最右侧节点
                    if (mostRight.right == null) { //第一次访问最右侧节点
                        mostRight.right = curr;
                        curr = curr.left;
                        continue;
                    } else {
                        mostRight.right = null;//恢复左子树最右侧节点的默认值
                        printEdge(curr.left); //逆序打印自己左树的右边界
                    }
                }
                curr = curr.right;
            }
            printEdge(head); //逆序打印整棵树的右边界
            System.out.println();
        }
    
        /**
         * 逆序打印x为头结点的二叉树右边界
         *
         * @param x
         */
        public static void printEdge(Node<Integer> x) {
            Node<Integer> tail = reverseEdge(x);
            Node<Integer> curr = tail;
            while (curr != null) {
                System.out.println(curr.value + " ");
                curr = curr.right;
            }
            reverseEdge(tail);
        }
    
        /**
         * 把from——>from.right——>from.right.right单链表逆序
         *
         * @param from
         * @return 逆序后的头结点
         */
        public static Node<Integer> reverseEdge(Node<Integer> from) {
            Node<Integer> pre = null;
            Node<Integer> next = null;
            while (from != null) {
                next = from.right;
                from.right = pre;
                pre = from;
                from = next;
            }
            return pre;
        }
    
        /**
         * morris遍历的应用
         * 判断一颗二叉树是否是搜索二叉树
         * (中序遍历时,遍历序列是升序的,即,左子树都比自己小,右子树都比自己大)
         * 时间复杂度 O(N)
         * 空间复杂度 O(1)
         *
         * @param head
         */
        public static boolean isBST(Node<Integer> head) {
            if (head == null) {
                return true;
            }
            Node<Integer> curr = head;
            Node mostRight = null;
            int preValue = Integer.MIN_VALUE;
            while (curr != null) {
                mostRight = curr.left;
                if (mostRight != null) {
                    while (mostRight.right != null && mostRight.right != curr) {
                        mostRight = mostRight.right;
                    }
                    //截止到这里,mostRigt找到了左子树的最右侧节点
                    if (mostRight.right == null) { //第一次访问最右侧节点
                        mostRight.right = curr;
                        curr = curr.left;
                        continue;
                    } else {
                        mostRight.right = null;//恢复左子树最右侧节点的默认值
                    }
                }
    //            System.out.print(curr.value + ",");
                //原本中序遍历打印的位置,做比较即可
                if (preValue >= curr.value) {
                    return false;
                }
                curr = curr.right;
            }
            return true;
        }
    
        public static void main(String[] args) {
            Node head = new Node(1);
    
            Node left = new Node(2);
            Node right = new Node(3);
    
            Node node4 = new Node(4);
            Node node5 = new Node(5);
            Node node6 = new Node(6);
            Node node7 = new Node(7);
    
            head.left = left;
            head.right = right;
    
            left.left = node4;
            left.right = node5;
            right.left = node6;
            right.right = node7;
    
            morris(head);
            System.out.println();
            System.out.println("---------------------------");
            morrisPre(head);
            System.out.println();
            System.out.println("---------------------------");
            morrisMid(head);
            System.out.println();
            System.out.println("---------------------------");
            morrisIn(head);
        }
    }

    发表评论:

  • 最新文章

  • Go-数组,切片,map
  • scp拷贝文件
  • 笔试题-牛羊吃草问题
  • 笔试题-最少的袋子数装苹果
  • 递归DP-找零钱的方法数
  • 存档

  • 2022年10月(1)
  • 2022年8月(1)
  • 2022年6月(11)
  • 2022年5月(6)
  • 2022年4月(33)
  • 2022年3月(26)
  • 2021年3月(1)
  • 2020年9月(2)
  • 2018年8月(1)
  • 2018年3月(1)
  • 2017年3月(3)
  • 2017年2月(6)
  • 2016年12月(3)
  • 2016年11月(2)
  • 2016年10月(1)
  • 2016年9月(3)
  • 2016年8月(4)
  • 2016年7月(3)
  • 2016年6月(4)
  • 2016年5月(7)
  • 2016年4月(9)
  • 2016年3月(4)
  • 2016年2月(5)
  • 2016年1月(17)
  • 2015年12月(15)
  • 2015年11月(12)
  • 2015年10月(6)
  • 2015年9月(11)
  • 2015年8月(8)
  • 分类

  • Java(4)
  • 基础(8)
  • IO(3)
  • JVM(7)
  • 多线程(11)
  • 调优命令(1)
  • Go(0)
  • 基础(1)
  • Linux(10)
  • mac(12)
  • 数据库(2)
  • Mysql(7)
  • Nosql(8)
  • 技术框架(2)
  • Spring(5)
  • Kafka(3)
  • ibatis(2)
  • 分布式(4)
  • 数据结构与欧宝安德拉(0)
  • 数据结构(6)
  • 欧宝安德拉(44)
  • 笔试题(19)
  • emlog(1)
  • 问题解决记录(2)
  • 随笔记录(26)
  • 金融(1)
  • 工具使用(8)
  • 操作系统(3)
  • 用友NC(3)
  • NC常见问题(2)
  • 热门文章

  • SpringMVC:Null ModelAndView returned to DispatcherServlet with name 'applicationContext': assuming HandlerAdapter completed request handling
  • Mac-删除卸载GlobalProtect
  • java.lang.SecurityException: JCE cannot authenticate the provider BC
  • Idea之支持lombok编译
  • MyBatis-Improper inline parameter map format. Should be: #{propName,attr1=val1,attr2=val2}
  • 标签

    mac emlog NC授权 授权数 用户数 破解 天上一天 redis 已达授权数 用友NC 可打印 地上一年 超光速 大于光速 时间静止 时光倒流 相对论 go基础 shell CountDownLatch 狱中诗 线程同步 任务同步 SecureCRT 光标消失 做人 做事 职业发展 选人 转义字符 json 格式错误 内存分区 操作系统 cache 分布式 程序 Linux crontab 定时任务 license 安全 备份 IO操作 同步 异步 阻塞 进程 线程 并发 共享内存 mybatis Improper inline 数据库 mysql 如果为null query paxos 分布式一致性 if ifnull spring ioc BlockingQueue OOM 软引用 弱引用 并行 jvm参数 gc jvm kafka 2016 数据库引擎 加密 解密 java文件压缩 命令 RDB AOF 配置 调优 sharding jvm结构 存储引擎 myiasm innodb 乐观锁 悲观锁 理财 欧宝安德拉 异地多活 ctrl+alt+delete idea lombok springmvc aes 宝宝 项目经理 nc curl 按位操作 逻辑思维 excel 原子增操作 awk printf OceanBase mac锁屏 快捷键 文件监听 confict git 商品管理 sku 自动注入 Apple ID Javassist branch 正则表达式 参数必填 代码优化 grep 程序员 未来 保险 坦然生活 抗风险 优秀经纪人 汉诺塔 递归
  • 最新评论

  • logisqykyk
    Javassist分析、编辑和创建jav...
  • xxedgtb
    Redis—常见参数配置 - 韭菜园 ...
  • wdgpjxydo
    SpringMVC:Null Model...
  • rllzzwocp
    Mysql存储引擎MyISAM和Inno...
  • dpkgmbfjh
    SpringMVC:Null Model...
  • tzklbzpj
    SpringMVC:Null Model...
  • bqwrhszmo
    MyBatis-Improper inl...
  • 乐谱吧
    good非常好
  • diaba
    @diaba:应该说是“时间的度量依据”...
  • diaba
    如果速度增加接近光速、等于光速、甚至大于...
  • 最新微语

  • 从今天起,做一个幸福的人。喂马,砍柴,(思想)周游世界

    2022-03-21 23:31

  • 2022.03.02 23:37:59

    2022-03-02 23:38

  • 几近崩溃后,找到解决方法,总是那么豁然开朗!所以遇到问题要坚持!

    2018-07-18 10:49

  • 2018年关键字“走心”

    2018-03-19 16:07

  • 保护好自己最大的方法是让自己更强大,不要柔弱的像一只绵羊一样,得谁巴拉,就谁巴拉!

    2017-12-20 10:24

  • 更多»

    Powered by emlog 京ICP备15045175号-1 Copyright © 2022