この関数を非再帰的にするには？

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