Threaded Binary Tree : Construction and Inorder Traversal [Java]

Threaded Binary Trees: Instead of containing a null pointer in its right field, a node with an empty right subtree points to its inorder successor. Such a pointer is called a thread. Note that the rightmost node in each tree still has a null right pointer, since it has no inorder successor. Such trees are called right in--threaded binary trees. A threaded binary tree eliminates the need for a stack in a nonrecursive traversal even if a father field is not available.

To implement a right in-threaded binary tree under the dynamic node implementation of a binary tree, and extra logical field, rthread, is included within each node to indicate whether or not its right pointer is a thread. For consistency, the rthread field of the rightmost node of a tree (i.e. the last node in the tree's inorder traversal) is also set to true, although its right field remains null.

The inorder traversal of a binary tree gives its elements in ascending order. So if the user inputs (-999 is end marker for input):

1 2 5 2 3 4 6 7 4 5 7 7 -999

the output will be

1 2 2 3 4 4 5 5 6 7 7 7

which is in ascending order, as expected.

Important sections of the code are italicized. They should be understood carefully.

import java.util.Scanner;

class nodetype {

    int info;
    nodetype left;  /*reference to left son*/

    nodetype right; /*reference to right son*/

    boolean rthread; /*
     rhtread is TRUE if right is
     null or non-null THREAD 
     */

}

public class ThreadedBinaryTrees {

    static nodetype maketree(int x) {
        nodetype p;

        p = getnode();
        p.info = x;
        p.left = null;
        p.right = null;
        p.rthread = true;
        return p;
    }

    static nodetype getnode() {
        return new nodetype();
    }

    static void setleft(nodetype p, int x) {
        nodetype q;

        if (p == null) {
            System.out.println("Void insertion\n");
        } else if (p.left != null) {
            System.out.println("Invalid insertion\n");
        } else {
            q = getnode();
            q.info = x;
            p.left = q;
            q.left = null;
            /* The inorder successor of node(q) is node(p) */
            q.right = p;
            q.rthread = true;
        }/*end if*/

    }/*end setleft*/


    static void setright(nodetype p, int x) {
        nodetype q, r;

        if (p == null) {
            System.out.println("Void insertion\n");
        } else if (!p.rthread) {
            System.out.println("Invalid insertion\n");
        } else {
            q = getnode();
            q.info = x;
            /* save the inorder successor of node(p) */
            r = p.right;
            p.right = q;
            p.rthread = false;
            q.left = null;
            /*the inorder successor of node(q) is the previous suuccessor of node(p)*/
            q.right = r;
            q.rthread = true;
        } /* end else */

    }     /* end setright */


    static void intrav3(nodetype tree) {
        nodetype p, q;
        p = tree;
        do {
            q = null;
            while (p != null) { /* Traverse left branch */

                q = p;
                p = p.left;
            }/*end while*/

            if (q != null) {
                System.out.print(q.info + " ");
                p = q.right;
                while (q.rthread && p != null) {
                    System.out.print(p.info + " ");
                    q = p;
                    p = p.right;
                }/* end while */

            }/* end if */

        } while (q != null);
    }
    
    public static void main(String[] args){
        nodetype ptree;
        nodetype p = null, q;
        int number;
        
        System.out.println("Binary Tree Traversal\n\n");
        System.out.println("Enter numbers :");
        Scanner scan = new Scanner(System.in);
        number = scan.nextInt();
        
        ptree = maketree(number);
        
        while((number=scan.nextInt())!=-999){
            p = q = ptree;
            while(q!=null){
               p=q;
            if(number<p.info)
                q = p.left;
            else if(number>=p.info){
                if(!p.rthread){
                q = p.right;
                }
                if(p.rthread){
                    setright(p, number);
                    break;
                }                  
            }
        }
    
         if (number<p.info)
            setleft(p, number); 
        }
        
        System.out.println("\nInorder traversal : ");
        intrav3(ptree);
    }
}