算法-二叉树遍历-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);
    }
}

发表评论:

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