Non-recursive tree walking

#include <iostream> // Non-recursive In-order Tree Printing

#include <string>

class treeable

{ public:

string key;

treeable(string k): key(k) { } };

class tree

{ protected:

struct node

{ treeable * data;

node * left, * right;

node(treeable * d): data(d), left(NULL), right(NULL) { } };

node * root;

void printallfromnode(node * n);

public:

tree(void): root(NULL) { }

void add(treeable * d);

treeable * find(string k);

void printall(void);

void NonRecursivePrintAll(void); };

void tree::add(treeable * d)

{ string k = d->key;

node * prev = NULL;

node * curr = root;

while (curr!=NULL)

{ prev=curr;

if (k<curr->data->key)

curr=curr->left;

else

curr=curr->right; }

curr = new node(d);

if (prev==NULL)

root=curr;

else if (k<prev->data->key)

prev->left=curr;

else

prev->right=curr; }

treeable * tree::find(string k)

{ node * curr = root;

while (curr!=NULL)

{ if (curr->data->key==k)

return curr->data;

else if (k<curr->data->key)

curr=curr->left;

else

curr=curr->right; }

return NULL; }

void tree::printall(void)

{ printallfromnode(root);

cout << "\n"; }

void tree::printallfromnode(node * n)

{ /* alpha */

if (n==NULL) return;

printallfromnode(n->left);

/* beta */

cout << " " << n->data->key;

printallfromnode(n->right);

/* gamma */ }

void tree::NonRecursivePrintAll(void)

{ enum position { alpha, beta, gamma };

struct StackFrame

{ position wherefrom;

node * currentnode; };

StackFrame stack[100];

int stacktop=0;

stack[stacktop].wherefrom = alpha;

stack[stacktop].currentnode = root;

while (stacktop >= 0)

{ StackFrame & task = stack[stacktop];

switch (task.wherefrom)

{

case alpha:

{ if (task.currentnode == NULL)

{ stacktop -= 1;

continue; }

task.wherefrom = beta;

stacktop += 1;

StackFrame & newtask = stack[stacktop];

newtask.wherefrom = alpha;

newtask.currentnode = task.currentnode->left;

continue; }

case beta:

{ cout << " " << task.currentnode->data->key;

task.wherefrom = gamma;

stacktop += 1;

StackFrame & newtask = stack[stacktop];

newtask.wherefrom = alpha;

newtask.currentnode = task.currentnode->right;

continue; }

case gamma:

{ stacktop -= 1;

continue; } } }

cout << "\n"; }

void main(void)

{ tree T;

cout << "? ";

while (1)

{ string s;

cin >> s;

if (s=="end") break;

T.add(new treeable(s)); }

T.printall();

T.NonRecursivePrintAll(); }

$ a.out

? one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen sixteen end

eight eleven fifteen five four fourteen nine one seven six sixteen ten thirteen three twelve two

#include <iostream> // An Enumerator

#include <string>

class treeable

{ public:

string key;

treeable(string k): key(k) { } };

class tree

{ protected:

struct node

{ treeable * data;

node * left, * right;

node(treeable * d): data(d), left(NULL), right(NULL) { } };

node * root;

public:

tree(void): root(NULL) { }

void add(treeable * d);

treeable * find(string k);

void NonRecursivePrintAll(void);

friend class TreeEnumerator; };

void tree::add(treeable * d)

{ string k = d->key;

node * prev = NULL;

node * curr = root;

while (curr!=NULL)

{ prev=curr;

if (k<curr->data->key)

curr=curr->left;

else

curr=curr->right; }

curr = new node(d);

if (prev==NULL)

root=curr;

else if (k<prev->data->key)

prev->left=curr;

else

prev->right=curr; }

treeable * tree::find(string k)

{ node * curr = root;

while (curr!=NULL)

{ if (curr->data->key==k)

return curr->data;

else if (k<curr->data->key)

curr=curr->left;

else

curr=curr->right; }

return NULL; }

class TreeEnumerator

{ protected:

enum position { alpha, beta, gamma };

struct StackFrame

{ position wherefrom;

tree::node * currentnode; };

StackFrame stack[100];

int stacktop;

public:

TreeEnumerator(tree t);

treeable * GetNext(void); };

TreeEnumerator::TreeEnumerator(tree t)

{ stacktop = 0;

stack[stacktop].wherefrom = alpha;

stack[stacktop].currentnode = t.root; }

treeable * TreeEnumerator::GetNext(void)

{ while (1)

{ if (stacktop<0)

return NULL;

StackFrame & task = stack[stacktop];

switch (task.wherefrom)

{

case alpha:

{ if (task.currentnode == NULL)

{ stacktop -= 1;

continue; }

task.wherefrom = beta;

stacktop+=1;

StackFrame & newtask = stack[stacktop];

newtask.wherefrom = alpha;

newtask.currentnode = task.currentnode->left;

continue; }

case beta:

{ treeable * value = task.currentnode->data;

task.wherefrom = gamma;

stacktop+=1;

StackFrame & newtask = stack[stacktop];

newtask.wherefrom = alpha;

newtask.currentnode = task.currentnode->right;

return value; }

case gamma:

{ stacktop -= 1;

continue; } } } }

void main(void)

{ tree T;

cout << "? ";

while (1)

{ string s;

cin >> s;

if (s=="end") break;

T.add(new treeable(s)); }

TreeEnumerator getter(T);

while (1)

{ treeable * item = getter.GetNext();

if (item==NULL) break;

cout << " " << item->key; }

cout << "\n"; }

// Multiple Enumerators Acheiving the Otherwise Impossible

void ReadTree(string prompt, tree & T)

{ cout << prompt << "\n: ";

while (1)

{ string s;

cin >> s;

if (s=="end") break;

T.add(new treeable(s)); } }

void main(void)

{ tree T1, T2;

ReadTree("Enter strings for first tree", T1);

ReadTree("Enter strings for second tree", T2);

TreeEnumerator getter1(T1);

TreeEnumerator getter2(T2);

while (1)

{ treeable * item1 = getter1.GetNext();

treeable * item2 = getter2.GetNext();

if (item1==NULL && item2==NULL)

{ cout << "Both trees ended together. They are the SAME\n";

break; }

if (item1==NULL || item2==NULL)

{ cout << "One tree ended, other still going. They are DIFFERENT\n";

break; }

cout << "tree1: '" << item1->key << "', tree2: '" << item2->key << "'\n";

if (item1->key != item2->key)

{ cout << "Trees produced non-matching items. They are DIFFERENT\n";

break; }

cout << "OK so far\n"; } }

$ a.out

Enter strings for first tree

: one two three four five six seven eight nine ten eleven twelve end

Enter strings for second tree

: twelve eleven ten nine eight seven six five four three two one end

tree1: 'eight', tree2: 'eight'

OK so far

tree1: 'eleven', tree2: 'eleven'

OK so far

tree1: 'five', tree2: 'five'

OK so far

tree1: 'four', tree2: 'four'

OK so far

tree1: 'nine', tree2: 'nine'

OK so far

tree1: 'one', tree2: 'one'

OK so far

tree1: 'seven', tree2: 'seven'

OK so far

tree1: 'six', tree2: 'six'

OK so far

tree1: 'ten', tree2: 'ten'

OK so far

tree1: 'three', tree2: 'three'

OK so far

tree1: 'twelve', tree2: 'twelve'

OK so far

tree1: 'two', tree2: 'two'

OK so far

Both trees ended together. They are the SAME