asked on
#include "stdio.h"
using namespace std;
#include <stack>
// BST Node
struct Node
{
int key;
struct Node *left;
struct Node *right;
};
class Iterator
{
private:
Node* thisRoot;
Node* thisCurr;
Node* thisMaximum;
stack<Node*> cards;
void InOrder(Node* root, Node*& succ, int key)
{
// Base case
if (root == NULL) return ;
// If key is present at root
if (root->key == key)
{
// the minimum value in right subtree is successor
if (root->right != NULL)
{
Node* tmp = root->right ;
while (tmp->left)
{
cards.push(tmp);
tmp = tmp->left;
}
succ = tmp ;
}
return ;
}
// If key is smaller than root's key, go to left subtree
if (root->key > key)
{
succ = root;
InOrder(root->left, succ, key) ;
}
else
{
if (key == thisMaximum->key)
{
return;
}
if (cards.size() > 0)
{
succ = cards.top();
if (succ != NULL && key < thisMaximum->key)
{
InOrder(
root->right,
succ,
key) ;
}
}
}
}
Node* HelperGoLeft(Node* where)
{
if (where == NULL)
{
return NULL;
}
if (where->left == NULL & where->right == NULL)
{
return where;
}
return HelperGoLeft(where->left);
}
Node* HelperGoRight(Node* where)
{
if (where == NULL)
{
return NULL;
}
if (where->left == NULL & where->right == NULL)
{
return where;
}
return HelperGoRight(where->right);
}
public:
Iterator(Node* theTree)
{
thisRoot = theTree;
thisCurr = HelperGoLeft(thisRoot);
thisMaximum = HelperGoRight(thisRoot);
}
int next()
{
struct Node* successor(NULL);
InOrder(thisRoot, thisCurr, thisCurr->key);
return thisCurr->key;
}
bool HasNext()
{
return thisRoot != NULL && thisCurr->key < thisMaximum->key;
}
};
This is my C++ test driver program.
// A utility function to create a new BST node
Node *newNode(int item)
{
Node *temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
/* A utility function to insert a new node with given key in BST */
Node* insert(Node* node, int key)
{
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
return node;
}
int main(int argc, char* argv[])
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
Node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
insert(root, 100);
insert(root, 90);
insert(root, 110);
Iterator* test = new Iterator(root);
while( test->HasNext())
{
printf("%d\n", test->next());
}
return 1;
}
ASKER
ASKER
ASKER
C++ is an intermediate-level general-purpose programming language, not to be confused with C or C#. It was developed as a set of extensions to the C programming language to improve type-safety and add support for automatic resource management, object-orientation, generic programming, and exception handling, among other features.
TRUSTED BY