Binärer Baum -> Tiefe
-
Moin moin,
Ich hoffe ihr könnt mir bei einem weiteren Problem aushelfen.
Ich bin gerade dabei eine eine Zahl in einem binären Baum zu suchen und die Tiefe (bis diese Zahl am schnellsten gefunden werden kann) auszugeben.
Mein Baum sieht in graphischer Form ungefähr so aus................12
...........---- ----
........../...........\
.........5.............17
......./...\
.....3......6
..............\
...............9Dieser Baum ist schon in codeform umgesetzt und ich will mit meiner funktion nun zb, die Tiefesuche der Zahl 9 berechnen. Leider klappt das nicht so genau.
Ich kenne mich mit Rekursion noch nicht glänzend aus, weiss deswegen nicht genau was in dieser Funktion genau Falsch ist.Die Struktur:
struct tree_node{ int item; struct tree_node *left; struct tree_node *right; }; struct tree_node *root=NULL;Funktion:
int bst_tiefe(struct tree_node *head, int key) //key = Die Tiefe dieser Zahl wird gesucht { int k=0; if (root==NULL || head==NULL) return NULL; if (head->item !=key) k=1; if (head->item==key) return k; if (key < head->item) return k+=bst_tiefe(head->left, key); if (key > head->item) return k+=bst_tiefe(head->right, key); }
-
Ungestestet würde ich jetzt sagen, dass das so lauten muss:
int bst_tiefe(struct tree_node *head, int key) //key = Die Tiefe dieser Zahl wird gesucht { if (head->item==key) return 1; if (key < head->item) return 1 + bst_search(head->left, key); if (key > head->item) return 1 + bst_search(head->right, key); }Wobei ich annehme, dass du den Sonderfall "leerer Baum" schon vorher abfängst. Außerdem sucht sich diese Funktion zu Tode, falls der Wert nicht enthalten ist. Man sollte ggf left und right noch auf NULL prüfen und entsprechend reagieren (du musst noch definieren, was in diesem Fall das Ergebnis sein soll).
-
danke für die schnelle antwort. hab ne falsche funktion in meine bst_tiefe verpackt, nämlich bst_search, das war der fehler. Ich hab jetzt gleich den Fall behandelt wenn die Zahl garnicht vorhanden ist und das schaut jetzt bei mir so aus. Die Funktion erkennt wenn die Zahl nicht vorhanden ist und gibt eine minus Zahl(im Bereich -95 bis -99 zurück, je nachdem welchen Wert ich suche). Wäre das in diesem Fall so richtig oder gibt es eine elegantere Lösung?
int bst_tiefe(struct tree_node *head, int key) { int k=0; if (root==NULL || head==NULL) return NULL; if (head->item==key) return k; if((head->left==NULL) && (head->right==NULL)) return -100; if (head->item !=key) k=1; if (key < head->item) return k+=bst_tiefe(head->left, key); if (key > head->item) return k+=bst_tiefe(head->right, key); }
-
Oh wie peinlich, dass ich das mit der falschen Funktion nicht gleich gesehen habe.
Es geht wesentlich eleganter. Stelle dir folgende Fragen:
Wozu ist k da?
Warum gibst du bei leerem Baum NULL zurück?
Sind alle deine Abfragen nötig? Sehr viel ist redundant und kann niemals erreicht werden.Mit deinen Anforderungen an die Rückgabe von -100 bei Nichtfinden (ich finde das eine schlechte Konvention, aber das soll hier nicht diskutiert werden), würde ich das so machen:
int bst_tiefe(struct tree_node *head, int key) { /* So ist mit einem Schlag der Fall eines leeren Baumes und der Fall dass das Element nicht im Baum ist abgehandelt: */ if (head==NULL) return -100; /* So ist deutlicher, was du überhaupt zurück gibst und man muss nicht erst die gesamte Geschichte von k zurückverfolgen. Der Fall dass left oder right gleich NULL sind wird im nächsten rekursiven Aufruf gleich am Anfang abgefangen. */ if (key < head->item) return bst_tiefe(head->left, key) + 1; if (key > head->item) return bst_tiefe(head->right, key) + 1; /* Nachdem head weder Null ist und head->item weder kleiner noch größer ist als key, muss es wohl gleich key sein. Wieder geben wir zurück was wir zurückgeben wollen und nicht eine Variable mit einer Geschichte von Änderungen. */ return 1; }
-
yeah, das schaut fein danke viel mals !
