What is the Java Morris traversal algorithm and its application in binary trees?

1. Morris traversal

1. What is Morris traversal

Morris traversal is an algorithm for binary tree traversal, which can be implemented without using a stack or queue. Order traversal. The time complexity of this algorithm is O(n) and the space complexity is O(1).

2. Basic idea

The basic idea of ​​Morris traversal is to use the null pointer of leaf nodes to store temporary information to save space. Specifically, for the currently traversed node, if it has a left child node, find the rightmost node in the left subtree, point its right child node to the current node, and then update the current node to its left child node. If it has no left child, output the value of the current node and update the current node to its right child. Repeat the above steps until the complete tree is traversed.

3. Advantages and disadvantages of Morris traversal

The advantage of Morris traversal is that the space complexity is low O(1), but its disadvantage is that it will change the original binary tree structure, so it needs to be traversed After completion, restore the binary tree. Additionally, the algorithm may be slightly slower than recursive or stack-using algorithms.

4. Threading of binary trees

Threading of binary trees mainly uses the null pointer field in the leaf nodes to store the predecessor or subsequent nodes in a certain traversal order. , thus achieving the purpose of a clue binary tree

For example, the in-order traversal results in the figure below are shown below, and the null pointer field is clueed according to the in-order traversal

The clued binary tree is downward. Drawing it on the left indicates that the left node points to it, and drawing it on the right indicates that the right node points. For example, the predecessor node of 7 is 5, then the left node of 7 points to 5, and the successor node of 7 is 1, then the node of 7 right points to 1

From this, we may conclude that the node pointing to the current node in the in-order traversal of the binary tree is the left subtree of the current node. The rightmost node, for example, the rightmost node of left node 2, which points to node 1, is 7, and the rightmost node 4 of left node 4, which points to node 2, is 2. This point will be traversed later by Morris is very important

The specific code implementation is as follows:

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;
    }
}

But when implementing Morris traversal, it is not necessary to thread the left node of the node, only the right node of the node is Just perform clues. The specific reasons are analyzed below.

2. In-order Morris traversal

1. Analysis of mid-order Morris traversal

We said above During Morris traversal, we only need to clue the right node, which is explained here. When we traverse a tree in in-order, for example, this tree, we step by step node.left comes to the node 6 , the left of this node is empty, so we print the value of the node 6. At this time we need to return to the previous node. If we want to traverse in-order recursion, we need to return to the previous stack, and our Morris traversal It is impossible to return recursively, so at this time we only need to clue the right node of 6. At this time, the right node of 6 points to 4, we can return to 4, print the node 4, and 4 is also a clue Returns 2, prints 2, and then goes to the right node 5 of 2. The left node of 5 is empty, so 5 is printed, and then it goes to the right node 7 of 5, and the right node of 7 and 7 is also printed. After threading, enter the right node of 7 as 1, then print 1, enter the 3 node and print

Because it is best not to change the structure of the tree, so when we print, we will thread the The right node of the node is set to empty.

##2. The idea of ​​​​in-order Morris traversal

Morris traversal uses the idea of ​​​​the clue binary tree. The stack is not used during the traversal process, thus achieving a space complexity of O(1)

The specific implementation is as follows:

1. Initialize the current node as the root node

2. If the left node of the current node is empty, output the current node, and then traverse the right subtree of the current node, that is, 'curr=curr.right'

3. If the current node If the left node of the node is not empty, find the predecessor node of the current node, that is, the rightmost node of the left node of the current node, recorded as 'prev'

• if' prev.right'' is empty, then point pre.right to the curr node, and then traverse the left subtree of the current node, that is, 'curr=curr.left'

• if' prev.right'' is not empty, indicating that the left subtree of the current node has been traversed, disconnect `prev.right`, that is, 'prev.left=null', output the current node, and then traverse the right subtree of the current node Tree, that is `curr=curr.right`.

3. Specific code implementation

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;
    }
}

Test:

It is still such a binary tree, the output is as follows:

[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]

The above is the detailed content of What is the Java Morris traversal algorithm and its application in binary trees?. For more information, please follow other related articles on the PHP Chinese website!