COP 3530
  Section U03
  Spring 2016



                Homework #5
                ===========


                                        Due date: April 19, 2017




   The threaded tree of a binary tree is obtained by setting every null left child
to the predecessor of the node in the inorder traversal and every null right child
to the successor of the node in the inorder traversal.
It is important that we distinguish beteen the solid and the dashed lines.
For this reason we use the boolean fields lThread and rThread which are true when
the respective child is a thread.

You must complete the class ThreadedNode displayed below.

// this class describes the nodes of a tree threaded in inorder
public class ThreadedNode<T> {

    // the fields
    private T element; // the element
    // lThread is true if the left child is a thread and false if it is not
    private boolean lThread = false;
    private ThreadedNode<T> left; // the left child
    // rThread is true if the right child is a thread and false if it is not
    private boolean rThread = false;
    private ThreadedNode<T> right; // the right child

    // create a node with a given value and children
    // the threads are set to false
    public ThreadedNode(T theElement, ThreadedNode<T> lt, ThreadedNode<T> rt)
    {
        element = theElement;
        left = lt;
        right = rt;
    }

    // create a threaded tree that is identical to the root tree, 
    // execept that it has the threads  
    public ThreadedNode( BinaryNode<T> root)
    {
        // you write it
    }

    // return the element
    public T getElement()
    {
        return element;
    }

    // return lThread
    public boolean isLeftAThread()
    {
        return lThread;
    }
            
    // return the left child
    public ThreadedNode<T> getLeft()
    {
        return left;
    }

    // return rThread
    public boolean isRightAThread()
    {
        return rThread;
    }

    // return the right child
    public ThreadedNode<T> getRight()
    {
        return right;
    }

    // set the element to a given value
    // @param x is the new value
    public void setElement( T x)
    {
        element = x;
    }

    // set the left child
    // @param t is the left child
    public void setLeft(ThreadedNode<T> t)
    {
        left = t;
    }

    // set the right child
    // @param t is the right child
    public void setRight(ThreadedNode<T> t)
    {
        right = t;
    }

    // set the left thread
    // newT is the new thread
    public void setLeftThread(boolean newT )
    {
        lThread = newT;
    }

    // set the right thread
    // newT is the new thread
    public void setRightThread(boolean newT )
    {
        rThread = newT;
    }


    // print the tree elements in inorder
    public void printInOrder()
    {
        // write an iterative method that prints
        // the items of a threaded tree in inorder
        // do not use a stack

     } // end method

}


You must also write the 2 methods below and put them in
the BinaryNode class.

1. public static <T> BinaryNode<T> thread(BinaryNode<T> root)

   that threads the root tree. However, this time the threading 
   produces a binary tree that does not keep track of whether 
   the child is genuine a thread. 
   
2. public static <T> BinaryNode<T> unthread(BinaryNode<T> root)
   takes as input the output of the preceding method and 
   returns the original tree.

E-mail me  the complete class ThreadedNode.java and put the 2 methods    
thread and unthread in the BinaryNode class. Don't put any other methods 
and fields in the BinaryNode class since I have them.