/***************************************************************/
/* Prof. Dr. Gregor Büchel                                     */
/* Source : BB2anw3.java                                       */
/* Eine Java-Applikation für Binaerbaeume:  Mittels der Metho- */
/* de neuast() wird der Binaerbaum als lexikographisch sortier-*/
/* Baum (inorder) aufgebaut (gemaess des Algorithmus von Ker-  */
/* nighan & Ritchie). Die Methode inorder() gibt den Binaerbaum*/
/* inorder aus. Beide Methoden sind  r e k u r s i v  program- */
/* miert.                                                      */
/* Die Methoden hiertreu() gibt den Baum hierarchietreu aus,   */
/* d.h. von der Wurzel ueber alle Children-Knoten bis zu den   */
/* Blaettern werden die Knoten gemaess ihrer Anordnung auf den */
/* Hierarchiestufen ausgegeben. Die Baumknoten werden sukzes-  */
/* sive in eine Pipeline geschrieben, die durch eine doppelt   */
/* verkettete Liste verwaltet wird.                            */
/*                                                             */
/* Stand : 12.05.2002                                          */
/***************************************************************/

import java.util.*;

class BB2anw3
{public static void main(String args[]) 
 {String ew;
  BB2 wurz=null;
  int ip=0;
  ew=new String();
  System.out.println("Geben Sie eine Wortfolge ein. ENDE = '.' ");
  ew=IO1.einstring();
  while (ew.substring(0,1).compareTo(".")!=0)
  { wurz=neuast(wurz,ew,ip);
    ew=IO1.einstring();
  } 
  System.out.println("Lexikographisch sortierte Wortliste:");
  System.out.println("::: hp : anz : wort");
  inorder(wurz); 
  /* Aufruf der hierarchietreuen Ausgabe des Baumes */
  hiertreu(wurz);
  System.out.println("EOP.");
 }
 
 static BB2 neuast(BB2 wok, String ew, int ip)
 { BB2 kneu=null;
   int ir;
   int k;
   k=ip+1;
   if (wok==null)
   { kneu=new BB2();
     kneu.wo=ew;
     kneu.wz=1;
     kneu.hp=k;
     kneu.lnf=null;
     kneu.rnf=null;
     System.out.println("->(neu) "+kneu.wo);
     return kneu;
   };
   ir=ew.compareTo(wok.wo);
   if (ir==0) 
   { wok.wz=wok.wz+1;
     System.out.println("->(neue Anzahl:) "+wok.wz);
   }
   /* rekursiver Aufruf auf den linken Nachfolgerknoten */
   if (ir<0) 
   { wok.lnf=neuast(wok.lnf,ew,k);
     System.out.println("->(links nach:) "+wok.wo);
   }
   /* rekursiver Aufruf auf den rechten Nachfolgerknoten */
   if (ir>0) 
   { wok.rnf=neuast(wok.rnf,ew,k);
     System.out.println("->(rechts nach:) "+wok.wo);
   }
   return wok;
 }

 static void hiertreu(BB2 wok)
 { List ls1;
   ListIterator lit1;
   int makt, n, sz=0;
   boolean b1;
   BB2 akt,kn1;
   akt=wok;
   ls1=new ArrayList();
   /* Baum in eine Pipeline schreiben */
   /* Wurzel = Ende der Pipeline      */
   b1=ls1.add(akt);
   makt=ls1.indexOf(akt);
   System.out.println(" ");
   System.out.println("Zustand der Liste ");
   /* Der Zustand der Liste wird durch die Position      */
   /* des Knotens akt, der das Nachlesen von Baumknoten  */
   /* in die verkettete Liste steuert, dokumentiert.     */
   System.out.println("<-pos(akt)="+makt);
   while (akt!=null)
   { if (akt.lnf!=null) ls1.add(0,akt.lnf);
     if (akt.rnf!=null) ls1.add(0,akt.rnf);
     makt=ls1.indexOf(akt);
     System.out.println("<-pos(akt,nach nf-add)="+makt);
     if (makt>0) akt=(BB2)ls1.get(makt-1);
     else akt=null;
   }
   System.out.println(" ");
   n=ls1.size();
   lit1=ls1.listIterator(n);
   System.out.println("Hierarchietreue Ausgabe des Baumes");
   System.out.println("::: hp : anz : wort");
   while (lit1.hasPrevious())
   {kn1=(BB2)lit1.previous();
    System.out.println("::: "+kn1.hp+" : "+kn1.wz+" : "+kn1.wo);
    sz=sz+1;
   }
   System.out.println("<> Knotensumme:"+sz);
 }

 static void inorder(BB2 wok)
 { if (wok!=null)
   { inorder(wok.lnf);
     System.out.println("::: "+wok.hp+" : "+wok.wz+" : "+wok.wo);
     inorder(wok.rnf);
   }
 } 
}