Traversieren von Bäumen

[Nirvana]

In meinen Vorlesungsbuch habe ich ein Bspfür: mit In-order einen Baum zu durchgehen

Gerüst

public class Knoten<T> {
 
    public Knoten<T> links;
    public Knoten<T> rechts;
    public T inhalt;
 
    public Knoten(T elem){
        inhalt = elem;
        links = null;
        rechts = null;
    }
    public Knoten(T elem, Knoten<T> links, Knoten<T> rechts){
        inhalt = elem;
        this.links = links;
        this.rechts = rechts;
    }
}

Nun Klasse BinaerBaum erstellt:

public class BinaerBaum<T>  {
    public Knoten<T> wurzel;
    public Binaerbaum(){
   
    }
    public Binaerbaum(Knoten<T> wurzel){
        this.wurzel = wurzel;
    }
}

Die Methode, die mir schwierigkeiten bereitet

inOrder(BinaerBaum<T> baum) {
rekInOrder(baum.wurzel);
}
rekInOrder(Knoten<T> knoten) {
rekInOrder(knoten.links);
process(knoten.inhalt);
rekInOrder(knoten.rechts);
}

Ich verstehe die rekInOrder - Methode nicht. der ruft doch immer am anfang die methode für den knoten links davon auf.. bis es irgendwann keinen knoten mehr gibt?

 

[SlaterB]

so wie es aktuell programmiert ist, gibt es kein 'bis', der Code wird nicht gut funktionieren,
ausprobieren ist erlaubt

Internetsuche nach rekInOrder(Knoten<T> knoten) liefert eine andere Klasse mit

 void rekInorder(Knoten<T> k, ArrayList<T> ml){
        if (k != null){
           rekInorder(k.links, ml);
           ml.add(k.inhalt);
           rekInorder(k.rechts, ml);
      }
  }

das sieht schon besser aus, da gibt es Abbruch

 

[Nirvana]

Ja ich hab die Methode vergessen:

void process(T elem){
System.out.println(elem.toString());
}

Naja es wurde vom Professor geschrieben, ich hab sie nicht ausprobiert da ich ja weiß was die Methoden machen sollen, also neme ich die Richtigkeit an.
Trotzdem habe ich es hierreingeschrieben, weil mir die Methode rekInOrder nicht klar ist.

Aber gehört da wirklich nur ein if vorne dran für eine Abbruchbedingung.

Die Methode ruft sich aber trotzdem immer selber auf bez des linken Kinder-Knotens, aber wird dann der inhalt ausgegeben der Knoten von unten nach oben`??

 

[SlaterB]

male dir einen Baum auf Papier auf, male in jeden Knoten eine Zahl, in der Reihenfolge wie sie dran kommen,
erst geht es nach ganz links unten, das ist richtig, dann wird dort als process() ausgeführt, richtig,
und was passiert danach?

wenn dir das Aufmalen zu schwierig ist oder eben auch mit Fehlern zu rechnen ist,
dann gibts ja immer noch Java, dafür wurden Computer schließlich erfunden,
lasse das Programm ablaufen, gib die Schritte aus, schaue dir an was bei process() ankommt,

das sind ja alles nachvollziehbare Prozesse, nichtmal die häufige Frage 'was ist zu tun [bei noch leerem Programm]?',
etwas unnötig hier im Forum zu diskutieren, was passieren wird, wenn man es auch direkt anschauen kann, oder?

 

[Nirvana]

Ich würde trotzdem gerne eine ABsicherung von dir noch bekommen

erst geht es von der Wurzel nach ganz links unten dann wird dort process() ausgeführt.
dann wird geschaut ob dieser ein GeschwisterKnoten hat, wenn wird die Methoden mit diesen aufgerufen,wenn dies keinen linken Kinderknoten hat wird der inhalt ausgegeben.

ALso wird es diagonal von links unten nach rechts oben abgearbeitet.

Stimmt das so erklärt?

Nun habe ich noch eine Frage bei Post-order:

postOrder(BinaerBaum<T> baum) {
rekPostOrder(baum.wurzel);
} rekPostOrder(Knoten<T> knoten) {
rekPostOrder(knoten.links);
rekPostOrder(knoten.rechts);
process(knoten.inhalt);
}

Hier geht man genauso von der Wurzel nach ganz links unten. Und dann in der selben Ebene nach ganz rechts oder wie?

 

[SlaterB]

> Stimmt das so erklärt?

ich kann in den inhaltlichen Sätzen nichts falsches erkennen,
ob damit alles abgedeckt ist und der wahre Sachverhalt korrekt beschrieben ist, ist für mich dabei nicht sicher,

"diagonal von links unten nach rechts oben" ist zugespitzt völlig offene Interpretation, von mir nicht zu beurteilen,
edit: ein entarteter Baum Marke "\", nur mit rechten Nachfolgern, muss und wird auch bearbeitet

die Frage von Pre, In, Post ist vor allem, wie bei drei Knoten, Wurzel + linker + rechter Nachfolger, die Reihenfolge ist,
Pre-, In-, Post-Order
daraus ergibt sich der Rest automatisch

> Und dann in der selben Ebene nach ganz rechts oder wie?

das ist nachweislich falsch, es geht immer nur um Teilbäume, eine ganze Ebene kann nicht direkt bearbeitet werden

 

[Nirvana]

Ich verstehe trotzdem nun nicht wie in PostOrder die Knoten abgearbeitet werden, da die Methode, die den Inhalt des Knoten ausgibt am Ende steht. Könntest Du mir diese vlt kurz erklären?

LG

 

[SlaterB]

wie gesagt sträube ich persönlich mich, es rein zu erklären, wenn du es nicht selber vorher bearbeitest, was hier nun wirklich möglich ist,
die Gedankengänge sind schon eine Hälfte und löblich, die zweite Hälfte ist aber, aktiv ein Beispiel durchzugehen,

auf Papier mag genau das herauskommen was du sowieso schon denkst, wobei die tatsächliche Arbeit schon manches korrigieren kann,
das Programm zeigt schließlich genau, ob es stimmt oder nicht bzw. bei gar keiner Vorstellung mehr (Ebene habe ich ausgeschlossen) den tatsächlichen Ablauf


ich will nicht nur mir Arbeit einsparen (diese Postings hier dauern schon länger), sondern sehe das als den einzigen Weg zum Lernen,
langfristig spare ich vielleicht durch weniger Folgefragen zu anderen Themen

"Gib einem Mann einen Fisch ..."

 

[Nirvana]

Ich habe eine mündliche Prüfung deshalb behaare ich auf das Erklären, denn wenn ich das Programm ausführe, dann sehe ich nicht richtig wie es die Methoden durchgeht. Und ein Satz eklärung würde mir eben helfen.ich bitte darum

LG

 

[SlaterB]

> dann sehe ich nicht richtig wie es die Methoden durchgeht.
zeige das Programm, zeige inwiefern es nicht eindeutig ist, an welcher Stelle ist genau was unklar?

aber um auf den vorherigen Link zurückzukommen
Pre-, In-, Post-Order
da steht es ja schon drin:
post-order: linker Teilbaum, rechter Teilbaum, Wurzel

was gibt es mehr zu sagen? es geht nach links, es geht nach rechts, dann das eigene Element,
ich könnte jetzt natürlich einen Baum über 5 Ebenen mit 7 Zweigen malen und die Reihenfolge aller Elemente untereinander aufzählen,
aber darauf ist nun wirklich ewig zu warten

noch nicht ein Beispielbaum ist bisher hier zur Besprechung von dir vorgelegt,
das ist eben die einfache Fleißarbeit auf dem Weg zur Erkenntnis

 

[hüteüberhüte]

Du hattest ein ähnliches Thema bereits hier: http://www.java-forum.org/java-basics-anfaenger-themen/139731-binaerbaum-implementierung.html

Darin wurde auch schon pre-, post- und inorder besprochen