Frage von Anonynonymous, 20

Java Binärbaum in bestimmter Reihenfolge in Array übertragen?

Hallo zusammen,

ich hocke derzeit vor einer von mehreren ziemlich kniffligen Aufgaben und komme nicht so recht weiter.

Hintergrund: Ich habe einen Binärbaum mit 15 Objekten. Diese Objekte haben einen Namen, Rang, einen linken- und rechten Nachfolger und die boolean Information männlich/weiblich.

Die Wurzel nimmt das Objekt König ein. Im linken Teilbaum sind die Maennlein und im rechten die Weiblein. Der Inhalt des Baumes wurde im Rahmen einer vorherigen Aufgabe weiter unterteilt nach Rängen. Alles in allem soweit erst einmal ein ganz normaler Binärbaum, denke ich.

Meine Aufgabe ist es eine Volkszaehlung() durchzuführen. Dazu soll ich das Königreich (den Binärbaum) in ein Array umwandeln und die Plätze nach folgenden Regeln füllen:

  1. An Erster Stelle kommt der König (Hier erst einmal irrelevant, ich denke diesen Spezialfall kann ich recht leicht abfangen)

  2. Es folgen alle männl. Personen in Reihen folge ihres Ranges (König, Fuersten, Buerger, Bauern)

  3. Dann weibliche Personen in der selben Reihenfolge

  4. Es gibt keine leeren Zellen im Array, es hat exakt die benötigte Größe.

Ich habe bisher eine Hilfsmethode geschrieben, die mir die Anzahl der Objekte im Baum besorgt, damit ich das Array mit der richtigen Größe erstellen konnte.

Ich habe darüber hinaus eine weitere Hilfsmethode geschrieben, die mir anhand von rekursiven Aufrufen das Array füllen soll (Rekursion muss hier benutzt werden ;) )

Hier noch einmal der Code:

public Person[] volkszaehlung()
    {
        int i = 1; // Zaehlervariable
        int v = Rang.FUERST.ordinal(); // Rang
        Person linkerteilbaum = spitze.getLinks();// Linker Teilbaum
        Person[] Kingdom = new Person [getPersonenAnzahl()]; // Array mit 15 elementen
                
        while (v > 0) {
            volkszaehlung(linkerteilbaum, v, Kingdom, i);
            v--;
        }
            
        return Kingdom;
    }
    
    private Person [] volkszaehlung(Person spitze, int v, Person [] Kingdom, int i){
        
        if (spitze.getLinks() != null){
            volkszaehlung(spitze.getLinks(), v, Kingdom, i);
        }
    
        if (spitze.getRechts() != null){
            volkszaehlung(spitze.getRechts(), v, Kingdom, i);
        }

                if(spitze.getRang().ordinal() == v){
                    Kingdom[i] = spitze;
                                        i++;
                }
        return Kingdom;
    }

Weitere Anmerkungen:

  • Personen sind die Baumelemente

  • Die Ränge sind in einer enum-class, man kann sie also leicht mit ordinal() vergleichen.

  • spitze = Wurzel.

  • Wie ihr seht, rufe ich die Methode private Person [] volkszaehlung(Person spitze, int v, Person [] Kingdom, int i) nur einmal für den Linken Teilbaum auf. Das liegt zum einen daran, dass ich noch nicht fertig bin und zum anderen daran, dass ich sie erst einmal für den Linken Teilbaum zum laufen bekommen möchte.

Mein Problem: Soweit läuft eig. alles. Mein Problem ist, dass in der Hilfsmethode i nur für den Momentanen Aufruf inkrementiert wird...Anstatt das Array also weiterzuführen, wird die Stelle [1] immer wieder mit der entsprechenden Person überschrieben.

Expertenantwort
von KnusperPudding, Community-Experte für Java, 3

Dein Problem ist, wie du mit Referenzen umgehst:

private void test() {
  int meineZahl = 0;
  test(meineZahl);
  System.out.println(meineZahl);
}

private void test(int zahl) {
 zahl++;
}

Hier wirst du feststellen, dass das Ergebnis die 0 ist.

Entsprechend hättest du mehrere Möglichkeiten:

1. Du  änderst den Returntype deiner "Hilfsmethode" zu int ab und lässt dort den neuen Index zurück geben, welchen du entsprechend setzen könntest:

i = volkszaehlung(spitze.getRechts(), v, Kingdom, i);

2. Du erstellst dir eine Hilfsklasse,  in der du die Informationen Speicherst und reichst es an deine Hilfsmethoden durch:

class Position {
  int index;

  public Position(int index) {
     this.index = index;
  }
  
 public void increment() {...};
}

Wovon du einmalig eine Instanz bildest und die Referenz davon an deine Methoden durchreichst um beispielsweise hoch zu zählen oder den Index abzufragen.

Theoretisch, sofern die Sortierung nach diesem Prinzip nicht deine Hauptaufgabe sein sollte, könntest du die Array erstmal 'einfach so' füllen und dann einfach via Comparator sortieren lassen.

Den Comparator müsstest du sowieso ausformulieren, aber das würde so aussehen:

Collections.sort(Arrays.asList(persons), new Comparator{ .... });

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten