Hier ist ein Java-Code für die erste Reise:
%Vor%Ist es möglich, eine rekursive Funktion zu schreiben, um das Gleiche zu tun?
Zuerst dachte ich, das wäre einfach, also kam ich heraus:
%Vor%Dann habe ich herausgefunden, dass es nicht funktioniert. Es ist tatsächlich das Gleiche:
%Vor%Hat jemand schon einmal darüber nachgedacht?
Ich kann mir nicht vorstellen, warum Sie möchten, wenn Sie eine perfekte iterative Lösung haben, aber hier gehen Sie;)
%Vor% Ich sollte hinzufügen, dass, wenn Sie wirklich die Knoten des Baums rekursiv durchqueren möchten, Sie ein DFS mit einem level -Parameter machen können, und die Knoten nur bei level ausgeben, dann recurse up. Aber das ist nur verrückt reden, weil Sie Knoten wayyyyy zu oft wieder besuchen würden ... einfach akzeptieren, dass BFS ist ein iterativer Algorithmus. :)
Sie können iterative Tiefentiefe-zuerst-Suche verwenden, was effektiv ein Breast-First-Algorithmus ist, der Rekursion verwendet . Es ist sogar besser als BFS, wenn Sie einen hohen Verzweigungsfaktor haben, da es nicht viel Speicher verbraucht.
Das wird nicht für alle befriedigend sein - da bin ich mir sicher. Mit allem Respekt für alle. Um die Leute, die fragen, was ist der Sinn? Der Punkt ist, dass wir glauben, dass jeder iterative Algorithmus auch eine (einfache?) Rekursive Lösung hat. Hier ist eine Lösung von "sisis" von stackoverflow.
%Vor%Es hat eine gewisse Menge an Spaß daran, aber es ist nicht klar, dass es gegen rekursive Regeln verstößt. Wenn es keine rekursiven Regeln verletzt, sollte es akzeptiert werden. IMHO.
Eine einfache BFS- und DFS-Rekursion: Drücken Sie einfach / den Wurzelknoten des Baumes in Stack / Queue an und rufen Sie diese Funktionen auf!
%Vor%}
%Vor%}
Tags und Links algorithm java c++ tree breadth-first-search