Binärbaum sortiert ausgeben

[lowterm]

Hi,

ich stehe vor einem Problem, das ich seit Stunden nicht lösen kann.
Ich muss einen AVL-Baum(Binär) sortiert augeben, wobei möglichst
wenige Knoten der Baumes durchlaufen werden sollen.

Die Sortierung habe ich ganz schnell hinbekommen, wie kann ich aber
dafür sorgen, dass möglichst wenige Knoten der Baumes durchlaufen werden?

Hat jemand da eine Idee. Für jede Hilfe bin ich dankbar.

Danke im Voraus. :bahnhof:

 

[lowterm]

Hi,

das ist auch der Quelltext, was das ganze sortiert.

public String sortieren(Knoten einKnoten, String text){
  if(einKnoten.getKnotenLinks() != null && einKnoten.getKnotenLinks().getSchluessel() < rootKey)
      text = sortieren(einKnoten.getKnotenLinks(), text);
  		
    text += einKnoten.getSchluessel() + " " + einKnoten.getBezeichnung() + "\n";

    if(einKnoten.getKnotenRechts() != null)
       text = sortieren(einKnoten.getKnotenRechts(), text);
   
   return text;
 }

Gruß

 

[Hilefoks]

Wenn du einen binären Baum InOrdner ausgibst, dann ist diese Ausgabe sortiert und jeder Knoten wird nur einmal besucht. Und fast genau das hast du programmiert. Nur deine erste if-Abfrage macht zu viel - aussreichend ist diese:

if(einKnoten.getKnotenLinks() != null) 
      text=sortieren(einKnoten.getKnotenLinks(), text);

Zudem solltest du den "String text" durch einen StringBuilder oder StringBuffer ersetzen. Mit diesen beiden Änderungen ist dann nicht nur die Anforderung "möglichst wenige Knoten der Baumes durchlaufen" erfüllt (das ist sie schon), sondern dein Code ist dann auch, an dieser Stelle, nahezu perfekt.

MfG,
Hilefoks

 

[lowterm]

Hi,

vielen Dank für deine Antwort.

Du willst etwa nicht sagen, dass ich gestern stundenlang für nichts meine Zeit vergeuden
habe, obwohl die Lösung schon da war

Naja, soweit muss auch kommen, dass man vor lauten Bäumen den Wald nicht sehen kann,
wenn man wegen Müdigkeit kaum denken kann.

Ich war nicht so sicher, weil mein Prof. sagte, dass ich noch diese Anfordeung erfüllen muss,
nachdem er meinen Code gesehen hatte. ???:L

Danke nochmals.

 

[lowterm]

Hi,

es habe da was vergessen.
Es sollte bei der Sortierung nur die Schlüssel auf gelistet werden die zwischen 1000 und 1999
liegen. Daher sollte man doch die Abfrage so gestalten, dass die Knoten links und rechts nicht
unnötig besucht werden, wenn nicht relevant sind. :bahnhof:

Gruß

 

[Hilefoks]

Das ist auch nicht so schwer... ein AVL-Baum sieht ja immer etwa so aus (von jedem Teilbaum sind alle Einzelwerte des linken kleiner und des rechten grösser als der Wert im aktuellen Knoten):

       12
     /    \
   4        20
  / \       / \
 1    6   17    30
         /     / \
       13    22   35

InOrder bedeutet das man immer erst links, dann die Wurzel und dann rechts bearbeitet (und zwar rekursiv). Das bedeutet man läuft erst links den Baum herab bis zur 1 und behandelt diesen Knoten dann (gibt also z.B. die 1 aus). Danach behandelt man die Wurzel dieses Knotens (4) und danach den rechten Teilbaum (6). Nun ist der linke Teilbaum der 12 komplett bearbeitet und es wird die 12 behandelt. Danach geht es im rechten Teilbaum weiter (20). Hier steigt man wiederum links bis zum Blatt ab (13), usw. ....

Wenn du nun z.B. alle Zahlen grösser 20 ausgeben möchtest musst du nur schauen ob der aktuelle Knoten grösser (gleich) der kleinsten auszugebenen Zahl ist. Wenn ja gehst du links tiefer, sonst behandelt du den aktuellen Knoten und gehst rechts herunter.

Du brauchst also nur deine ursprüngliche if-Abfrage wieder einbauen (die, die ich für überflüssig gehalten habe) und leicht anpassen.

Hoffe du verstehst was ich meine... ;-)

MfG,
Hilefoks

P.S: Bist du (Informatik)-Student in einem frühen Semester?

 

[lowterm]

Hi,

danke. Leider alle meiner Versuche, dies mit if-Abfrage abzufangen gescheitert sind.
Da bekomme ich immer irgend welche Werte, die nicht vorkommen müssen. Ich stehe
leider auch etwas unter Druck(Morgen Abgabetermin und Mathe-Klausur) und daher
kaum zurechnungfähig :autsch: . Dr Code sieht jetzt so aus:

      public String sortieren(Knoten einKnoten, String text){
          if(einKnoten.getKnotenLinks() != null && einKnoten.getSchluessel() >= 1000){
               text = sortieren(einKnoten.getKnotenLinks(), text);
          }

          text += einKnoten.getSchluessel() + " " + einKnoten.getBezeichnung() + "\n";

          if(einKnoten.getKnotenRechts() != null && einKnoten.getSchluessel() <= 1999){
               text = sortieren(einKnoten.getKnotenRechts(), text);
          } 
      }

Gruß[/code]

 

[SlaterB]

wozu in aller Welt braucht der Mensch Code, wenn nicht selber denken kann?

mache dir erstmal einen Plan, beschreibe in deutscher Schrift was passieren soll,
du prüfst z.B. nur den aktuellen Knoten bei der Weiterführung der Rekursion,
ob aber der linke Knoten < 1000 ist, ist egal, der wird auf jeden Fall ausgegeben..


> Da bekomme ich immer irgend welche Werte, die nicht vorkommen müssen.

analysieren, verstehen, verbessern,
die Reihenfolge ist doch wohl immer noch gegeben, oder?
(die Operation sortiert nicht, sondern sollte sortierteAusgabe oder so heißen)
was läuft falsch?, welche Knoten konkret in welchem Baum,
prüfe den genauen Programmablauf,
warum wurde ein falscher Knoten ausgegeben bzw. ein richtiger nicht,
wie widerspricht der Programmablauf deinem gedachten Ablaufplan
(den du dir erstmal auf Papier erstellen musst)

 

[lowterm]

Hallo,

ich kann die richtigen Ausgabe erzwingen, indem ich die if-Abfrage direct da setze, wo der String
zusammengebaut wird. Das ist aber nicht der Sinn der Sache, weill es sollte so wenig wie mödlich
die Knotten besucht werden.

   if(einKnoten.getSchluessel() >= 1000 && einKnoten.getSchluessel() <= 1999)		
      text += einKnoten.getSchluessel() + " " + einKnoten.getBezeichnung() + "\n";

Eigentlich sollte das Ganze so funktionieren, wo ich was falsch mache, finde ich leider nach langer
Suche nicht, daher auch die Frage im Forum.

Gruß

 

[SlaterB]

quatsch, einmal den Schlüssel auslesen musst du mindestens,
und mit beiden Werten vergleichen auch

es sei denn, du übergibst vom Vaterknoten, dass der Maximalwert gar nicht erreicht werden kann (Vaterknoten 1500, dann ist linkes Kind auf jeden Fall < 1999),
aber das wäre unnötig kompliziert, nicht sinnvoll,

was stört es, den Knoten neben >1000 auch auf <1999 zu prüfen?
das kostet so gut wie keine Zeit,

nervige Aufgabenstellungen, die du wahrscheinlich nur falsch interpretierst, zählen nicht,

viel wichtiger ist für 'nicht mehrmals besuchen', dass du wirklich nichts mehrmals besuchst, also von einem Knotem mehrmals das linke Kind bearbeitest,
das wäre nämlich aufwendig..

 

[Hilefoks]

So sollte es reichen:

      public String sortieren(Knoten einKnoten, String text){
          if(einKnoten.getSchluessel() > 1999 || einKnoten.getSchluessel() < 1000)
               return "";

          if(einKnoten.getKnotenLinks() != null)
               text = sortieren(einKnoten.getKnotenLinks(), text);

          text += einKnoten.getSchluessel() + " " + einKnoten.getBezeichnung() + "\n";

          if(einKnoten.getKnotenRechts() != null)
               text = sortieren(einKnoten.getKnotenRechts(), text);
 
         return text;
      }

MfG,
Hilefoks

 

[SlaterB]

falsch,

schau dir deinen obigen Baum als Beispiel an und nimm als Grenze 5-10,

wenn du dann beim Knoten 4 sofort aufhörst wirst du nie den korrekten Knoten 6 erreichen

---------

es stört hier vielleicht etwas, andererseits passt es wirklich gut:
die ganzen String-Additionen sind sehr inperformant,
besser einen StringBuilder mit append benutzen, das schont den Arbeitsspeicher und geht auch noch viel flotter
(relativ gesehen, auch die langsame Methode dauert nur ein paar Millisekunden, je nach Größe des Baums)