✔ Anzahl von Knoten in einem Baum

[christina05]

Hallo alle zusammen,

ich hoffe ihr könnt mir hier helfen..
Ich möchte eine Methode schreiben, die zunächst einen gegebenen binären Suchbaum untersucht, ob dieser vollständig ist oder nicht (vollständig = alle Knoten haben entweder 0 oder 2 Kinder), falls dieser Baum nicht vollständig soll, soll die Funktion FullTree() diesen Baum um die fehlenden Knoten vervollständig, so dass man am Ende einen vollständigen Baum hat.

Meine Idee:
Um diese Methode schreiben zu können, muss man erstmal die Höhe von jedem Knoten in dem Baum herausfinden. Achtung: nicht die Höhe von dem kompletten Baum, weil man ebene für ebene durchgehen muss. Das Problem ist, egal wie ich versuche die Funktion, sieht sie am Ende wieder genau so aus wie die Methode zur Ermittlung der Höhe.

Ich hoffe ihr könnt mir helfen.


LG

 

[sheel]

Hi

warum brauchst du die Höhe? Warum Ebene für Ebene durchgehen?

Welche Knotenwerte sollen die auffüllenden Knoten erhalten?

 

[christina05]

Hi,

Naja wie soll ich denn sonst festellen, ob der Baum vollständig ist oder nicht? Ich muss ja irgendwie feststellen können wo genau in einem Baum Knoten fehlen..
also das glaube ich zumindest.
Ja die Schlüssel sind vom Typ String.

 

[sheel]

alle Knoten haben entweder 0 oder 2 Kinder

Dafür ist mir die Höhe eigentlich egal. Rekursiv jeden existierenden Knoten durchgehen, und bei jedem die Kindanzahl prüfen. Wenn 1 dann noch ein Kind erzeugen, fertig. Und die Wertefrage war, welche [String-]Werte die neuen Knoten bekommen sollten.

 

[christina05]

Kannst du mir vielleicht da etwas auf die Sprünge helfen, weil ich nicht genau weiß wie ich das machen, weil meine Knoten vom Typ Node sind und nicht Integers...
Soweit bin ich noch nicht, um die Werte zu bestimmen.

public int countNodes (Node tree){
if(tree == null){
return 0;
}
else if (tree gleich 2 oder 0)
dann ist der Baum vollständig.
(..)

 

[sheel]

Annahme: Node hat die Variablen String value, Node left, Node right,
und die Methoden sind Teil von Node (wobei sie bei der Wurzel aufgerufen werden)

boolean isfull() {
    if(left == null && right == null) return true;
    if(left == null) return false;
    if(right == null) return false;
    return left.isfull() && right.isfull()
}
void makefull() {
    if(left == null && right == null) return;
    if(left == null) left = new Node();
    if(right == null) right = new Node();
}

Eine Methode countNodes war laut deiner Angabe eigentlich nicht gefragt.

 

[christina05]

Die Methode countNodes hatte ich mir selbst ausgesucht.
Trifft diese Methode auch dafür zu wenn die Knoten 2 Kinder haben? Und werden auch damit die inneren Knoten untersucht?

 

[sheel]

Du solltest dir diese zwei wirklich kurzen Methoden einmal gründlich anschauen
und durchdenken. Die Fragen erledigen sich dann vermutlich von selbst.