Datastrukturer & Algoritmer, Datalogi C

Henning Christiansen 30/10-2001

Opgave til forelÊsningen 29/10-2002

F¯lgende opgave, som ogs er afleveringsopgave for dat Cπerne; afleveringsfrist fredag d. 15. november. Opgaven kan mÂske tage lidt lÊngere tid end de ¯vrige, da der skal eksperimenteres lidt for at f den grafiske side til at makke ret, men burde ikke vÊre voldsomt svÊr at l¯se p det principielle plan. I¯vrigt er der ingen forelÊsning 5/11, s der skulle vÊre tid nok.

Opgaven handler om at tegne binÊre s¯getrÊer, og man skal benytte de grafiske primitiver, som ogs er blevet brugt i programmet ≤drawRuler≤ side 247 i bogen (plus et par stykker mere, som forklares nedenfor); programtekst med hovedprogram kan findes via link p kursushjemmesiden.

Om binÊre s¯getrÊer:

Der er lavet en tilpasning af bogens binÊre s¯getrÊer (afsnit 19.1), s de ogs har de metoder, som blev beskrevet i kapitel 18 for ≤almindelige≤ binÊre trÊer.

Du skal have f¯lgende filer i dit arbejdskatalog, og du skal compilere dem i den rÊkkef¯lge de fremgÂr her:

DuplicateItemException.java

ItemNotFoundException.java

UnderflowException.java

Stack.java

Queue.java

ArrayStack.java

ArrayQueue.java

BinaryNode.java

BinarySearchTree.java

TestTreeIterators.java

Det er modificerede udgaver af filer (≤fra bogen≤), og du kan finde dem i kataloget

draw_tree_files

som du kan finde link til p kursets hjemmeside. Hvis problemer, s sp¯rg Lars Mogensen.

Programstruktur som kan bruges til opgaven:

Her f¯lger et skelet du evt. kan bruge til at strukturere dit program efter.

import java.awt.Frame;

import java.awt.Graphics;

import java.awt.Color;

public class TreeDraw extends Frame

{ private static final int theSize = 500;// konstant som benyttes nedenfor;

private static BinarySearchTree theTree = new BinarySearchTree();

// Man SKAL definere en πpaintπ metode; som s p magisk vis

// aktiveres af πshowπ nedenfor

public void paint( Graphics g )

{ setBackground( Color.white );

g.setColor( Color.red ); // den farve der tegnes og skrives med

// Her kan du kalde din egen tegnemetode med theTree som argument

}

// private void ... dine tegnemetoder.

// For simplicity, must terminate from console with a control-c

public static void main( String [ ] args )

{ Frame f = new TreeDraw( ); // det her skal der alts bare stÂ

f.setSize( theSize, theSize); // det her skal der alts bare stÂ

//Initialiser et trÊm f.eks.:

theTree.insert(new Integer(55));

theTree.insert(new Integer(35));

theTree.insert(new Integer(88));

theTree.insert(new Integer(40));

theTree.insert(new Integer(20));

theTree.insert(new Integer(45));

theTree.insert(new Integer(117));

// denne her skal bare kaldes, og s kommer din tegning ud p skÊrmen :)

f.show( );

}

}

Om de grafiske primitiver:

Vi kan beskrive den tegneflade, vi arbejder indenfor, ved et koordinatsystem med en X-akse, som peger den vej fra venstre mod h¯jre og en Y-akse som peger nedefter og med punktet (0,0) i ¯verste venstre hj¯rne. I Mac-versionen (mÂske ogs p PC) er der i¯vrigt den underlige egenskab at Y-aksen starter med at tÊlle i den bjÊlke, som er p vinduet, s hvis man sÊtter en prik i (117, 0) kan man ikke se den, mens en prik i (117,50) kan ses i den ¯verste del af vinduet.

Til at l¯se opgaven er der brug for f¯lgende metoder:

g.drawString(String str, int x, int y)

g.drawLine(int x1, int y1, int x2, int y2)

hvor ≤g≤ er et Graphics-objekt (se hvordan der er brugt i bogens programmer).

Den f¯rste udskriver en streng (men kan ogs godt finde ud af tal), s det nederste venstre hj¯rne af ≤billedet≤ svarende til strengen ligger i punkt (x,y). F.eks. svarende i foden af Pπet i ≤Pilsner≤. Metoden drawLine tegner en streg mellem (x1,y1) og (x2,y2).

Endelig har vi brug for at skifte farve, og skal man f.eks. skrive noget i en anden farve end resten af tegningen, skal man 1) skifte farve, 2) skrive, og 3.) skifte farven tilbage. F.eks. sÂdan her,

g.setColor( Color.green );

g.drawString(≤Pilsner≤), 100, 100);

g.setColor( Color.red );

hvis vi aktuelt tegner med r¯dt og vil skrive en enkelt gr¯n streng.

Nu kommer opgaven ã Sp¯rgsmÂl 1

Skriv en f¯rste version af et program, som tegner et binÊrt s¯getrÊer p skÊrmen, s det s nogenlunde ligger midt i vinduer, og vi ≤drejer≤ blot lige meget til h¯jre og venste, nÂr vi gÂr ned i et deltrÊ. Det kan illustreres sÂledes for vort eksempeltrÊ:

Sp¯rgsmÂl 2

Men hvis trÊet er st¯rre opstÂr der et problem, da knuder fra forskellige grene vil blive tegnet over i hinanden. Vi bliver n¯dt til at udstyre vores tegnemetode med et bredde-argument. Det optimale ville nok vÊre at skrive en metode, som beregner bredden af et trÊ, men vi kan n¯jes med at benytte den eksisterende h¯jdemetode. Vi bruger s h¯jden som udgangspunkt for et startvÊrdi for hvor meget grenene skrÊver og halverer (eller noget deromkring) i hvert skridt.

TrÊet skulle nu gerne komme ud noget i denne her retning:

Sp¯rgsmÂl 3

I vores hackede udgave af binÊre s¯getrÊer kan vi risikere at et fejagtigt program kan modificere trÊet, sÂledes at den definerende egenskab for binÊre s¯getrÊer (hvilken?) ¯delÊgges. F.eks. hvis det trÊ vi har brugt hidtil udsÊttes for f¯lgende:

theTree.getRoot().right.element=new Integer (52);

Udvid dit program, s det fremhÊves p tegningen, hvor der er problemer i trÊet, ved i stedt for at bruge farven bl til tallet at benytte farven sort. For det modificerede trÊ fÂr vi f¯lgende billede:

(Hvis du ikke kan se farverne, s er 52 sort og de ¯vrige tal blÂ).

Sp¯rgsmÂl 4 (kun for specielt interesserede perfektionister)

S¯rg for, at knuden fremstÂr som en kasse med afrundede hj¯rner med tallet inden i, og s grenede ned til undertrÊerne rammer disse kasser perfekt.