Binärbaum auf vollständigkeit prüfen

[MisterB]

Hallo zusammen,

ich habe von der Uni aus eine Aufgaben bezüglich eines Binärbaumes erhalten den ich auf seine Vollständigkeit hin überprüfen soll. Als solches wäre das auch eigentlich kein Problem für mich, wenn die Lösung nicht rekursiv sein sollte und die Methodensignatur bereits vorgegeben wäre.
Die Methodensignatur sieht als Parameter ein Node Objekt vor und als Rückgabewert Boolean, weitere Objektmember und/oder Methoden sind verboten.

Damit ihr mich nicht falsch versteht, ich brauche keine fertige Lösung von euch, sondern einen Anstoss bezüglich der Vorgehensweise. Ich stehe schlicht gesagt auf dem Schlauch und habe keine Idee wie ich das Problem lösen soll.

Zählervariablen und Iterationen mittels Schleifen fallen aufgrund der geforderten Rekursion weg.
Zusätzliche Objektvariablen und Methoden dürfen nicht implementiert werden.

Ich frage mich einfach wie ein Boolean mir da weiterhelfen soll, mehr als fragen ob der Node Kinder hat kann ich nicht, und die Ebene mit in die nächste Rekursion nehmen kann ich auch nicht.

Vielen Dank schonmal

 

[XHelp]

Mehr brauchst du ja auch nicht. Du fängst bei der Wurzel an:

boolean check(Node n) {
  hat n keine kinder? return true
  hat n 1 kind? return false;
  sonst: return check(n.rechtesKind)&&check(n.linkesKind)
}

So sollte es funktionieren...

 

[MisterB]

Vielen Dank zunächst einmal.
Ich habe mittlerweile auch meinen Denkfehler gefunden. Ich habe die ganze Zeit versucht zu prüfen ob der Binärbaum "Vollständig ausbalanciert" und nicht daran gedacht das "vollständig" != "vollständig ausbalanciert" ist. Aber nach deine Vorschlag und erneut konzentrierten Lesen der Aufgabenstellung war die Sache dann doch klar.

Aber auch so wenig Pseudoquellcode hätte nicht sein müssen.

 

[Ggguest]

Hey hey,

scheinst gerade an der Bonusaufgabe für EinfInf2 an der FH Do zu sitzen, mh?
Also in der VL06, Folie 12 ist ein vollständiger Baum folgendermaßen definiert:

• Vollständiger Baum
– Hat auf jedem Niveau die maximal mögliche Knotenzahl und
sämtliche Blätter haben dieselbe Tiefe

Da die Bonusaufgabe ja auf der VL basiert,bedeutet das wohl also auch, dass du nicht nur prüfen musst, ob jeder Knoten zwei Kinder hat, sondern eben auch, ob die Knoten alle die selbe Tiefe haben.

Folgenden Baum würde obige Rekursion akzeptieren. Ist aber laut der Vorelesung falsch.

        trees[1] = new BinaryNode(
                        new BinaryNode(
                            new BinaryNode(null, 9, null),
                            8,
                            new BinaryNode(null, 7, null)
                        ),
                        5,
                        new BinaryNode(
                            new BinaryNode(null, 1, null),
                            3,
                            new BinaryNode(
                                    new BinaryNode(null, 666, null),
                                    4,
                                    new BinaryNode(null, 667, null)
                                    )
                        )
                   );

 

[MisterB]

Thank's for the info.
Zwei, drei Handgriffe dann is der Drop gelutscht.