hægtede lister og binær træer

Et binært træ kan defineres som:

Node(Node left, Node Right)

rekursiv definition - så dit andet spørgsmål.. :-)

Altså start med en rod. Roden har et left og et right child. Left og right child til roden kan så igen have hver deres left og right child.

En hægtet liste (linked list) er en række elementer der hver peger på forgående og efterfølgende element.

Element(Element prev, Element next, Object value)

I forreste Element peger prev på null
I sidste Element peger next på null

Det spørgsmål er lidt større end dine andre spørgsmål !

Her er et eksempel på et binært træ:

package bt;

import java.util.*;

public class BinaryTree {
    private Element root;
    public BinaryTree() {
        root = null;
    }
    public void insert(String data) {
        if(root==null) {
            root = new Element(data);
            root.setParent(null);
        } else {
            root.insertChild(data);
        }
    }
    public boolean isPresent(String data) {
        Element curr = root;
        while (curr != null) {
            int cmp = curr.getData().compareTo(data);
            if (cmp == 0) {
                return true;
            } else if (cmp > 0) {
                curr = curr.getLChild();
            } else if (cmp < 0) {
                curr = curr.getRChild();
            }
        }
        return false;
    }
    public List find(String startdata) {
        List res = new ArrayList();
        root.find(startdata, res);
        return res;
    }
    public String toString() {
        return root.toString();
    }
}

class Element {
    private String data;
    private Element parent;
    private Element lchild;
    private Element rchild;
    public Element(String data) {
        this.data = data;
        parent = null;
        lchild = null;
        rchild = null;
    }
    public void setParent(Element parent) {
        this.parent = parent;
    }
    public void setLChild(Element lchild) {
        this.lchild = lchild;
    }
    public void setRChild(Element rchild) {
        this.rchild = rchild;
    }
    public String getData() {
        return data;
    }
    public Element getLChild() {
        return lchild;
    }
    public Element getRChild() {
        return rchild;
    }
    public String toString() {
        StringBuffer res = new StringBuffer("");
        if(lchild!=null) {
            res.append(lchild.toString());
            res.append(" ");
        }
        res.append(data);
        if(rchild!=null) {
            res.append(" ");
            res.append(rchild.toString());
        }
        return res.toString();
    }
    public void insertChild(String data) {
        int cmp = this.data.compareTo(data);
        if(cmp == 0) {
            return;
        } else if(cmp > 0) {
            if(lchild == null) {
                lchild = new Element(data);
                lchild.setParent(this);
            } else {
                lchild.insertChild(data);
            }
        } else if(cmp < 0) {
            if(rchild == null) {
                rchild = new Element(data);
                rchild.setParent(this);
            } else {
                rchild.insertChild(data);
            }

        }
    }
    public void find(String startdata, List res) {
        if(data.startsWith(startdata)) {
            res.add(this.data);
        }
        if((lchild != null) && (data.compareTo(startdata) > 0)) {
            lchild.find(startdata, res);
        }
        if((rchild != null) && (data.compareTo(startdata + "zzz") < 0)) {
            rchild.find(startdata, res);
        }
    }
}

Java kommer med en LinkedList, så den vil man normalt ikke implementere.

En hægtet liste er glimrende til bruge i en Stack eller Queue struktur.
Der har man jo netop kun brug for at kunne accesse første og sidste element.

På næste semester vil jeg råde dig til at følge lidt med i timerne, det kan spare dig for en frygteligt masse besvær til eksamen :-)

Held og lykke

Til Disky, ja - det er nok rigtigt...:-)

Til Arne - alt det kode du har lagt ind - har ikke nogen main-metode??

Nej - den ligger i en separat klasse.

Vil du gerne have et test hoved-program ?

Meget simpelt eksempel:

package bt;

import java.util.*;

public class Test3 {
    public static void main(String args[]) {
        BinaryTree bt = new BinaryTree();
        bt.insert("Brøndby");
        bt.insert("FCK");
        bt.insert("AAB");
        bt.insert("OB");
        bt.insert("AGF");
        System.out.println(bt);
    }
}

ja, tak det vil jeg gerne have..

Og med brug af isPresent:

package bt;

import java.util.*;

public class Test3 {
    public static void main(String args[]) {
        BinaryTree bt = new BinaryTree();
        bt.insert("Brøndby");
        bt.insert("FCK");
        bt.insert("AAB");
        bt.insert("OB");
        bt.insert("AGF");
        System.out.println(bt);
        System.out.println("Er OB i træet ? " + bt.isPresent("OB"));
        System.out.println("Er Nørre Snede i træet ? " + bt.isPresent("Nørre Snede"));
    }
}

Hej Arne, Den giver mig følgende fejlmedl. - når ejg kører Test3
cannot resolve symbol
symbol  : class BinaryTree 
location: class bt.Test3
        BinaryTree bt = new BinaryTree();

altså den første version af din test3

De virker godt nok, men lad mig gætte - du plejer ikke at bruge
package ?

Prøve bar eat slet linien:

package bt;

i begge filerne !

nej, har aldrig set det før...Hvad er det?

jeg kan se at den "omdøber" min klasse.... location: class bt.Test3

Det er en måde at prefixe klassenavne på.

Fuldstændigt ligesom java.util.ArrayList aå hedder den her bt.Test3.

Men for at det virker skal du have dem i et directory ved navn bt og
din classpath skal pege på det directory som bt directory ligger i - ikke
bt directory.

Meget interessant.

Men hvis du bare vil køre programmet så slet de linier.

hey, nu fungere det...lækkert
Skal man virkelig bruge alle klasserne og metoderne - for at køre det "lille" superliga eks. igennem?

Kunne du evt. ikke forklare hægtede lister på samme måde... det er ret effektivt... håber jeg :-)

Der er så meget kode fordi det hele er hjemme-lavet d.v.s. ikke bruger
et binært træ der kommer med java.

import java.util.LinkedList;

public class LinkedListTest {
    public static void main(String[] args) {
        LinkedList ll = new LinkedList();
        ll.add("1");
        ll.addFirst("2");
        ll.addLast("3");
        for(int i = 0; i < ll.size(); i++) {
            System.out.println((String)ll.get(i));
        }
        System.out.println(ll);
        ll.removeFirst();
        System.out.println(ll);
    }
}

Hej Arne... Ganske neat kode i dit binære træ, men er der ikke en anden løsning end:
if((rchild != null) && (data.compareTo(startdata + "zzz") < 0)) {
            rchild.find(startdata, res);
        }
Tænker her på "zzz"

Jo - du kan også tage det sidste bogstav i startdata og ligge en til.

Hvis du søger på abc kan du i.s.f. abczzz bruge abd.

Du skal bare have noget der markerer en slutning på et interval.

Kode stumpen er iøvrigt oprindeligt lavet til et andet spørgsmål.

Og resten af koden går tilbage til et tredie spørgsmål.

Hvis man bruger zzz er der iøvrigt et potentielt problem med danske
bogstaver.

Rart at man kan genbruge *GG*

Har i øvrigt lige lagt et debatindlæg på den "fri" - hvad syntes du?
http://www.eksperten.dk/spm/364859

Inbox lyder som en god ide.

Chat er muligvis også en god ide, men jeg ville ikke selv bruge et
chat forum.

Ahh... skulle lige finde ideen med koden... Har jeg ret når jeg deducerer at koden finder alle forekomster??

Hmm... svarer lige selv... en hurtig gennemgang af koden synes at antyde at en node som allerede eksisterer blot overskrives (ellers blot ignoreres). Dermed har jeg misset forståelsen af de tre z'er :-(

Det er korrekt at insert ikke gør noget hvis noget allerede er der d.v.s.
at hver string kun er en gang træet.

isPresent er en normal test på om en string er i træet.

find er en speciel metode som finder alle strings i træet der
starter med noget bestemt.

Eksempel:

man skal finde alle string i træet der starter med "for"

metoden find finder så alle strings fra "for" til "forzzz" (eller "fos").

Hvis du leder efter strings der starter med "for" og du står på
en node "fora", så kan der godt være nogle match ud af højre grenen,
men hvis du står på "fox", så kan der ikke være nogle match ud af
højregrenen.

Skillelinien går ved forzzz/fos.

Haaaar det, ganske smart! Og anvendeligt hvis man som nogen (Læs: DØK 1. år eksamensopgave - de har afleveret) skal lave en app. som reagerer på en brugers input og kommer med forslag til ord der passer på hans hidtil indtastede! Eks. brugeren har tastet 'be' og app. foreslår 'bedre', 'bedring', 'benzin' etc...