Datalogilaboration 6 - Binära träd med strängar

Laborationens tema är binära sökträd och uppgiften är att bygga upp ett sökträd från en fil med svenska ord, spotta ut dubbletter, söka efter skenbart svenska ord in en engelsk ordfil och skriva ut dom, dock endast första förekomsten av varje svenskt ord. Redan funna ord sparas i ett annat sökträd, och dom båda sökträden är objekt.

Ett sökträd med ordlista

I filen BinarySearchTree.java ska du programmera en kraftigt bantad version av den class BinaryNode som finns i lärobokens fig 18.5, nämligen följande.
    class BinaryNode{
        String word;
        BinaryNode left = null, right = null;
    }
Efter den ska du skriva class MiniTree som en groteskt nedbantad version av fig 18.6-18.10, nämligen följande.
class MiniTree {
    static BinaryNode root = null;
    static void insert(String x) {
        - - - ;
    }
    static BinaryNode insert(String x, BinaryNode t) {
        - - - ;
    }
    public static void main(String[] args) {
        - - - ;
    }
}
Idéer till det första utelämnade avsnittet kan du få från fig 18.6, till det andra från fig 18.10. I stället för satsen throw DuplicateItem ska du helt enkelt skriva ut dubbletten på skärmen.

I main ska du slutligen med en enda sats läsa in hela filen /info/kurser/datalogi_e01/labbar/word3.txt i trädet. Enklast blir det om man startar programmet med kommandot

    java MiniTree < word3.txt
Om du gjort rätt kommer dom dubblettord som spottas ut att bilda ett viktigt budskap.

Två binära sökträd som objekt

Nu ska du skriva en riktig public class BinarySearchTree, som du kan ha glädje av hela livet! Kopiera klassen MiniTree, men gör följande förbättringar.
  1. Alla static tas bort, så att flera träd kan skapas med new BinarySearchTree().
  2. Hela main() tas bort.
  3. Den booleska metoden exists skrivs. Den har en parameter, nämligen ett ord, och den returnerar true om ordet finns i trädet, annars false.
Testprogrammet för din färdiga sökträdsklass kan ligga i samma fil, men ska heta class TestTree. Det ska som tidigare börja med att läsa in ordlistan i trädet, men nu måste man först skapa ett trädobjekt, exempelvis kallat ordträd. Filläsningen ska ske på det krångliga sätt som beskrevs i föreläsning 4 (BufferedInputStream - - -).

Den här gången ska programmet ha startats med kommandot

    java TestTree < engelska.txt
Filen engelska.txt finns på kursbiblioteket och innehåller en kortare engelsk text som ditt program ska läsa ord för ord, kolla om ordet finns i ordträdet och i så fall skriva ut det. Om ett ord finns flera gånger ska bara dess första förekomst skrivas ut. Därför måste du skapa ett nytt tomt träd, exempelvis oldwords, och spara alla funna ord i detta träd.

Om du har gjort rätt kommer dom utskrivna orden att bilda ännu ett hemligt budskap! När du mottagit det kan du försöka få underskrift av en lärare.

Genialt programmerat av ..................................... anser.............................. den .................


^ Upp till kurssidan.


Sidansvarig: <efo@nada.kth.se>
Senast ändrad 21 januari 2002
Tekniskt stöd: <webmaster@nada.kth.se>