SS2017 3a) Kantorowitsch Bäume: Frage zur Preorder-Traversierung

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

SS2017 3a) Kantorowitsch Bäume: Frage zur Preorder-Traversierung
Hallo zusammen,

Gegeben sei folgende Aufzählung KOp für Knoten (Operatoren in Großbuchstaben, Operanden sind Variablen und kleingeschrieben) und der Beginn der Klasse Kare zur Verarbeitung von Kantorowitsch-Bäumen:

import java.util.*;

enum Kop { // operators AND/OR/NOT and operands a-z for Kantorowitsch trees 
    AND, OR, NOT, a, b, c....
}

class Tree { // Kantorowitsch tree
        KOp o;
        KTree[] cs; //children

        public KTree (KOp o, KTree... cs) {  ---> was bedeuten hier die 3 Punkte?
            this.o = o; // example: "new KTree(KOp.a)" creates  a leaf with
            this.cs = cs; // an empty cs array that represents variable "a"
        }

1. Frage: Was bedeuten die 3 Punkte im Kopf des Konstruktors?

2. Frage: Warum mache ich im folgenden Stück Code: r.[b]addAll/b?
Wenn ich toPrefix() aufrufe mache ich doch schon r.add(o) wodurch alle Elemente eingesammelt werden sollten?
Oder muss das zwingend so gemacht werden, da toPrefix() eine LinkedList zurückgibt und nur addAll(), aber nicht add() alleine
ganze Collections hinzufügen kann?

Ergänzen Sie die Instanzmethode toPrefix, die den baum in Prerder-Reihenfolge traversiert und dabei die Knotenwerte in die Ergebnisliste r sammelt:

LinkedList<KOp> toPrefix() {
    LinkedList<KOp> r = new LinkedList<>();
    r.add(o);
    for(KTree c : cs) {
        r.addAll(c.toPrefix());
    }
    return r;
)

Liebe Grüße
Speedy

3

Hallo,

zu Frage 1: Das [m]KTree… cs[/m] ist eine Möglichkeit, eine beliebige Anzahl an Argumenten eines bestimmten Typs zu übergeben. Beispielsweise kann man den Konstruktor sowohl mit [m]new KTree(Kop.AND);[/m], aber auch mit [m]new KTree(Kop.AND, k1);[/m] oder [m]new KTree(Kop.AND, k1, k2, k3);[/m] aufrufen. Die Argumente werden in dem Array [m]cs[/m] gespeichert, im letzten Beispiel wäre dann also [m]cs[0] = k1[/m], [m]cs[1] = k2[/m] und [m]cs[2] = k3[/m]. Damit die Zuordnung klar ist, kann man diese Notation grundsätzlich nur am Ende der Argumentenfolge und auch nur einmal verwenden (folgendes ist also explizit nicht möglich: [m]public KTree(KTree… a, KTree… b) { … }[/m] oder auch [m]public KTree(KTree… a, KOp cs) { … }[/m]). Für mehr Informationen einfach mal hier schauen: https://docs.oracle.com/javase/tutorial/java/javaOO/arguments.html#varargs

zu Frage 2: Da musst du einfach mal die Preorder-Reihenfolge auf einem Blatt durchgehen. Man fügt zunächst den Knoten, der gerade betrachtet wird, hinzu. Danach betrachtet man rekursiv die Preorder-Reihenfolgen der nachfolgenden Teilbäume, und fügt diese jeweils an die Ausgabeliste. Das Problem, was bei deiner Lösung auftritt, ist folgendes: Durch [m].add[/m] wird grundsätzlich nur ein Element hinzugefügt. Das ist kein Problem, wenn es nur einen nachfolgenden Teilbaum gibt (hier kann man einfach das aktuelle Element vorne an die Liste des Teilbaums hinzufügen). Hast du mehrere nachfolgende Teilbäume, müssen deren Elemente aber in eine Liste zusammengefügt werden. In der FSI-Lösung wird dieses Problem behandelt, indem einfach die Liste mit einem Element initialisiert wird und anschließend mit [m]addAll[/m] alle Elemente einer Liste eines Teilbaums an die Ergebnisliste drangehängt werden.

Man kann natürlich die Aufgabe auch ohne Kenntniss von [m]addAll[/m] lösen. Möglich wäre es z. B., mit einer Schleife über die Elemente der Preorder-Liste eines Teilbaums zu iterieren und jedes Element einzeln an die Ausgabeliste anzuhängen.

LG Gabriel

1 „Gefällt mir“
4

Vielen Dank Gabriel2029 für deine ausführlichen Antworten!