ThreadedBinaryTree

/***********************TBNode**************************/

class TBNode<E extends Comparable<E>> {
public E info;
public TBNode <E> left;
public TBNode <E> right;
char ltag, rtag;

public TBNode(E info) { //kreira jazol list
this.info = info;
ltag=rtag='-';

}
}

/***********************TBTree**************************/

class TBTree <E extends Comparable<E>>
{
    public TBNode <E> lead;  //jazol vodach

    public boolean proveri()
    {
        TBNode<E> it = succInorder(lead);
        while(it != lead && succInorder(it) != lead)
        {
            if(Math.abs((Integer)it.info - (Integer)succInorder(it).info) != 1 )
                return false;
            it = succInorder(it);
        }
        return true;
    }

    public TBTree() //kreirame jazol vodach
    {
        lead=new TBNode(null);
        lead.left=lead.right=lead; //vodachot pokazhuva sam na sebe
        lead.rtag='+';
        lead.ltag='-';
    }
    public void  makeRoot(E x) //kreirame jazol koren
    {
        TBNode <E> root= new TBNode(x);
        root.left=root.right=lead; //korenot na pochetok pokazhuva kon vodachot
        lead.left=root; //vodachot samo od levo pokazhuva kon korenot
        lead.ltag='+';

    }

    public void insert(E x, TBNode<E> r)
    {
        if(r.left==r) //ako drvoto e prazno, odnosno imame samo jazol vodach
            makeRoot(x);
        else
        {
            TBNode <E> n=new TBNode(x);
            TBNode <E> pom = r.left; //pochuvame od korenot
            //da barame soodvetna pozicija za vmetnuvanje
           while(pom!=r) //se duri ne gi izmineme site jzali
           {
               int comp=x.compareTo(pom.info);
               if(comp<0)
               {
                   if(pom.ltag=='-') //sme nashle pozicija za vmetnuvanje
                   {
                       n.left=pom.left;
                       pom.left=n;
                       n.right=pom;
                       pom.ltag='+';
                       break;
                   }
                   else
                       pom=pom.left;
               }
               else if(comp>0)
               {
                   if(pom.rtag=='-') //sme nashle pozicija za vmetnuvanje
                   {
                       n.right=pom.right;
                       pom.right=n;
                       n.left=pom;
                       pom.rtag='+';
                       break;
                   }
                   else
                       pom=pom.right;
               }
               else ;
           }
        }
    }

    public TBNode<E> predInorder(TBNode <E> node)
    {
        if(node.ltag=='-') //ako node e najleviot jazol vo drvoto
            return node.left;
        /* prethodnik na jazol vo inorder e posledno poseteniot jazol pred da se poseti node
         * a toa e najdesniot jazol vo levoto podsteblo na node */
        TBNode<E> pom=node.left;
        while(pom.rtag=='+')
            pom=pom.right;
        return pom;
    }

    public TBNode<E> succInorder(TBNode <E> node)
    {
        if(node.rtag=='-') //ako node e najdesniot jazol vo drvoto
            return node.right;
        /* sledbenik na jazol vo inorder e prvo poseteniot jazol otkako kje se poseti node
         * a toa e najleviot jazol vo desnoto podsteblo na node */
        TBNode<E> pom=node.right;
        while(pom.ltag=='+')
            pom=pom.left;
        return pom;
    }

    public TBNode <E> find(E x, TBNode <E> r)
    {
        if(lead.left==lead) return null;
        TBNode <E> pom=lead.left;
        while(pom!=lead)
        {
             int comp=x.compareTo(pom.info);
               if(comp<0)
               pom=pom.left;
               else if(comp>0)
               pom=pom.right;
               else
                   return pom;
        }
        return pom;
    }

    public void inorder()
    {
        if(lead.left==lead)
            return;
        //treba da pochneme od najleviot jazol, koj e sledbenik na lead
        TBNode<E> pom=succInorder(lead);
        //potoa so pomosh na funkcijata sledbenik, gi izminuvame site jazli
        while(pom!=lead)
        {
            System.out.print(pom.info+" ");
            pom=succInorder(pom);
        }
        System.out.println();
    }

    public TBNode <E> succPreorder(TBNode <E> node)
    {
        if(node.ltag=='+') //ako levo ima jazol, toj e prviot koj kje se izmine posle jazolot node
            return node.left;
        if(node.rtag=='+') //ako levo nema, no desno ima jazol, toj e sledbenik
        return node.right;
         //ako stanuva zbor za list
        while(node.rtag=='-')//dvizhi se po nishki na desno, duri ne dojdesh do vrska
        node=node.right;
        if(node==lead) return lead; //ako stanuva zbor za posledniot jazol od izminuvanjeto, vodachot e sledbenik
        else
        return node.right;
    }

    public TBNode <E> predPostorder(TBNode <E> node)
    {
        if(node.rtag=='+') //ako desno ima jazol toj kje se izmine vednash pred jazolot p
        return node.right;
        while(node.ltag=='-')//dvizhi se po nishki na levo, duri ne dojdesh do vistinska vrska
        node=node.left;
        return node.left; //vrati go jazolot levo od pogore najdeniot koren
    }
   public void insertRight(TBNode <E> parent, TBNode <E> child)
  {
    TBNode <E> pom;
    child.right=parent.right;    //1
    child.rtag=parent.rtag;      //1

    child.left=parent;  //2
    child.ltag='-'; //2

    parent.right=child; //3
    parent.rtag='+';    //3

    if(child.rtag=='+')
    {
    pom=child.right;
    while(pom.ltag=='+')
    pom=pom.left;
    pom.left=child;
    }
 }


}

public class ThreadedBinaryTree {


    public static void main(String[] args) {

        TBTree <Integer> tree=new TBTree();
       tree.insert(7, tree.lead);
        tree.insert(2, tree.lead);
        tree.insert(1, tree.lead);
        tree.insert(15, tree.lead);
        tree.insert(13, tree.lead);
        tree.insert(14, tree.lead);

        System.out.println(tree.proveri());

        tree.inorder();


    }


}