Binärbaum prüfen, ob sortiert oder unsortiert

[speedle]

Hallo,

wie überprüfe ich am einfachsten, ob ein Binärbaum sortiert oder unsortiert vorliegt?
Also ich habe bereits Bäume erstellt mit Wurzel sowie linken + rechten Ästen. Und am einfachsten erscheint mir mittels der Infix Ordnung zu überprüfen, ob er (un)sortiert ist, hier muss nämlich der vorhergehende Datenwert immer kleiner sein als der darauffolgende.
Oder gibt es noch ne elegantere Lösung und wie setze ich diese am geschicktesten in einer boolean Methode um?

Gruß

 

[Ziegenpeter]

Nunja, du solltest schon wissen wie du den Baum traversieren willst um festzustellen ob er sortiert ist. Jede Traversierung liefert dir mitunter andere Ergebnisse zurück. Außerdem macht das Ganze auch nur Sinn wenn du dir im Klaren über die Implementierung des Baumes und speziell seines insert-Verhaltens bist. Balanciert sich der Baum z.B. selbst aus beim Einfügen, kannst du dir die Methode sparen und annehmen es sei nicht sortiert.

Wenn InOrder-Traversierung das Mittel der Wahl ist hast du ja schon selbst beschrieben wie man's macht. (wobei du drauf achten solltest, dass du's dir richtig vorstellst. Bei InOrder würde dann gelten: linkes_Kind <= parent <= rechtes Kind) Ansonsten wüsste ich keine gescheitere Methode.

 

[speedle]

Also auf den Baum selbst werden alle 3 möglichen Ordnungen ausgegeben.
Ich weiss aber leider nicht, wie ich nun am geschicktesten vorgehe, um mir eine boolean Methode zu basteln, die mir mitteilt, ob der Baum sortiert ist oder nicht. Angelegt wird der baum einmal händisch und dann wird nichts mehr geändert!

 

[Ziegenpeter]

Ja, das du den Baum in In-, Pre- und PostOrder traversieren kannst ist mir klar.

Worauf ich nur hinauswollte ist, dass es nicht viel Sinn macht einfach mal in irgendeiner Weise zu prüfen ob der Baum sortiert ist oder nicht, wenn man nicht weiß was man erwartet oder wie er sortiert sein soll.

Ansonsten hast du ja schon alles gesagt. Du legst dir eine Variable an, die dir das letzte Element anzeigt und gehst InOrder durch. Dabei updatest du immer diese Variable.

Du kannst es ja erstmal probieren und wenn du nicht weiterkommst einfach einen Ansatz hier posten.

 

[speedle]

Hallo,

mein Problem liegt jetzt darin, dass ich net zu 100% weiss, ob er das alte Datenelement zwischenspeichert oder sich gleich das nächste schnappt?

public boolean sortiert(){
			if (left != null)
				left.sortiert();
			int temp = data;
			if(temp < data)
				return true;
			if (right != null)
				right.isSorted();
			return false;
		}

Jetzt spuckt er mir immer false aus. Der Fehler liegt sicherlich im Abgleich aktueller Datenwert mit altem Datenwert!?

 

[Ziegenpeter]

Nun, dass immer false zurückgegeben wird ist ja klar. Du erstellst eine Variable die nur innerhalb der Methode sichtbar ist. Effektiv vergleichst du im zweiten if ob data < data ist und das ist natürlich immer falsch.

Ich geb' dir mal 'ne Methode, die auf deiner beruht:

int temporaryValue = Integer.Min_Value; //global deklarierte Temp-Variable
...
public boolean isSorted(){
            boolean res = true;
            if (left != null)
                res = res && left.isSorted();
            res = res && (temporaryValue <= data);
            temporaryValue = data;
            if (right != null)
                res = res && right.isSorted();
            return res;
        }

Diese Lösung bietet dir noch Möglichkeiten dir Gedanken zu machen, da es bewusst keine optimale Lösung ist, sie wohl aber funktionieren wird (ungetestet aufgrund der Uhrzeit).
Das <= ist für die Funktionalität in einem besonderen Randfall wichtig (welcher Fall ist das?), macht allerdings nichts kaputt da ja Werte ruhig doppelt vorkommen dürfen (oder nicht?).
Ansonsten wird dieses Ergebnis genau dann falsch, wenn mindestens ein Vergleich falsch geliefert hat.

 

[Ziegenpeter]

Im Eifer des Gefechts hab' ich natürlich einen Fehler gemacht. Die temporaryValue müsste natürlich static sein, sonst klappt es nicht.
Also statt

int temporaryValue = Integer.MIN_VALUE;

muss es:

static int temporaryValue = Integer.MIN_VALUE;

heißen. Diese Lösung erfordert aber ein zurücksetzen der Variable vorm nächsten prüfen, aber ich sagte ja schon, dass ich keine optimale Lösung geben wollte da du auch noch ein wenig nachdenken darfst.