Как сделать эту функцию нерекурсивной?

Question

Здравствуйте, мне было предложено, чтобы я научился писать вещи нерекурсивно, чтобы понять, что происходит в программе гораздо более четко. Это двоичная программа поиска, которая читает .dat-файл списка президентов и сортирует их по алфавиту. Вот мой код, который я хочу сделать нерекурсивна:

BstNode* Insert(BstNode* root, string data) { 

if (root == NULL) { 
    root = GetNewNode(data); 
} 
else if (data <= root->data) { 
    root->left = Insert(root->left, data); 
} 
else { 
    root->right = Insert(root->right, data); 
} 
return root; 

} 

Я хочу понять, что такое рекурсия и как смотреть на что-то рекурсивного и сделать его не рекурсивным. Мне сложно понять эти понятия. Я не уверен, что мне нужно будет отрегулировать остальную часть дерева двоичного поиска, если я сделаю эту часть нерекурсивной.

Вот полная программа в случае, если вам нужно, чтобы увидеть, что еще происходит:

 #include <stdio.h> 
     #include <iostream> 
     #include <fstream> 
     #include <string> 
     using namespace std; 

struct BstNode { 

    string data; 
    BstNode* left; 
    BstNode* right; 

}; 

BstNode* GetNewNode(string data) { 

    BstNode* newNode = new BstNode(); 
    newNode->data = data; 
    newNode->left = newNode->right = NULL; 
    return newNode; 

} 



BstNode* Insert(BstNode* root, string data) { 

    if (root == NULL) { 
     root = GetNewNode(data); 
    } 
    else if (data <= root->data) { 
     root->left = Insert(root->left, data); 
    } 
    else { 
     root->right = Insert(root->right, data); 
    } 
    return root; 

} 

bool Search(BstNode* root, string data) { 

    if (root == NULL) return false; 
    else if (root->data == data) return true; 
    else if (data <= root->data) return Search(root->left, data); 
    else return Search(root->right, data); 

} 

void Print(BstNode*x) { 

    if (!x) return; 
    Print(x->left); 
    cout << ' ' << x->data << endl; 
    Print(x->right); 
} 

int main() { 

    BstNode* root = NULL; //creating an empty tree 
    //root = Insert(root, "adam"); test 
    //root = Insert(root, "greg"); test 
    //root = Insert(root, "tom"); test 
    //root = Insert(root, "bill"); test 
    //root = Insert(root, "sarah"); test 
    //root = Insert(root, "john"); test 

    ifstream fin; 
    fin.open("prez.dat"); 
    string currentprez; 
    string input = ""; 

    while (!fin.eof()) { 

     fin >> currentprez; 
     root = Insert(root, currentprez); 
    } 

    for (;;) { 
      string input = ""; 
      cout << "Would you like to 'search', 'insert', 'print' or 'quit'?\n"; 
      cin >> input; 

      //if user searches 
      if (input == "search" || input == "Search") { 

       string searchstr = ""; 
       cout << "Enter string to be searched: \n"; 
       cin >> searchstr; 
       if (Search(root, searchstr) == true) cout << searchstr + " was Found\n"; 
       else cout << "Not Found\n"; 

      } 
      //if user inserts 
      else if (input == "insert" || input == "Insert") { 

       string insertstr = ""; 
       cout << "Enter string to be inputted: \n"; 
       cin >> insertstr; 
       if (Search(root, insertstr) == true) cout << insertstr + " already exists\n"; 
       else root = Insert(root, insertstr); 

      } 

      //if user prints 
      else if (input == "print" || input == "Print") Print(root); 
      //if user quits 
      else if (input == "quit" || input == "Quit") return(0); 
      //if anything else 
      else cout << "Invalid input\n"; 


     } 


    } 

Answer 1

алгоритмы дерева, как это на самом деле очень хорошо подходит для рекурсии, но способ сделать это без рекурсии может быть такой :

BstNode* Insert(BstNode* root, string data) { 
    if (root == null) { 
     return GetNewNode(data); 
    }  

    BstNode* prev = null; 
    BstNode* pos = root; 
    while (pos != null) { 
     prev = pos; 
     if (data <= pos->data) { 
      pos = pos->left; 
     } 
     else { 
      pos = pos->right; 
     } 
    } 
    if (data <= prev -> data) { 
     prev -> left = GetNewNode(data); 
    }else { 
     prev -> right = GetNewNode(data); 
    } 

    return root; 
}