Höhe eines Binärbaums rekursiv

02.04.2008, 14:51

orkano

Höhe eines Binärbaums rekursiv

Hallo Ihr!

Habe folgende Aufgabe: Geben sie einen Pseudocode für eine rekursive Methode an, mit der man die Höhe eines Binärbaums bestimmen kann.
Dazu möchte ich die Teifensuche benutzen, heisst ich nehme den Startknoten, schaue nach, ob der Kinder hat und speichere diese in einem Stack.
Dann rufe ich die Methode rekursiv mit allen Knoten (hier ja max. 2) im Stack auf. Sobald ein Knoten keine Kinder mehr hat, weiss ich, dass hier der Zweig zu Ende ist.

Mein ganzes Problem bei der Sache sind die Verzweigungen des Baumes, durch die ich es nicht hinkriege einen vernünftigen Counter in den Algo zu bekommen, der mir mitzählt, in welcher "Höhe" ich mich gerade befinde. Durch die Verzweigungen zählt der immer zuviel, aber ich weiss nicht, wie ich das ändern kann wegen der Rekursivität! verwirrt

Bitte helft mir, wie kann ich das hinkriegen?

Hier mein Algo bis jetzt ohne Counter:

Tiefensuche(knoten n) {
knoten stack s;
if(n.hasChildren()){
s.push(n.getLeftChild());
if(n.hasRightChild()){
s.push(n.getRightChild());
}
}
while( !n.isEmpty()) {
Tiefensuche(s.pop());
}
}

So wird jeder Pfad durchgegangen und wenn der Stack Empty ist, weiss ich, dass ich am Ende bin. Aber wie kanni ch das zählen?

02.04.2008, 21:59

Auf diesen Beitrag antworten »

Tobias

Du schreibst doch selber, dass du das Problem rekursiv lösen willst. Wo hast du deine Rekursion versteckt?

Kleiner Tipp:

code:
1: 2: 3: 4: 5:	Tiefe(Knoten v) { if (v has no children) return 0; return max(Tiefe(v.leftChild), Tiefe(v.rightChild)) + 1; }

Neue Frage »

Antworten »

Höhe eines Binärbaums rekursiv

Verwandte Themen