Как сделать эту функцию нерекурсивной?
Здравствуйте, мне предложили научиться писать вещи не рекурсивно, чтобы понять, что происходит в программе намного более четко. Это программа бинарного поиска, которая читает файл списка президентов в формате .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";}}
Решение
Древовидные алгоритмы, подобные этому, на самом деле очень хорошо подходят для рекурсии, но способ сделать это без рекурсии может быть следующим:
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;
}
Другие решения
Других решений пока нет …