DFS 검색 (트리) 코드에 문제가 있습니다. 재귀를 어떻게 끊을 수 있습니까?

Question

트리를 검색하는 데 사용한 방법은 재귀를 통해 발생합니다. 재귀에서 벗어나 정상적인 흐름으로 프로그램에 도달 할 수 있는지 궁금합니다. 그래서 기본적으로 스택을 추적하지 않고 재귀를 중단 할 수있는 방법이 있습니까? 누군가 다른 방법을 제안 할 수 없다면?

BinaryTree 클래스

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

출력 생성

A 
B 
D 
E 
found 
C 
F 
G 

출력 필수

A 
B 
D 
E 
found 

Answer 1

가장 간단한 해결책은 내 마음에 온다 :

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

그러나 클래스 선언에서 반환 유형을 변경해야한다.