Rekursion Baumknoten

[Lazyyy]

Hallo zusammen,

Gegeben sei folgender "Kopf"

class TreeNode
{
private int Cont = 0;
private TreeNode Left = null;
private TreeNode Rght = null;
public TreeNode(int _Cont, TreeNode _Left, TreeNode _Rght) { 
Cont = _Cont;
Left = _Left;
Rght = _Rght;
}
}

Die aufgabe ist zu Testen ob der Baum ein Binärbaum ist:
Binär heisst er hat jeweils zwei childNodes oder keinen. der Baum ist nicht unbedingt ausbalanciert.

Mein Ansatz:

public boole IsBinary() {
if(Right != null && Left != null) return Right.IsBinary();
} 
if(Right != null && Left != null) return Left.IsBinary();
}

2. Ist es richtig, dass die Methode keine Parameter benötigt weil jeder Knoten als Kopfknoten betrachtet werden kann ?
3. Ist die Laufzeit O(N^2) ? Weil im schlimmsten fall sich jede Ebene in zwei weitere aufspaltet ?

Vielen Dank und Grüße
Lazy

 

[mihe7]

zu 1.? Dein Ansatz ist nicht falsch, am Ende fehlt natürlich noch return false;. Die zweite, identische if-Abfrage, kannst Du Dir allerdings sparen:

public boolean isBinary() {
    if (right != null && left != null) {
        return right.isBinary() && left.isBinary();
    }
    return right == null && left == null;
}

(BTW: Methoden- und Variablennamen schreibt man in Java in lowerCamelCase-Schreibweise)


zu 2. Ja.
zu 3. Was ist N?

EDIT: letztes return korrigiert, s. Kommentar von @Robat

 

[Robat]

Das letzte return müsste eher zu return right == null && left == null werden, oder?
Es wäre ja auch ein gültiger Knoten, wenn sowohl linkes als auch rechtes Kind null sind.

 

[mihe7]

@Robat Richtig

 

[Lazyyy]

zu 3. Was ist N?
[/USER]

Gut das ist die Frage .. Wenn N die Anzahl der Knoten bzw Ebenen ist?
Sprich wie sich die Laufzeit für einen sehr großen Baum ändert..

Denke das sich bei O(N^2) sich N auf die Anzahl der Knoten bezieht ?

Zusatz: Aufgabe SwapTree()
sprich links mit rechts vertauschen:

public void swapTree(){
if(left != null){
left = right;
left.swapTree()
}
if(right!= null){
right = left;
right.swapTree()
}
}

wäre das so richtig ?

 

[fhoffmann]

wäre das so richtig ?

Nein, das funktioniert so nicht. In dem Moment, in dem du

left=right

aufrufst, hast "vergessen", was ursprünglich in left stand.

 

[mihe7]

Denke das sich bei O(N^2) sich N auf die Anzahl der Knoten bezieht ?

Du durchläufst (EDIT: im schlimmsten Fall) alle Knoten, d. h. wenn N die Zahl der Knoten ist, ist die Laufzeit O(N).

 

[Lazyyy]

Nein, das funktioniert so nicht. In dem Moment, in dem du

left=right

aufrufst, hast "vergessen", was ursprünglich in left stand.

public void swapTree(){
if(left != null){
left = this;                              //left.parent = this 
left.swapTree()
}
if(right!= null){
right = this;                              //right.parent = this
right.swapTree()
}
}

mit dem Code im Kommentar würde ich jeweils den Zeiger umdrehen (reverseLink())
auf was genau zeigt das this hier ? ..
so stimmt die swapTree dann vermutlich auch nicht ?

 

[fhoffmann]

Ein swap funktioniert typischerweise so:

TreeNode temp = left;
left = right;
right = temp;

Danach müssen bei dir die rekursiven Aufrufe folgen.