BinarySearchTree

[Coppenst]

Guten Tag,
Folgendes Problem beim Implementieren von einem BinarySearchtree:
Aufbau mit einem Interfacepublic interface BinarySearchTree<T> { mit den Eigenschaften:
public interface BinarySearchTree<T> {
public T[] toArray();
public boolean find( T value );
public void insert( T value );
public void delete( T value );
public Iterator<T> iterator();
public Iterator<T> preOrderIterator();
public Iterator<T> levelOderIterator();

Gehen Sie davon aus dass der Typ T das Interface java.lang.Comparable<T>
implementiert. (Dies tun z.B. Integer und Double). Schränken Sie
den Generic Parameter entsprechend ein.
– das Interface BinarySearchTree<T> implementieren.
– Beim zurückgegebenen Iterator sollen Sie einen java.util.Iterator<T>
zurückgeben.
– Des weiteren sollen beide Bäume das Interface java.lang.Iterable<T>
implementieren.

Falls jmd Lösungsvorschläge bzw vorgehensweisen hat , wäre ich sehr dankbar darüber!

 

[VfL_Freak]

Moin,

https://www.google.de/#q=binary search tree java

Da werden doch wohl genug Anregungen dabei sein, oder ???:L

Gruß
Klaus

 

[Coppenst]

Leider liegt die Schwierigkeit ja in den verschieden Implementierungen [ Generic ] und java.util/lang. Für den reinen Baum gibt es ja ziemlich viel aber das ist ja nicht das Problem :bahnhof: aber trotzdem danke

 

[hauptDev]

Da ist doch schon eine Menge vorgegeben, wo kommst du denn nicht weiter?
Wie sieht deine bisherige Implementierung aus?

Schau doch mal in die API bzgl. Comparable<T>:
Comparable (Java Platform SE 7 )

Vielleicht hilft dir die Methodenbeschreibung dort weiter.

 

[Coppenst]

Mit der Implementierung z.b von den Iteratoren rückgabe java.util.Iterator T und das java.lang.IterableT implemenation. Ich verstehe den Aufbau im Code nicht, habe ja schon versucht einen aus google zunehmen und das Generic zumachen. Aber das mit dem Interface hat dann leider auch nicht so geklappt mir fehlt irgendwie das Grundgerüst überhaupt einen funktionierenden code zu erstellen der das erfüllt. Danke schonmal für den link werde ihn mir jetzt mal durchlesen:rtfm:

 

[hauptDev]

Die einzelnen Suchalgorithmen kennst du aber?
Die müsstest du in den einzelnen Methoden implementieren und die Werte zum Beispiel in eine ArrayList (Java Platform SE 7 ) packen. Wie du siehst, liefert dir die Klasse ArrayList bereits eine Methode:

Iterator<E> 	iterator()
Returns an iterator over the elements in this list in proper sequence.

Wenn du immer noch nicht weiterkommst, dann zeig mal was du bisher hast, dann kann man weitere Hinweise geben ;-)

 

[Coppenst]

package tree;

public class BinarySearchTreeNode<T extends Comparable<T>> implements Comparable<BinarySearchTreeNode<T>> {
	private BinarySearchTreeNode<T> left;
    private BinarySearchTreeNode<T> right;
    private T value;
 
    BinarySearchTreeNode(T value, BinarySearchTreeNode<T> left, BinarySearchTreeNode<T> right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
 
    BinarySearchTreeNode(T value) {
        this(value, null, null);
    }
 
    BinarySearchTreeNode<T> getLeft() {
        return left;
    }
 
    void setLeft(BinarySearchTreeNode<T> left) {
        this.left = left;
    }
 
    BinarySearchTreeNode<T> getRight() {
        return right;
    }
 
    void setRight(BinarySearchTreeNode<T> right) {
        this.right = right;
    }
 
    T getValue() {
        return value;
    }
 
    void setValue(T value) {
        this.value = value;
    }
 
    @Override
    public int compareTo(BinarySearchTreeNode<T> o) {
        return value.compareTo(o.getValue());
    }
}

package tree;

public class BinarySearchTree<T extends Comparable<T>> implements Tree<T>  {
	private BinarySearchTreeNode<T> root;
    private int elements;
 
   
    public BinarySearchTree() {
        elements = 0;
        root = null;
    }
 
    @Override
    public void insert(T e) {
   
        insertHelp(root,e);
    }
    
    public void insertHelp (BinarySearchTreeNode<T> binNode, T e){
        if (e == null)
            return;
        if (binNode == null)
        {
            binNode = new BinarySearchTreeNode<T>(e);
            this.elements ++;
        }
        else
        {
            if (binNode.getValue().compareTo(e) == 0)
                return;
            if (e.compareTo(binNode.getValue()) == -1 )
                insertHelp(binNode.getLeft(),e);
            if ( e.compareTo(binNode.getValue()) == 1 )
                insertHelp(binNode.getRight(),e);
        }
    }
 
 
    @Override
    public T find(T e) {
      
        return null;
    }
 
 
    @Override
    public T delete(T e) {
    
        return null;
    }
 
    
 
    @Override
    public Object[] traversePreOrder() {
     
        return null;
    }
 
    
 

    public static <T extends Comparable<T>> BinarySearchTree<T> createTree(
            T[] vals) {
        BinarySearchTree<T> tree = new BinarySearchTree<T>();
        for (T val : vals) {
            tree.insert(val);
        }
        return tree;
    }
 
 
    
    void setRoot(BinarySearchTreeNode<T> root) {
        this.root = root;
    }
 

    BinarySearchTreeNode<T> getRoot() {
        return root;
    }
 
   
    public int getNumOfElements() {
        return elements;
    }
}

Das problem ist einfach das es alles schrott ist :bloed: und ich die aufgabe ende der woche haben muss. Bin da einfach bisschen überfordert aber vielen vielen dank für die bemühungen!

 

[hauptDev]

Also hier wird u.a. dein Problem liegen:

    public void insertHelp (BinarySearchTreeNode<T> binNode, T e){
        if (e == null)
            return;
        if (binNode == null)
        {
            binNode = new BinarySearchTreeNode<T>(e);
            this.elements ++;
        }
        else
        {
            if (binNode.getValue().compareTo(e) == 0)
                return;
            if (e.compareTo(binNode.getValue()) == -1 )
                insertHelp(binNode.getLeft(),e);
            if ( e.compareTo(binNode.getValue()) == 1 )
                insertHelp(binNode.getRight(),e);
        }
    }

Du solltest hier, prüfen, ob die Wurzel "null" ist, wenn ja, solltest du der Wurzel einen neuen Knoten zuweisen.

 

[stg]

Die Probleme fangen schon früher an.

Du sollst eine Klasse schreiben, die einen Binären Suchbaum abbildet. Hierfür soll deine Klasse das gegebene Interface

BinarySearchTree

implementieren. Stattdessen schreibst du aber eine eigene Klasse BinarySearchTree, die das Interface

Tree

implementiert (wo auch immer das herkommen mag). Wieso tust du das? Was ein Interface ist und wie man dieses benutzt weißt du aber, oder fangen hier schon die Probleme an?

Die Iteratoren kannst du (zunächst) einfach ignorieren. Kümmer dich als allererstes wirklich mal darum, dass du Elemente in deinen Baum einfügen, finden und löschen kannst. Eventuelle Rotationen innerhalb des Baumes würde ich zunächst auch einfach mal unter den Tisch fallen lassem.

 

[Coppenst]

Jaa ich muss zugeben, das mein Programm mit den Funktionen Löschen einfügen suchen noch nichtmal funktionieren ;( ja ich weiß alles so schwammig, ich wäre ja einfach schon nur froh darüber eine funktionierenden binärbaum der diese 3 dinge kann! und das natürlich mit den gestellten aufgaben die beachtet werden müssen. Aber ja std du hast es erkannt es hing schon am Interface

 

[hauptDev]

@stg,
da hast du Recht. Das habe ich bewusst vorerst nicht angesprochen, da ich die Implementierung der Funktionalität als Kernproblem betrachtet habe.

@Coppenst,
am Besten du schreibst dir mal mit Stift und Papier auf, wie das Einfügen und Löschen funktionieren soll (evtl. schon einmal grob in der Vorlesung behandelt?). Danach versuchst du es umzusetzen.
Wo gibt es denn jetzt noch konkrete Probleme, wo man dir helfen kann?

 

[Coppenst]

Konkret dann nichtsmehr, ich werde dann erstmal das versuchen. Das war ja unsere Vorlesungsaufgabe umsetzen müssen wir es dann selber. Dann versuche ich das mal Schritt für Schritt aufzuarbeiten vielen dank für die Tipps die mir sicher nochmal helfen werden

 

[dcc]

Hier mal ein Ansatz von mir, vielleicht kannst es gebrauchen
Habe nix großartig getestet und fertig ist es auch nicht.
Rekursion deluxe und vergiss nicht, du musst den Kram auch erklären können sonst hast du abgeschrieben und bekommst ne 5.0 ! Gab bei mir im Studium öfter solche Fälle. Die haben sogar tools um Code auf Ähnlichkeit zu scannen.

Generische Typen schränkst du mit dem extends ein. Brauchst du beim Suchbaum da du ja die Objekte die reinkommen vergleichen können musst um zu wissen ob du links oder rechts lang zu gehen hast. Vergleichen lässt sich alles was das comparable interface implementiert. Dieser Fakt lässt sich hier als Beschränkung nutzen.

Iteratoren schreibe ich mir immer mit "implements iterable". Machst du dies z.B. in meiner Klasse, hast du die public iterator...bla Methode. Diese muss ein eine Instanz einer Klasse zurück geben die Iterierbar ist. Kannst also eine private Klasse machen "private class implements Iterator". Dann musst die next() und hasnext() bauen. next() schaltet auch immer eins weiter, nicht vergessen! Das Resultat der Geschicht, for (E tmp : bla) {} geht auf einmal.

Mein Tip:
Lerne Rekursion wirklich zu verstehen. Druck dir eine Klasse 10x aus und für jeden rekursiven aufruf legst die Seite hin und merkst dir wo du stehen geblieben bist. Beim Abbruch der Rekursion (hier isEmpty()) rollen die Aufrufen von hinten nach vorne zurück. D.h. erst wird die letzte Seite abgearbeitet ab der Stelle wo es stand, wenn fertig dann die vorletzte usw. Das reicht dann alles bis ganz nach vorn durch.

public class MyBinaryTree<E extends Comparable<E>> {
	E head;
	MyBinaryTree<E> left;
	MyBinaryTree<E> right;

	MyBinaryTree() {
		head = null;
		left = null;
		right = null;
	}

	public boolean isEmpty() {
		return head == null && left == null && right == null;
	}

	public boolean add(E item) {
		if (isEmpty()) {
			head = item;
			left = new MyBinaryTree<E>();
			right = new MyBinaryTree<E>();
			return true;
		} else if (head.compareTo(item) == 0) {
			// System.out.println("Duplikat gefunden, breche ab.");
			return false;
		} else if (item.compareTo(head) < 0) {
			// System.out.println("Traversiere links.");
			left.add(item);
		} else {
			// System.out.println("Traversiere rechts.");
			right.add(item);
		}
		return false;
	}

	public boolean contains(E item) {
		if (isEmpty()) {
			return false;
		} else if (head.compareTo(item) == 0) {
			return true;
		}
		return left.contains(item) | right.contains(item);
	}

	public int size() {
		if (isEmpty()) {
			return 0;
		}
		return left.size() + right.size() + 1;
	}

	public void preorder() {
		if (isEmpty()) {
			return;
		}
		System.out.println(head);
		left.preorder();
		right.preorder();
	}

	public void inorder() {
		if (isEmpty()) {
			return;
		}
		left.preorder();
		System.out.println(head);
		right.preorder();
	}

	public void postorder() {
		if (isEmpty()) {
			return;
		}
		left.preorder();
		right.preorder();
		System.out.println(head);
	}

	public boolean remove(E item) {
		if (isEmpty()) {
			return false;
		}

		if (item.compareTo(head) == 0) {
			// Fall 1: Knoten ist ein Blatt, entferne direkt
			if (left.isEmpty() && right.isEmpty()) {
				System.out.println("entferne: " + head);
				head = null;
				left = null;
				right = null;
				return true;
				// Fall 2: Knoten hat ein Kind, setze Kind an seine Stelle
			} else if (!left.isEmpty() & right.isEmpty()) {
				head = left.head;
				left = left.left;
				right = left.right;
				return true;
			} else if (left.isEmpty() & !right.isEmpty()) {
				head = right.head;
				left = right.left;
				right = right.right;
				return true;
				// Fall 3: Knoten hat zwei Kinder:
				// - setze linkesten Knoten im rechten Teilbaum an seine Stelle
				// - oder setze rechtesten Knoten im linken Teilbaum an seine Stelle
				// - verbinde eventuelle dran hängende Knoten mit dem vorherigen
			} else if (!left.isEmpty() & !right.isEmpty()) {
				// TODO
			}
		}
		return left.remove(item) & right.remove(item);
	}

	public int nodeCount() {
		if (isEmpty()) {
			return 0;
		}
		return left.nodeCount() + right.nodeCount() + 1;
	}

	public int deepest() {
		return deepest(0);
	}

	public int deepest(int i) {
		if (isEmpty()) {
			return 0;
		}

		int L = left.deepest()+1;
		int R = right.deepest()+1;

		if (L > R) {
			return L;
		} else {
			return R;
		}
	}
}

public class MyTest {

	public static void main(String[] args) {	
		MyBinaryTree<String> a = new MyBinaryTree<String>();
		a.add("z");
		a.add("b");
		a.add("c");
		a.add("a");
		a.add("d");

		System.out.println(a.nodeCount());
		System.out.println(a.deepest());
	}
}

 

[Coppenst]

Sooo wie ich eben erfahren habe , müssen die Eigenschaften Suchen Finden Löschen Iterativ gebildet werden , damit man Werte bis 1Millionen einfügen können um die Laufzeit zu verkürzen, und bei den Iteratoren irgendwas mit Stacks und Ques bilden. Nun die Frage wie man das Iterative bildet :shock:

 

[dcc]

Iterativ ist viel einfacher, musst nur wissen wie man durch Baumstrukturen manövrieren kann.
Ich mach mal ein kleines Beispiel, das musst du dann erweitern um auch durch den rechten Teil des Baums zu navigieren. Somit kannst du bestimmen wie navigiert wird, und auch deine PreOrder etc. passend ausgeben.

public class MyTest {

	public static void main(String[] args) {	
		MyBinaryTree<String> a = new MyBinaryTree<String>();
		a.add("z");
		a.add("b");
		a.add("c");
		a.add("a");
		a.add("d");

	
		for (MyBinaryTree<String> start=a; start.left != null; start = start.left){
			System.out.println(start.head);
		}
	}
}

oder besser, gleich mit der isEmpty() Methode:

		for (MyBinaryTree<String> start=a; !start.isEmpty() ; start = start.left){
			System.out.println(start.head);
		}

 

[Coppenst]

Super, das habe ich dann jetzt verstanden. Aber was mir nicht klar ist die Iteratoren Pre und lvl order muss ich die irgendwo extra anlegen? Die sind ja in der main, und die Frage ist ja ob es ohne weiteres machbar ist und die andere Frage bei was man Stack und Qeue für die Iteratoren Pre+lvl order verwendet.Hoffe man versteht meine Problemstellung

 

[dcc]

Beim Iterator machst einfach eine "private klasse" innerhalb der hauptklasse.
Die Iterator Methoden (public Iterator<T> preOrderIterator() liefern dann per "return new "private klasse" den Iterator zurück, der preorder etc. ausgibt.
Wirst wohl mehrere dieser Iteratoren (privater klassen brauchen). Hast du die Instanz des Iterators, dann kannst damit den Baum z.B. mit einer for Schleife durchlaufen indem du das wie oben machst, aber start = iterator.next() beim weiterschalten benutzt.

hastnext() und next() musst du natürlich so bauen, dass es die PreOrder oder was auch immer einhält. Dazu musst du wissen wie Preorder funktioniert. bei der remove wirf einfach eine unsupportetexception und gut ist^^

LevelOrder ist iterativ das Einfachste (rekursiv das Schwerste^^). Das ist einfach den Baum zeilenweise ausgeben. Wenn links was ist, gib es aus, wenn rechts was ist gib es aus, sonst gehe ebene tiefer usw.

	private class bla<T> implements Iterator<T>{

		@Override
		public boolean hasNext() {
			// TODO Auto-generated method stub
			return false;
		}

		@Override
		public T next() {
			// TODO Auto-generated method stub
			return null;
		}

		@Override
		public void remove() {
			// TODO Auto-generated method stub
			
		}
		
	}

 

[hauptDev]

Hey,
ist dir denn bekannt wie Queues und Stacks funktionieren? Wenn nicht:
http://wwwiti.cs.uni-magdeburg.de/iti_db/lehre/gif/gif_29.pdf
(ca. die ersten fünf Folien)

Bei dieser Vorgehensweise, wird durch den Baum gegangen und sich die besuchten Knoten in einem Stack gemerkt (push) und beim zurücklaufen (um andere Zweige besuchen zu können) wird der gemerkte Knoten vorherige gemerkte Knoten wieder abgerufen (pop). Die Queue ist dann zum Speichern der Werte in der richtigen Reihenfolge da.

Der grobe Ablauf:
1 laufe so lange nach links bis es nicht weiter geht
2 merke auf dem weg bis dahin alle Knoten im Stack
3 speichere letzten knoten in der Queue
4 gehe nach rechts, wenn möglich + gleicher Ablauf
5 gehe weiter nach oben

So in der Art, eine genaue Implementierung habe ich jetzt nicht.

 

[Coppenst]

Main Klasse

ckage blabla;

public class MyBinaryTree<E extends Comparable<E>>{
	E head;
    MyBinaryTree<E> left;
    MyBinaryTree<E> right;
 
    MyBinaryTree() {
        head = null;
        left = null;
        right = null;
    }
 
    public boolean isEmpty() {
        return head == null && left == null && right == null;
    }
    MyBinaryTree<E extends Comparable<E>> implements BinarySearchTree<T>
    public boolean insert(E item) {
        if (isEmpty()) {
            head = item;
            left = new MyBinaryTree<E>();
            right = new MyBinaryTree<E>();
            return true;
            MyBinaryTree<E> current = this;
            while (true)
            {
                if (...) {
                    current.head = item;
                    return;
                }
                if (...compare...) {
                    current = left;
                } else {
                    current = right;
                }
            }
        }
        return false;
  
 
    public boolean remove(E item) {
        if (isEmpty()) {
            return false;
        }
 
        if (item.compareTo(head) == 0) {
            // Fall 1: Knoten ist ein Blatt, entferne direkt
            if (left.isEmpty() && right.isEmpty()) {
                System.out.println("entferne: " + head);
                head = null;
                left = null;
                right = null;
                return true;
                // Fall 2: Knoten hat ein Kind, setze Kind an seine Stelle
            } else if (!left.isEmpty() & right.isEmpty()) {
                head = left.head;
                left = left.left;
                right = left.right;
                return true;
            } else if (left.isEmpty() & !right.isEmpty()) {
                head = right.head;
                left = right.left;
                right = right.right;
                return true;
                // Fall 3: Knoten hat zwei Kinder:
                // - setze linkesten Knoten im rechten Teilbaum an seine Stelle
                // - oder setze rechtesten Knoten im linken Teilbaum an seine Stelle
                // - verbinde eventuelle dran hängende Knoten mit dem vorherigen
            } else if (!left.isEmpty() & !right.isEmpty()) {
                // TODO
            }
        }
        return left.remove(item) & right.remove(item);
    }
 
    public int nodeCount() {
        if (isEmpty()) {
            return 0;
        }
        return left.nodeCount() + right.nodeCount() + 1;
    }
 
    public int deepest() {
        return deepest(0);
    }
 
    public int deepest(int i) {
        if (isEmpty()) {
            return 0;
        }
 
        int L = left.deepest()+1;
        int R = right.deepest()+1;
 
        if (L > R) {
            return L;
        } else {
            return R;
        }
    }
}
private class bla<T> implements Iterator<T>{
	 
    @Override
    public boolean hasNext() {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public T next() {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
       public void remove() {
        // TODO Auto-generated method stub
        
    }
    
}

Test Klasse

package blabla;

public class MyTest {
		 
	    public static void main(String[] args) {    
	        MyBinaryTree<String> a = new MyBinaryTree<String>();
	        MyBinaryTree<String> b = new MyBinaryTree<String>();
	        a.insert("z");
	        a.insert("b");
	        a.insert("c");
	        a.insert("a");
	        a.insert("d");
	 
	    
	        for (MyBinaryTree<String> start=a; !start.isEmpty() ; start = start.left){
	            System.out.println(start.head);
	            
	            else
	            	(MyBinaryTree<String> start=b; !start.isEmpty() ; start = start.right){
		            System.out.println(start.head);
	            	
	            
	        };
	        }
	    }

Kann man für das Inser iterativ die MyBinaryTree<E extends Comparable<E>> implements BinarySearchTree<T> einfach so verwenden?

 

[dcc]

Klar, du vergleichst ja an der Wurzel ob das einzufügende Element

1. gleich dem aktuellem ist -> breche ab
2. kleiner ist -> gehe links
3. größer ist -> gehe rechts

Das machst so lange bis es keine weiteren Knoten gibt und fügst es dann ganz unten an.
Suchen kannst du praktisch mit fast der gleichen Methode, nur das nix angefügt sondern zurück gegeben wird.

Tja, das ist der Unterschied zum Fachinformatiker und zum Informatik Student. Die Ersteren hätten einfach die TreeSet etc. benutzt und nie kapiert was sich da wirklich tut Dafür weiß der Informatiker hinterher nicht wie TreeSet funktioniert

Aber durchhalten, ab dem 4ten Semester wird es einfacher. Die Grundlagen sind nur heftig.
Und wenn dir ein Ex Diplomer sagt: Diplom > Bachelor, dann sag ihm: Rechne das Vordiplom in deine Noten ein, dann siehst wie viel besser es ist

 

[Barista]

public class BinarySearchTreeNode<T extends Comparable<T>> implements Comparable<BinarySearchTreeNode<T>>

Das ist schon mal falsch, nicht die Node ist Comparable, sondern nur die Elemente darin

public class BinarySearchTreeNode<T extends Comparable<T>>

Weiterhin ist dies eine rekursive Struktur.
Die extra Klasse BinarySearchTree ist also nicht nötig.

Alle Methoden sollten an der Node definiert sein:

public class BinarySearchTreeNode<T extends Comparable<T>> implements BinarySearchTree<T>

Wenn Dir die Sache unklar ist,
solltest Du eventuell eine Skizze
(Klassendiagramm oder so)
machen.

 

[hauptDev]

Bei Erstem muss ich dir Recht geben, wobei ich es nicht für völlig sinnlos erachte, wenn man das Interface implementiert, damit man u.a. Konstrukte wie node.getValue().compareto(node2.getValue()) kürzer schreiben kann.

Die extra Klasse BinarySearchTree ist also nicht nötig.

Nicht? So, steht es aber in den Anforderung (1. Post). Weiterhin finde ich eine BinarySearchTree-Klasse sinnvoll, welche sich um die Verwaltung der Knoten kümmert, welche an sich nur Datenobjekte sein sollen.

 

[Barista]

Ich hatte gar nicht gesehen, dass dieser Thread bereits eine zweite Seite hat,
komisch, dass bei mehreren Seiten auf nicht-letzten Seiten ein Antwort-Textfeld ist.

Bei Erstem muss ich dir Recht geben, wobei ich es nicht für völlig sinnlos erachte, wenn man das Interface implementiert, damit man u.a. Konstrukte wie node.getValue().compareto(node2.getValue()) kürzer schreiben kann.

Ich würde erst mal zusehen, es korrekt hinzubekommen statt schon was abzukürzen.

Zitat:
Die extra Klasse BinarySearchTree ist also nicht nötig.

Nicht? So, steht es aber in den Anforderung (1. Post).

So direkt steht das dort nicht, aber noch so eine Klasse
für die Baumwurzel zu haben, sollte ein sekundäres Problem sein.

Weiterhin finde ich eine BinarySearchTree-Klasse sinnvoll,
welche sich um die Verwaltung der Knoten kümmert,
welche an sich nur Datenobjekte sein sollen.

Wenn Du es rekursiv machen willst,
können die Knoten nicht nur Datenobjekte
sein.

Obwohl Du soweit recht hast,
dass man rekursive Algorithmen
auf der Basis des Sprach-Stack
oder alternativ auf der Basis
eines eigenen Stacks
realisieren kann.

Mit einem eigenen Stack
kannst Du von vornherein Stackoverflows
vermeiden.

Aber ich nehme an, dass dies
nicht im Fokus der Aufgabe steht.

 

[Barista]

Noch ein Einwand:

Wenn Du keine zusätzliche Wurzel-Klasse hast,
kann es keinen leeren Baum geben.

Also ok, mache noch eine BinarySearchTree-Klasse.

 

[Barista]

Ich würde an Deiner Stelle mit Unit-Test (TDD-Style) anfangen.

In der Eclipse kannst Du Dir JUnit-Tests anlegen lassen.

Falls Dir das erst mal zu viel ist,
mache eine Test-Klasse mit main-Methode
und prüfe einfach mit if's

if ( ! condition ) {
    throw new RuntimeException();
}

 

[Barista]

Dann legst Du mit einem leeren BinarySearchTree los:

BinarySearchTree<String> tree = new BinarySearchTree<String>();

if ( tree.find( "A" ) {
    throw new RuntimeException();
}

tree.insert( "A" );

if ( ! tree.find( "A" ) {
    throw new RuntimeException();
}

Damit bekommst Du den Kram wenigstens einigermassen stabil und eine Erweiterung zerstört nicht unbemerkt vorher Erreichtes.

 

[dcc]

Um JUnit würde ich mich nicht drücken, das kommt 100% in späteren Modulen.
Ist auch simpler als die ifs ^^

assertTrue(baum.find("A"));

 

[hauptDev]

Also, so wie ich das sehe, hat der TO überhaupt Probleme mit DIESEM Modul. Also sollte er sich wirklich noch nicht mit zukünftigen Inhalten beschäftigen. Zudem versucht er gerade mit Hilfe von Antworten zweier Java-Communities sich etwas zurecht zufrickeln bis zum Ende der Woche und hat für JUnit bestimmt keine Zeit, da die Basics erst einmal wirklich sitzen sollten. Es gibt so viele Implementierungen in Java im Internet und (u.a.) hier wurde auch schon viel geholfen, keine Ahnung wo man da noch ansetzen soll ohne eine vollständige Lösung zu verraten.

 

[dcc]

Bäume zeichnen, überlegen wie man navigiert für das Iterative.

Für Rekursion 20x die gleiche Methode ausdrucken, für jeden Aufruf ein Ausdruck dazu legen und merken wo man im Code stehen blieb bevor der nächste Aufruf kam. Rekursion ist wie ein JoJo, erst macht es die Kette bis zum Abbruch (hier bis isEmpty()) und rollt dann vom letzten Zettel bis zum ersten zurück.

Man muss nur beim zurück rollen die Abfragen und Ausgaben geschickt platzieren um den gewünschten Effekt zu bekommen. Z.b. die preorder / postorder, kommt nur drauf an an welcher Stelle das System.out erfolgt.

 

[Coppenst]

Jaa ich habe versucht mir überall Information zu besorgen , hoffe das ist erlaubt , also ich hab jetzt einiges lösen können und bin auch relativ weit gekommen. Ich bin nun bei den Iteratoren, und weiß das ich den LvlOrder mit einer Schlange ( Queue ) machen muss und die Preorder mit einem Stack. Die frage wie schaffe ich es den Iterator ( Preorder ) anstatt mit einer ArrayList zumachen welche ich nur so hinbekomme.. als eine Iterator-Klasse? Und die Tipps davor haben einiges gebracht im nachhinein

 

[Coppenst]

Ach genau, wir haben dann doch einiges mehr Zeit bekommen es wurde dann eingesehen das die Aufgabe mehr Zeit in Anspruch nimmt

 

[hauptDev]

Ist das denn an sich verboten eine ArrayList zu nehmen? Ich meine irgendwo muss man die Reihenfolge ja speichern.
In der API nachsehen ist immer eine gute Idee:
[JAPI]ArrayList[/JAPI]

Wie du siehst, wird dir von der ArrayList bereits eine Methode iterator() geboten, die dir einen Iterator zurückliefert. Den könntest du bei deinen Methoden dann einfach weiterreichen.

[TIPP]Auch andere Klassen vom Typ Collection erben und überschreiben üblicherweise die Methode iterator(), also auch z.B. die Queue[/TIPP]

 

[dcc]

Nix ArrayList. Im Studium programmiert man die ArrayList selbst, die man dann nutzen kann
Das ist ja der Zweck der Sache, man soll lernen wie Java funktioniert, nicht wie man es verwendet.

 

[hauptDev]

Jaja, kenn' ich ja. Hab' ich schon selber hinter mir. Aber wenn es jetzt um Trees geht, kann man doch Listen schon voraussetzen oder nicht? Normalerweise kommen die nämlich vorher dran ;-D

 

[Coppenst]

Ich bin doch erst am Anfang, ich will es ja lernen :lol: Rom wurde auch nicht an einem Tag erbaut ueh:! Ja das verstehe ich und Verboten ist es nicht eine ArrayList zu verwenden.. ich wüsste aber zugern ob es einen anderen weg geht einen Stack Iterativ als Klasse zu machen auch wenn ich es evtl nicht gleich verstehen würde

 

[dcc]

Du brauchst für Bäume halt eine verschachtelte Struktur und Listen in Java sind sowas.
Eine Liste kannst auch bauen indem du:

		LinkedList<String> a = new LinkedList<String> (new LinkedList<String> (new LinkedList<String> (new LinkedList<String> ())));

usw. machst. Bäume haben dann mehrere Listen die in einer Liste drin stecken.