Aufgabe Rekursion Binärer Baum

[FuckinDonuts]

Hallo liebes Java Forum,

ich habe ein kleines Problem mit einer Aufgabe und könnte ein wenig Hilfe gebrauchen 🙂

Und zwar soll ich eine Methode für die Klasse TreeNode schreiben mit der es mir möglich ist (Rekursiv natürlich), alle Knoten auf der übergegeben Ebene (level), sowie die darunteren zu löschen.

Mein Ansatz sieht bis jetzt wie folgt aus:

    public void removeLevel(int level) {
       int counter = 0;          //Auf welcher Ebene befinden wir uns zurzeit
       int boarder = level;    // Wann wird gelöscht

       if (level != 0) {         // Der Root Knoten soll erhalten bleiben
           for (int i = 0; i < 4; i++) {
               if (counter == level) { //Sobald man auf der gewünschten Ebenen ist sollen                                     // alle Referenzen auf null gesetzt werden. Kommt dem Löschen hier gleich
               
                children[I] = null;
              
                } else if (children[I] != null) { 
                   counter++;
                   children[I].removeLevel(counter);
               }
           }
       }
   }

Habe meinen Gedankengang mal mit Kommentiert... Falls jemand eine Idee hat, woran es liegen könnte dass es nicht funktioniert, darf mir gerne helfen. Würde mich riesig freuen. Kann auch gerne meine Testclient und die restliche Klasse hochladen falls einer es selbst in Java ausprobieren mag.[/I][/I][/I]

 

[Xyz1]

Gut, dass du die Implementierung mit-angegeben hast mit Foto, da sonst die Aufgabenstellung nicht eindeutig wäre.

Ist die entsprechende Ebene gefunden, muss children = new TreeNode[4]; gesetzt werden. Das ist alles.

 

[FuckinDonuts]

Danke, für die schnelle Antwort. Ja das hatte ich auch schon, jedoch funktioniert das immernoch nicht ganz und ich weiß mir auch nicht mehr zu helfen. Habe mal den ganzen Code hochgeladen. Evtl. kann man dann besser nachvollziehen was ich meine.

public class TreeNode {
   private String name;
   private TreeNode children[];
   TreeNode(String name) {
       this.name = name;
       this.children = new TreeNode[4];
   }
   public void setName(String name) {
       this.name = name;
   }
   public String getName() {
       return name;
   }
   public void setChild(int index, TreeNode child) {
       this.children[index] = child;
   }
   // a)
   public int getHeight() {
       int counter = 0;

       for (int i = 0; i < children.length; i++) {
           if (children[i] != null) {
               int h = children[i].getHeight();
               if (h > counter) {
                   counter = h;
               }
           }
       }
       return counter + 1;
   }

   // b)
   public void removeLevel(int level) { 
       int counter = 0;
       int boarder = level;
       if (level != 0) {
           for (int i = 0; i < 4; i++) {
               if (counter == level) {
                   children = new TreeNode [4]; //Geändert
               } else if (children[i] != null) {
                   counter++;
                   children[i].removeLevel(counter);
               }
           }
       }
   }

public class TestClient {
   public static void main(String[] args) {
       TreeNode Root = new TreeNode("Hey");
       TreeNode First = new TreeNode("Run");
       TreeNode Second = new TreeNode("Faster!");
       Root.setChild(1, First);
       First.setChild(3, Second);
       Root.removeLevel(3);
       System.out.println(Root.getHeight());
   }
}

Normalerweise müsste die Ausgabe, beim Aufruf der Root.getHeight Methode, "2" sein da ja das 3 Level "gelöscht" wurde. Jedoch gibt er nach wie vor 3 aus. Ich glaube ich habe irgendwo noch einen kleinen Fehler in meinem Code. Vllt bei dem Inkrement counter++ ?

 

[Meniskusschaden]

Du solltest den Code in Code-Tags posten (z.B. über den Button "Einfügen"). Das kann man besser lesen und dabei wird auch nichts verfälscht, wie es hier offenbar geschehen ist. So ist es jedenfalls nicht kompilierbar.

 

[FuckinDonuts]

Vielen Dank für den Hinweis! Ja so sieht es auch gleich viel besser aus

public class TreeNode {

    private String name;
    private TreeNode children[];

    TreeNode(String name) {
        this.name = name;
        this.children = new TreeNode[4];
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setChild(int index, TreeNode child) {
        this.children[index] = child;
    }

    // a)
    public int getHeight() { // Methode die die Höhe eines Knoten bestimmt,
        // falls Wurzel null ist, -1 ausgeben
        int counter = 0; // Counter zu Beginn auf Null

        for (int i = 0; i < children.length; i++) {
            if (children[i] != null) {
                int h = children[i].getHeight();
                if (h > counter) {
                    counter = h;
                }
            }
        }
        return counter + 1;

    }

    // b)
    public void removeLevel(int level) { // Löscht alle Ebenen sowie die
                                            // darunter
        int counter = 0;
        int boarder = level;

        if (level != 0) {
            for (int i = 0; i < 4; i++) {
                if (counter == level) {
                    children = new TreeNode [4];
                } else if (children[i] != null) {
                    counter++;
                    children[i].removeLevel(counter);
                }
            }
        }
    }
}

public class TestClient {

    public static void main(String[] args) {
        TreeNode Root = new TreeNode("Hey");
        TreeNode First = new TreeNode("Run");
        TreeNode Second = new TreeNode("Faster!");
        Root.setChild(1, First);
        First.setChild(3, Second);
        Root.removeLevel(3);
        System.out.println(Root.getHeight());
    }
}

 

[Xyz1]

Du solltest den Code in Code-Tags posten

Ich glaub, es wird einfach nicht mein Nickname und meine Signatur gelesen! Dann kommen Fragen "Weißt du denn wie es geht" und Code wird einfach so frech unformatiert reingehauen. DerWissende heißt nicht DerWissende, wenn er nicht wüsste, wie es geht.

Desweiteren...... Sollte man lesen, wie man Fragen richtig stellt und Vor dem ersten Posting. Für Hausaufgaben und eine Musterlösung Prüfung bin ich nicht willens. 😉

Wahrscheinlich werd ich hier nichts mehr schreiben.

 

[FuckinDonuts]

Nach einer Musterlösung habe ich ja auch nicht gefragt, dachte es wäre etwas einfacher den Code nachzuvollziehen wenn man Ihn so vor sich hat.

Das der Code so "unformatiert reingehauen" wurde tut mir sehr leid, jedoch wusste ich nicht wie ich Ihn anders Einfügen sollte. War mein zweiter Post in dem Forum. Jetzt weiß ich ja wie es geht...

Trotzdem Vielen Dank für deine Mühen!

 

[Meniskusschaden]

Bei dem Aufruf children[ i].removeLevel(counter);hat counter immer den Wert 1. Das ist doch bestimmt nicht so beabsichtigt.

 

[FuckinDonuts]

Tatsächlich! Nein das war so auf jedenfall nicht gedacht.
Hab auch vergessen das sobald er in die Rekursion geht er jedes mal wieder auf 0 gesetzt wird. Habe mich jetzt auch ein bisschen mit dem debugger durch gekämpft und den code verändert und nun löscht er nur noch eine Ebene zu wenig... Das ist ja schon mal ein Anfang 😀 Werde mal morgen weiterschauen, ggf. den Code auch nochmal neu schreiben. Vielen Dank für deine Hilfe!

    public void removeLevel(int level) {
        int counter = 0;
        int boarder = level;
        for (int i = 0; i < children.length; i++) {
            if (counter == boarder) {
                children[i] = null;
            } else if (children[i] != null) {
                counter++;
                children[i].removeLevel(boarder - counter);
            }
        }
    }

 

[mrBrown]

Wenn die Methode für irgendeinen Baum wie gewünscht Funktioniert hat, war das ziemlicher Zufall.
Ich weiß nicht was dabei deine Idee war, aber ich würde da noch mal ganz von vorne anfangen 😉

 

[DrZoidberg]

Wieso kopierst du den Wert von level in die Variable boarder? Das ist völlig unnötig. Counter benötigst du auch nicht. Die Methode müsste eher so aussehen.

public void removeLevel(int level) {
  if(level < 1) {
    ...
  } else if(level == 1) {
    ...
  } else {
    for(...) {
    }
  }
}

 

[Meniskusschaden]

Aber immerhin funktioniert der Aufruf von removeLevel() für die nächste Ebene jetzt korrekt. Allerdings zu umständlich, denn die Variablen boarder und counter sind dafür überflüssig. Die Erkenntnis würde ich für den Neuanfang noch mitnehmen.😉

 

[mrBrown]

Aber immerhin funktioniert der Aufruf von removeLevel() für die nächste Ebene jetzt korrekt. Allerdings zu umständlich, denn die Variablen boarder und counter sind dafür überflüssig. Die Erkenntnis würde ich für den Neuanfang noch mitnehmen.😉

Das ist aber eine sehr weite Auslegung von "korrekt", mehr als 'es werden Zahlen übergeben' ist da kaum korrekt dran 😉

 

[Meniskusschaden]

Wenn ich das richtig sehe, wird an der Stelle letztendlich immer level-1 übergeben, was ja ganz sinnvoll ist.

 

[mrBrown]

Wenn ich das richtig sehe, wird an der Stelle letztendlich immer level-1 übergeben, was ja ganz sinnvoll ist.

Ne, fürs erste Kind level-1, fürs zweite level-2, usw, und sobald irgendwas kleiner 0 übergeben werden würde, wird stattdessen das Kind gelöscht...

 

[Meniskusschaden]

Stimmt. Das habe ich in meinem Posting #8 auch schon übersehen.😳