快捷導(dǎo)航

Java Morris遍歷算法及其在二叉樹中的應(yīng)用

更新時間：2023年04月27日 09:42:03 作者：允歆辰丶

Morris遍歷是一種基于線索二叉樹的遍歷算法，可以在不使用?；蜻f歸的情況下，實現(xiàn)二叉樹的前序、中序和后序遍歷。該算法利用二叉樹中的空指針或線索指針，將遍歷序列嵌入到原二叉樹中，實現(xiàn)了常數(shù)級別的空間復(fù)雜度，適用于對空間要求較高的場景

一.Morris遍歷

1.什么是Morris遍歷

Morris遍歷是一種用于二叉樹遍歷的算法，它可以在不使用棧或隊列的情況下實現(xiàn)中序遍歷。該算法的時間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。

2.基本思想

Morris遍歷的基本思想是，利用葉子節(jié)點的空指針來存儲臨時信息，以達(dá)到節(jié)省空間的目的。具體來說，對于當(dāng)前遍歷到的節(jié)點，如果它有左子節(jié)點，就找到左子樹中最右邊的節(jié)點，將其右子節(jié)點指向當(dāng)前節(jié)點，然后將當(dāng)前節(jié)點更新為其左子節(jié)點。如果它沒有左子節(jié)點，就輸出當(dāng)前節(jié)點的值，并將當(dāng)前節(jié)點更新為其右子節(jié)點。重復(fù)以上步驟，直到遍歷完整棵樹。

3.Morris遍歷的優(yōu)點和缺點

Morris遍歷的優(yōu)點是空間復(fù)雜度低O(1)，但它的缺點是會改變原來的二叉樹結(jié)構(gòu)，因此需要在遍歷完后還原二叉樹。此外，該算法可能會比遞歸或使用棧的算法稍微慢一些。

4.二叉樹的線索化

二叉樹的線索化,主要是利用了葉子結(jié)點中的空指針域,存放了在某種遍歷順序下的前驅(qū)或者后續(xù)結(jié)點,從而達(dá)到了線索二叉樹的目的

例如,下圖中序遍歷結(jié)果展示如下,根據(jù)中序遍歷對空指針域進(jìn)行線索化

線索化的二叉樹為下, 畫在左邊表示left結(jié)點指向,畫在右邊表示right指向,例如7的前驅(qū)結(jié)點為5,那么7的left指向5,7的后繼節(jié)點為1,那么7的right指向1

由此,我們可能總結(jié)出這樣的結(jié)論:中序遍歷二叉樹的指向當(dāng)前結(jié)點的結(jié)點為當(dāng)前結(jié)點的左子樹的最右端結(jié)點,例如指向1的結(jié)點為1的左節(jié)點2的最右端結(jié)點為7,指向2結(jié)點的為2的左節(jié)點4的最右端結(jié)點4.這一點在之后的morris遍歷中很重要

具體的代碼實現(xiàn)如下:

public class InorderThreadedBinaryTree {
    private ThreadTreeNode pre = null;
    public void threadedNodes(ThreadTreeNode node) {
        //如果node==null，不能線索化
        if (node == null) {
            return;
        }
        //1、先線索化左子樹
        threadedNodes(node.left);
        //2、線索化當(dāng)前結(jié)點
        //處理當(dāng)前結(jié)點的前驅(qū)結(jié)點
        //以8為例來理解
        //8結(jié)點的.left = null，8結(jié)點的.leftType = 1
        if (node.left == null) {
            //讓當(dāng)前結(jié)點的左指針指向前驅(qū)結(jié)點
            node.left = pre;
            //修改當(dāng)前結(jié)點的左指針的類型，指向前驅(qū)結(jié)點
            node.leftType = 1;
        }
        //處理后繼結(jié)點
        if (pre != null && pre.right == null) {
            //讓當(dāng)前結(jié)點的右指針指向當(dāng)前結(jié)點
            pre.right = node;
            //修改當(dāng)前結(jié)點的右指針的類型=
            pre.rightType = 1;
        }
        //每處理一個結(jié)點后，讓當(dāng)前結(jié)點是下一個結(jié)點的前驅(qū)結(jié)點
        pre = node;
        //3、線索化右子樹
        threadedNodes(node.right);
    }
}
class ThreadTreeNode {
    int val;
    ThreadTreeNode left;
    //0為非線索化,1為線索化
    int leftType;
    ThreadTreeNode right;
    //0為非線索化,1為線索化
    int rightType;
    public ThreadTreeNode(int val) {
        this.val = val;
    }
}

但是在實現(xiàn)Morris遍歷的時候,并不需要把結(jié)點的左節(jié)點線索化,只需要把結(jié)點的右節(jié)點進(jìn)行線索化即可,具體的原因在下面進(jìn)行分析.

二.中序Morris遍歷

1.中序Morris遍歷的分析

上面我們說了Morris遍歷的時候只需要線索化右節(jié)點,這里給大家進(jìn)行解釋.當(dāng)我們在中序遍歷一棵樹的時候,還比如是這樣一棵樹,我們一步步的node.left來到了6這個結(jié)點,這個結(jié)點的left為空,所以我們打印6這個結(jié)點的值,此時我們需要返回上一個結(jié)點,如果我們是要中序遞歸進(jìn)行遍歷的話,需要返回上一個棧,而我們Morris遍歷的時候無法進(jìn)行遞歸的返回,所以這個時候我們只需要把6的right結(jié)點進(jìn)行線索化,這個時候6的right指向4,我們就可以返回到4,把4這個結(jié)點進(jìn)行打印,4也線索化返回了2,把2進(jìn)行打印,然后進(jìn)行2的right結(jié)點5,5的left結(jié)點為空,因此打印5,之后進(jìn)入到5的right結(jié)點7,打印7,7的right結(jié)點也進(jìn)行了線索化,進(jìn)入7的right結(jié)點為1,然后打印1,進(jìn)入3結(jié)點并且打印

因為最好不要改變樹的結(jié)構(gòu),所以我們在打印的時候,將線索化的結(jié)點的right結(jié)點置為空.

2.中序Morris遍歷的思路

Morris遍歷是利用了線索二叉樹的思想,在遍歷的過程中不適用棧,從而達(dá)到了空間復(fù)雜度為O(1)

具體的實現(xiàn)如下:

1.初始化當(dāng)前的結(jié)點為根結(jié)點

2.若當(dāng)前的結(jié)點的左節(jié)點為空,則輸出當(dāng)前結(jié)點,然后遍歷當(dāng)前結(jié)點的右子樹,即'curr=curr.right'

3.若當(dāng)前結(jié)點的左節(jié)點不為空,則找到當(dāng)前結(jié)點的前驅(qū)節(jié)點,即當(dāng)前結(jié)點左節(jié)點的最右側(cè)結(jié)點,記為'prev'

如果'prev.right''為空,則將pre.right指向curr結(jié)點,然后遍歷當(dāng)前結(jié)點的左子樹,即'curr=curr.left'
如果'prev.right''不為空,說明已經(jīng)遍歷完了當(dāng)前節(jié)點的左子樹,斷開 `prev.right` 的連接,即'prev.left=null',輸出當(dāng)前節(jié)點,然后遍歷當(dāng)前節(jié)點的右子樹,即 `curr=curr.right`.

3.具體的代碼實現(xiàn)

public class Morris {
    /**
     * 將當(dāng)前根結(jié)點中序遍歷的結(jié)果存儲到list集合中
     * @param root  根結(jié)點
     * @return  中序遍歷的結(jié)合
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left == null) { // 左子樹為空，則輸出當(dāng)前節(jié)點，然后遍歷右子樹
                res.add(curr.val);  //如果要求直接打印,直接輸出System.out.println(curr.val);
                curr = curr.right;
            } else {
                // 找到當(dāng)前節(jié)點的前驅(qū)節(jié)點
                TreeNode prev = curr.left;
                while (prev.right != null && prev.right != curr) {
                    prev = prev.right;
                }
                if (prev.right == null) {
                    // 將前驅(qū)節(jié)點的右子樹連接到當(dāng)前節(jié)點
                    prev.right = curr;
                    curr = curr.left;
                } else {
                    // 前驅(qū)節(jié)點的右子樹已經(jīng)連接到當(dāng)前節(jié)點，斷開連接，輸出當(dāng)前節(jié)點，然后遍歷右子樹
                    prev.right = null;
                    res.add(curr.val);//如果要求直接打印,直接輸出System.out.println(curr.val);
                    curr = curr.right;
                }
            }
        }
        return res;
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

測試:

還是這樣一顆二叉樹,輸出如下:

[6, 4, 2, 5, 7, 1, 3]

三.前序Morris遍歷

1.前序Morris遍歷的思路

前序和中序的遍歷很想,只不過在打印(收集結(jié)點信息的時候不同),中序遍歷是在當(dāng)前結(jié)點的左節(jié)點為空(curr.left==null),或者當(dāng)前結(jié)點已經(jīng)被線索化(prev.right==curr)的時候進(jìn)行打印,仔細(xì)觀察前序遍歷的過程,我們通過修改打印的順序即可.前序遍歷是在當(dāng)前結(jié)點的左節(jié)點為空(curr.left==null),或者當(dāng)前結(jié)點沒有被線索化(prev.right==null)的時候進(jìn)行打印

具體的思路如下:

1.初始化當(dāng)前的結(jié)點為根結(jié)點

2.若當(dāng)前的結(jié)點的左節(jié)點為空,則輸出當(dāng)前結(jié)點,然后遍歷當(dāng)前結(jié)點的右子樹,即'curr=curr.right'

3.若當(dāng)前結(jié)點的左節(jié)點不為空,則找到當(dāng)前結(jié)點的前驅(qū)節(jié)點,即當(dāng)前結(jié)點左節(jié)點的最右側(cè)結(jié)點,記為'prev'

如果'prev.right''為空,輸出當(dāng)前節(jié)點,然后將pre.right指向curr結(jié)點,然后遍歷當(dāng)前結(jié)點的左子樹,即'curr=curr.left'
如果'prev.right''不為空,說明已經(jīng)遍歷完了當(dāng)前節(jié)點的左子樹,斷開 `prev.right` 的連接,即'prev.left=null',然后遍歷當(dāng)前節(jié)點的右子樹,即 `curr=curr.right`.

2.具體的代碼實現(xiàn)

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left == null) { // 左子樹為空，則輸出當(dāng)前節(jié)點，然后遍歷右子樹
                res.add(curr.val);//如果要求直接打印,直接輸出System.out.println(curr.val);
                curr = curr.right;
            } else {
                // 找到當(dāng)前節(jié)點的前驅(qū)節(jié)點
                TreeNode prev = curr.left;
                while (prev.right != null && prev.right != curr) {
                    prev = prev.right;
                }
                if (prev.right == null) {
                    res.add(curr.val);//如果要求直接打印,直接輸出System.out.println(curr.val);
                    // 將前驅(qū)節(jié)點的右子樹連接到當(dāng)前節(jié)點
                    prev.right = curr;
                    curr = curr.left;
                } else {
                    // 前驅(qū)節(jié)點的右子樹已經(jīng)連接到當(dāng)前節(jié)點，斷開連接，輸出當(dāng)前節(jié)點，然后遍歷右子樹
                    prev.right = null;
                    curr = curr.right;
                }
            }
        }
        return res;
    }

測試:

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(5);
        root.left.right.right = new TreeNode(7);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.left.left = new TreeNode(6);
        System.out.println(preorderTraversal(root));
    }

還是這樣一顆二叉樹,輸出如下:

[1, 2, 4, 6, 5, 7, 3]

四.后序Morris遍歷

1.后序Morris遍歷的思路

后序Morris遍歷實現(xiàn)起來有一定的難度,但是基本代碼還是不變,只是在打印的地方有略微的區(qū)別,

具體的思路如下:

1.初始化當(dāng)前的結(jié)點為根結(jié)點

2.若當(dāng)前的結(jié)點的左節(jié)點為空,則輸出當(dāng)前結(jié)點,然后遍歷當(dāng)前結(jié)點的右子樹,即'curr=curr.right'

3.若當(dāng)前結(jié)點的左節(jié)點不為空,則找到當(dāng)前結(jié)點的前驅(qū)節(jié)點,即當(dāng)前結(jié)點左節(jié)點的最右側(cè)結(jié)點,記為'prev'

如果'prev.right''為空,然后將pre.right指向curr結(jié)點,然后遍歷當(dāng)前結(jié)點的左子樹,即'curr=curr.left'
如果'prev.right''不為空,此時進(jìn)行逆序存儲,說明已經(jīng)遍歷完了當(dāng)前節(jié)點的左子樹,斷開 `prev.right` 的連接,即'prev.left=null',然后遍歷當(dāng)前節(jié)點的右子樹,即 `curr=curr.right`.

2.具體的代碼實現(xiàn)

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode dump = new TreeNode(0);//建立一個臨時結(jié)點
        dump.left = root;  //設(shè)置dump的左節(jié)點為root
        TreeNode curr = dump;  //當(dāng)前節(jié)點為dump
        while (curr != null) {
            if (curr.left == null) { // 左子樹為空，則輸出當(dāng)前節(jié)點，然后遍歷右子樹
                curr = curr.right;
            } else {
                // 找到當(dāng)前節(jié)點的前驅(qū)節(jié)點
                TreeNode prev = curr.left;
                while (prev.right != null && prev.right != curr) {
                    prev = prev.right;
                }
                if (prev.right == null) {
                    // 將前驅(qū)節(jié)點的右子樹連接到當(dāng)前節(jié)點
                    prev.right = curr;
                    curr = curr.left;
                } else {
                    reverseAddNodes(curr.left, prev, res);
                    // 前驅(qū)節(jié)點的右子樹已經(jīng)連接到當(dāng)前節(jié)點，斷開連接，輸出當(dāng)前節(jié)點，然后遍歷右子樹
                    prev.right = null;
                    curr = curr.right;
                }
            }
        }
        return res;
    }
    private void reverseAddNodes(TreeNode begin, TreeNode end, List<Integer> res) {
        reverseNodes(begin, end); //將begin到end的進(jìn)行逆序連接
        TreeNode curr = end;
        while (true) {//將逆序連接后端begin到end添加
            res.add(curr.val);
            if (curr == begin)
                break;
            curr = curr.right;
        }
        reverseNodes(end, begin);//恢復(fù)之前的連接狀態(tài)
    }
    /**
     * 將begin到end的進(jìn)行逆序連接
     *
     * @param begin
     * @param end
     */
    private void reverseNodes(TreeNode begin, TreeNode end) {
        TreeNode prev = begin;
        TreeNode curr = prev.right;
        TreeNode post;
        while (prev != end) {
            post = curr.right;
            curr.right = prev;
            prev = curr;
            curr = post;
        }
    }

測試:

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(5);
        root.left.right.right = new TreeNode(7);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.left.left = new TreeNode(6);
        System.out.println(postorderTraversal(root));
    }

還是這樣一顆二叉樹,輸出如下: