Morris Traversal

Posted on | Edited on | Views: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// Java program to print inorder traversal without recursion and stack 

/* A binary tree tNode has data, a pointer to left child 
and a pointer to right child */
class tNode {
    int data;
    tNode left, right;
    tNode(int item) {data = item;left = right = null;}
}

public class marris_inorder {
    tNode root;
    // Function to traverse a binary tree without recursion and without stack
    void MorrisTraversal(tNode root) {
        tNode current, pre;

        if (root == null) return;

        current = root;
        while (current != null) {
            if (current.left == null) {
                System.out.print(current.data + " ");
                current = current.right;
            } else {
                /* Find the inorder predecessor of current */
                pre = current.left;
                while (pre.right != null && pre.right != current)
                    pre = pre.right;

                /* Make current as right child of its inorder predecessor */
                if (pre.right == null) {
                    pre.right = current;
                    current = current.left;
                }
                /*
                 * Revert the changes made in the 'if' part to restore the original tree i.e.,
                 * fix the right child of predecessor
                 */
                else {
                    pre.right = null;
                    System.out.print(current.data + " ");
                    current = current.right;
                } /* End of if condition pre->right == NULL */

            } /* End of if condition current->left == NULL */

        } /* End of while */
    }

    public static void main(String args[]) {
        /* Constructed binary tree is 
               1 
             /   \ 
            2     3 
          /   \ 
         4     5 
        */
        marris_inorder tree = new marris_inorder();
        tree.root = new tNode(1);
        tree.root.left = new tNode(2);
        tree.root.right = new tNode(3);
        tree.root.left.left = new tNode(4);
        tree.root.left.right = new tNode(5);

        tree.MorrisTraversal(tree.root);
        System.out.println();
    }
}
0%