Ich habe ein Problem in meinem DFS Search (Tree) Code. Wie kann ich Rekursion brechen?

Question

Die Art, wie ich den Baum durchsucht habe, ist durch eine Rekursion. Ich habe mich gefragt, ob ich von der Rekursion brechen und das Programm zum normalen Fluss erreichen könnte. Also im Grunde versuche ich zu sagen ist, gibt es eine Möglichkeit, von einer Rekursion zu brechen, ohne den Stack zurück zu verfolgen? Wenn nicht kann jemand mir einen anderen Weg vorschlagen?

BinaryTree Klasse

class BinaryTree 
{ 
public: 
    template <class T> 
    class Node { 
    public: 
     Node(T item) { 
      this->item = item; 
      this->left = nullptr; 
      this->right = nullptr; 
     } 
     Node* left; 
     Node* right; 
     T item; 
    }; 
    BinaryTree(); 
    template<class T> 
    void DFS(Node<T> *N); 
private: 
    Node<char>* root; 

}; 


BinaryTree::BinaryTree() 
{ 
    this->root = new Node<char>('A'); 
    this->root->left = new Node<char>('B'); 
    this->root->right = new Node<char>('C'); 
    this->root->left->left = new Node<char>('D'); 
    this->root->left->right = new Node<char>('E'); 
    this->root->right->left = new Node<char>('F'); 
    this->root->right->right = new Node<char>('G'); 
    this->DFS(root); 
} 

template <class T> 
void BinaryTree::DFS(Node<T>* N) { 
    if(N == nullptr) 
     return; 
    cout << N->item << endl; 
    if(N->item == 'E') { 
     cout << "found\n"; 
     //Break from recursion; 
    } 

    DFS(N->left); 
    DFS(N->right); 
} 

Erzeugter Ausgang

A 
B 
D 
E 
found 
C 
F 
G 

Ausgabe Erforderlich

A 
B 
D 
E 
found 

Answer 1

Die einfachste Lösung, die mir in den Sinn kam:

template <class T> 
bool BinaryTree::DFS(Node<T>* N) { 
    if(N == nullptr) 
     return false; 
    cout << N->item << endl; 
    if(N->item == 'E') { 
     cout << "found\n"; 
     return true; 
    } 

    if(DFS(N->left)) 
     return true; 
    if(DFS(N->right)) 
     return true; 
    return false; 
} 

Sie müssten jedoch den Rückgabetyp in der Klassendeklaration ändern.