3-Baum, rekursive Iteration, jeden Knoten mit (seiner) Ebene beschriften

#1

Hallo guten Morgen, ich brauche nochmal Expertenmeinung (Achtung: Wortwitz: Vielleicht sehe ich den Wald vor lauter Bäumen nicht :smiley: ).

Ich habe einen 3-Baum (also nicht Binärbaum, wie nennt man einen 3-Baum?) und durchlaufe ihn rekursiv:

    String name = "*";
    Tree[] trees = new Tree[3];
}```

Wenn `tree.trees** == null` (also wenn nur ein einziger Unterbaum `null` ist), dann ist es ein Blatt. Folgerung: Baum vollständig?

```    private void printA(Tree tree, int index) {
        if (tree.trees[0] != null) {
            System.out.println(" \"" + tree.name + " ("+index+")\" -> \"" + tree.trees[0].name + " ("+(index+1)+")");
        }
        if (tree.trees[1] != null) { // Prüfung überflüssig . . . . . .
            System.out.println(" \"" + tree.name +  " ("+index+")\" -> \""+ tree.trees[1].name + " ("+(index+2)+")");
        }
        if (tree.trees[2] != null) {
            System.out.println(" \"" + tree.name + " ("+index+")\" -> \"" + tree.trees[2].name + " ("+(index+3)+")");
        }
        if (tree.trees[0] != null) {
            printA(tree.trees[0], index+3);
        }
        if (tree.trees[1] != null) { // Prüfung überflüssig . . . . . .
            printA(tree.trees[1], index+3);
        }
        if (tree.trees[2] != null) {
            printA(tree.trees[2], index+3);
        }
    }```

Was muss ich jetzt mit Index machen, dass Knoten/Blatt auf Ebene i noch ein ' (i)' als Beschriftung bekommt? Besser kann ich es leider nicht schildern, ich bin mir fast sicher, i-wer hat das schonmal gemacht....

Mag mir wer helfen?

Nochmal ein Hinweis!:
Es gibt 1mal Ebene 1,
es gibt 3mal Ebene 2,
es gibt 9mal Ebene 3, usw., usf.,
#2

Wie üblich völlig unverständlich. Vollständig würde bedeuten, dass alle drei Kinder vorhanden sind (nach landläufiger Verwendung von “vollständiger” Baum).

Leider ist völlig unklar, was deine Beschriftung eigentlich sein soll, was genau IST denn der index? und warum rufst du die Rekursion mit index+3 auf??

auch dein Ausdruck ist Nonsense, warum erst index und dann index+1 (index +2, index +3)

wenn index sagen wir 0 ist, dann kommt

0 Knoten 1
0 Knoten 2
0 Knoten 3

und dann? wie soll das weitergehen??

#3

Aaaach Mist, ich hab mich nicht verständlich ausgedrückt. Ich möchte alle Knoten (egal ob Blatt oder nicht) von oben nach unten und von links nach rechts innerhalb eines rekursiven “Tiefendurchlaufs” durchnummerieren.

Zudem ist der 3-Baum auf/in jeder Ebene (außer der “Blattebene”) vollständig.

Mein Ansatz war falsch. Ich hab es jetzt ganz einfach so “umgangen”:

    static int index1 = 1;
    int index2 = index1++;
    String name = "*";
    Tree[] trees = new Tree[3];
}```

Damit bekommt jeder Knoten nach der Erstellungsreihenfolge eine Nummer.

Wenn ihr trotzdem noch i-wie einen Tipp/Hint habt, dann immer raus damit (also dann schreibt ihn, bitte).
#4

stürzt das Ding nicht sofort ab?

#5

Besonders schön ist das nicht, da geb ich dir recht. Aber war eine Inkrementierung oder andere Anweisung an dieser Stelle vor Java 8 noch nicht möglich?

Nein, stürzt nicht ab, erfüllt seinen Zweck. Alle Knoten haben jetzt eine eindeutige ID.

Das hat zwar jetzt nix mehr mit den Ebenen zu tun, aber ich kann das Ergebnis der Ausgabe grafisch (richtig) darstellen

#6

BTW, Java ist eine objektorientierte Sprache. Was spricht dagegen, (inneren) Knoten und Blättern eigene Unterklassen zu spendieren?