Java Morris遍歷演算法及在二元樹中應用的方法是什麼

一.Morris遍歷

1.什麼是Morris遍歷

Morris遍歷是一種用於二元樹遍歷的演算法，它可以在不使用堆疊或佇列的情況下實作中序遍歷。此演算法的時間複雜度為O(n)，空間複雜度為O(1)。

2.基本思想

Morris遍歷的基本思想是，利用葉子節點的空指標來儲存臨時訊息，以達到節省空間的目的。具體來說，對於目前遍歷到的節點，如果它有左子節點，就找到左子樹中最右邊的節點，將其右子節點指向當前節點，然後將目前節點更新為其左子節點。如果它沒有左子節點，就輸出目前節點的值，並將目前節點更新為其右子節點。重複以上步驟，直到遍歷完整棵樹。

3.Morris遍歷的優點和缺點

Morris遍歷的優點是空間複雜度低O(1)，但它的缺點是會改變原來的二元樹結構，因此需要在遍歷完後還原二元樹。此外，該演算法可能會比遞歸或使用堆疊的演算法稍微慢一些。

4.二元樹的線索化

二元樹的線索化,主要是利用了葉子結點中的空指針域,存放了在某種遍歷順序下的前驅或者後續結點,從而達到了線索二元樹的目的

例如,下圖中序遍歷結果展示如下,根據中序遍歷對空指標域進行線索化

#線索化的二元樹為下, 畫在左邊表示left結點指向,畫在右邊表示right指向,例如7的前驅結點為5,那麼7的left指向5,7的後繼節點為1,那麼7的right指向1

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

具體的程式碼實現如下:

public class InorderThreadedBinaryTree {
    private ThreadTreeNode pre = null;
    public void threadedNodes(ThreadTreeNode node) {
        //如果node==null，不能线索化
        if (node == null) {
            return;
        }
        //1、先线索化左子树
        threadedNodes(node.left);
        //2、线索化当前结点
        //处理当前结点的前驱结点
        //以8为例来理解
        //8结点的.left = null，8结点的.leftType = 1
        if (node.left == null) {
            //让当前结点的左指针指向前驱结点
            node.left = pre;
            //修改当前结点的左指针的类型，指向前驱结点
            node.leftType = 1;
        }
        //处理后继结点
        if (pre != null && pre.right == null) {
            //让当前结点的右指针指向当前结点
            pre.right = node;
            //修改当前结点的右指针的类型=
            pre.rightType = 1;
        }
        //每处理一个结点后，让当前结点是下一个结点的前驱结点
        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;
    }
}

但是在實作Morris遍歷的時候,並不需要把結點的左節點線索化,只需要把結點的右節點進行線索化即可,具體的原因在下面進行分析.

二.中序Morris遍歷

1.中序Morris遍歷的分析

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

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

2.中序Morris遍歷的思路

Morris遍歷是利用了線索二叉樹的思想,在遍歷的過程中不適用堆疊,從而達到了空間複雜度為O(1)

具體的實現如下:

1.初始化當前的結點為根結點

2.若當前的結點的左節點為空,則輸出當前結點,然後遍歷當前結點的右子樹,即'curr=curr.right'

3.若當前結點的左節點不為空,則找到當前結點的前驅節點,即當前結點左節點的最右側結點,記為'prev'

• 如果' prev.right''為空,則將pre.right指向curr結點,然後遍歷當前結點的左子樹,即'curr=curr.left'

• 如果' prev.right''不為空,說明已經遍歷完了當前節點的左子樹,斷開`prev.right` 的連接,即'prev.left=null',輸出當前節點,然後遍歷當前節點的右子樹,即`curr=curr.right`.

3.具體的程式碼實作

public class Morris {
    /**
     * 将当前根结点中序遍历的结果存储到list集合中
     * @param root  根结点
     * @return  中序遍历的结合
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left == null) { // 左子树为空，则输出当前节点，然后遍历右子树
                res.add(curr.val);  //如果要求直接打印,直接输出System.out.println(curr.val);
                curr = curr.right;
            } else {
                // 找到当前节点的前驱节点
                TreeNode prev = curr.left;
                while (prev.right != null && prev.right != curr) {
                    prev = prev.right;
                }
                if (prev.right == null) {
                    // 将前驱节点的右子树连接到当前节点
                    prev.right = curr;
                    curr = curr.left;
                } else {
                    // 前驱节点的右子树已经连接到当前节点，断开连接，输出当前节点，然后遍历右子树
                    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遍历的思路

前序和中序的遍历很想,只不过在打印(收集结点信息的时候不同),中序遍历是在当前结点的左节点为空(curr.left==null),或者当前结点已经被线索化(prev.right==curr)的时候进行打印,仔细观察前序遍历的过程,我们通过修改打印的顺序即可.前序遍历是在当前结点的左节点为空(curr.left==null),或者当前结点没有被线索化(prev.right==null)的时候进行打印

具体的思路如下:

1.初始化当前的结点为根结点

2.若当前的结点的左节点为空,则输出当前结点,然后遍历当前结点的右子树,即'curr=curr.right'

3.若当前结点的左节点不为空,则找到当前结点的前驱节点,即当前结点左节点的最右侧结点,记为'prev'

• 如果'prev.right''为空,输出当前节点,然后将pre.right指向curr结点,然后遍历当前结点的左子树,即'curr=curr.left'

• 如果'prev.right''不为空,说明已经遍历完了当前节点的左子树,断开 `prev.right` 的连接,即'prev.left=null',然后遍历当前节点的右子树,即 `curr=curr.right`.

2.具体的代码实现

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left == null) { // 左子树为空，则输出当前节点，然后遍历右子树
                res.add(curr.val);//如果要求直接打印,直接输出System.out.println(curr.val);
                curr = curr.right;
            } else {
                // 找到当前节点的前驱节点
                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);
                    // 将前驱节点的右子树连接到当前节点
                    prev.right = curr;
                    curr = curr.left;
                } else {
                    // 前驱节点的右子树已经连接到当前节点，断开连接，输出当前节点，然后遍历右子树
                    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遍历实现起来有一定的难度,但是基本代码还是不变,只是在打印的地方有略微的区别,

具体的思路如下:

1.初始化当前的结点为根结点

2.若当前的结点的左节点为空,则输出当前结点,然后遍历当前结点的右子树,即'curr=curr.right'

3.若当前结点的左节点不为空,则找到当前结点的前驱节点,即当前结点左节点的最右侧结点,记为'prev'

• 如果'prev.right''为空,然后将pre.right指向curr结点,然后遍历当前结点的左子树,即'curr=curr.left'

• 如果'prev.right''不为空,此时进行逆序存储,说明已经遍历完了当前节点的左子树,断开 `prev.right` 的连接,即'prev.left=null',然后遍历当前节点的右子树,即 `curr=curr.right`.

2.具体的代码实现

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode dump = new TreeNode(0);//建立一个临时结点
        dump.left = root;  //设置dump的左节点为root
        TreeNode curr = dump;  //当前节点为dump
        while (curr != null) {
            if (curr.left == null) { // 左子树为空，则输出当前节点，然后遍历右子树
                curr = curr.right;
            } else {
                // 找到当前节点的前驱节点
                TreeNode prev = curr.left;
                while (prev.right != null && prev.right != curr) {
                    prev = prev.right;
                }
                if (prev.right == null) {
                    // 将前驱节点的右子树连接到当前节点
                    prev.right = curr;
                    curr = curr.left;
                } else {
                    reverseAddNodes(curr.left, prev, res);
                    // 前驱节点的右子树已经连接到当前节点，断开连接，输出当前节点，然后遍历右子树
                    prev.right = null;
                    curr = curr.right;
                }
            }
        }
        return res;
    }
    private void reverseAddNodes(TreeNode begin, TreeNode end, List<Integer> res) {
        reverseNodes(begin, end); //将begin到end的进行逆序连接
        TreeNode curr = end;
        while (true) {//将逆序连接后端begin到end添加
            res.add(curr.val);
            if (curr == begin)
                break;
            curr = curr.right;
        }
        reverseNodes(end, begin);//恢复之前的连接状态
    }
    /**
     * 将begin到end的进行逆序连接
     *
     * @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));
    }

还是这样一颗二叉树,输出如下:

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

以上是Java Morris遍歷演算法及在二元樹中應用的方法是什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章！