Informatiker Board | Praktische Informatik | Höhe eines Binärbaums rekursiv

Informatiker Board » Themengebiete » Praktische Informatik » Höhe eines Binärbaums rekursiv

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Höhe eines Binärbaums rekursiv

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

orkano
Grünschnabel

Dabei seit: 02.04.2008
Beiträge: 8

Höhe eines Binärbaums rekursiv

Zitatantwort auf diesen Beitrag erstellen

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 14:51

Nehmen Sie orkano in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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; }

02.04.2008 21:59

Nehmen Sie Tobias in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Praktische Informatik » Höhe eines Binärbaums rekursiv