public void insertThreaded(E x)
{
if (root==null)
{
root = new ThreadedTreeNode<E>(x);
return;
}
current = root;
//
//find appropriate null node to insert new node
while(current != null)
{
//initialize trailer to current
trailer = current;
//if x > current.data, move to right subtree
if (x.compareTo(current.getData())>0 )
{
if(current.getIsThreaded())
break;
trailer = current;
current = current.getRight();
}
//if x < current.data, move to left subtree
else if (x.compareTo(current.getData())<0)
{
trailer = current;
current = current.getLeft();
}
//break loop if node x already exist in tree.
else
{
return;
}
}
//
//current is null, compare x with trailer.data and insert x as child to trailer.
//if x > trailer.data, move to right subtree
if (x.compareTo(trailer.getData())>0)
{
//create new node for x with null left reference and right thread from trailer
ThreadedTreeNode<E> node = new ThreadedTreeNode<E>(x, null, trailer.getRight());
//set trailer right reference to x
trailer.setRight(node);
//remove isThread flag from trailer
trailer.setIsThread(false);
}
//if x < trailer.data, move to left subtree
else if(x.compareTo(trailer.getData())<0)
{
//create new node for x with null left reference and right thread from trailer
ThreadedTreeNode<E> node = new ThreadedTreeNode<E>(x, null, trailer);
//set trailer left reference to x
trailer.setLeft(node);
//remove isThread flag from trailer
}
//do nothing if node x already exists in tree
else
{
return;
}
}