Hello it was suggested to me that I learn to write things non-recursively to understand what is going on much more clearly in the program. It is a binary search program that reads a .dat file of a list of presidents and sorts them alphabetically. Here is my code that I want to make non-recursive:
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;
}
I want to understand what recursion is and how to look at something recursive and make it non recursive. I'm having trouble understanding these concepts. I'm not sure if I would need to adjust the rest of the binary search tree if I made that portion non-recursive.
Here's the full program in case you need to see what else is going on:
#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";
}
}
Tree algorithms like this are actually very well suited for recursion, but a way to do it without recursion could be this:
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;
}