Supply the missing code. Complete the program together with a printout of a run of the program. Use the C++ code given below build a binary tree. Using the non recursive algorithms to write the code to visit the tree in preorder, and levelorder. You should implement the stack using a large array, and the queue using a linked list. Use the code given as a start. The input should be 7, 3, 10, 2, 5, 8, 11, 4, -1.

#include #include using namespace std; struct tnode { int item; tnode *left, *right; tnode(int Item, tnode *Left, tnode *Right) {item = Item; left = Left; right = Right;} }; void tprint(tnode *tptr) { if ( tptr ) { tprint( tptr->left ); cout << tptr->item << ; tprint( tptr->right ); } } struct snode { int counter; tnode * node; snode(int c = 0, tnode * n = 0) {counter = c; node = n;}

}; class stack { private: enum { STACK_SIZE = 128 }; snode _stack[STACK_SIZE]; int _top; public: stack() { _top = 0; } void push( snode ); snode pop(); snode top() { assert( _top > 0 ); return _stack[_top - 1]; } bool is_empty() { return !_top; } }; void stack::push( snode sval ) { assert( _top < STACK_SIZE ); _stack[_top++] = sval; } snode stack::pop() { assert( _top > 0 ); return _stack[--_top]; } tnode * buildTree(){ tnode *tree = 0, *prev, *curr, *trptr; int ival; cout << "> "; cin >> ival; while ( ival > 0 ) { tnode *tptr = new tnode(ival, 0, 0); if ( !tree ) { tree = tptr;

} else { curr = tree; while ( curr ) { prev = curr; if (ival < curr->item) curr = curr->left; else curr = curr->right; } if (ival < prev->item) prev->left = tptr; else prev->right = tptr; } cout << "> "; cin >> ival; } return tree; } void visit(tnode * t){ cout << t->item << " "; } int main() { tnode * tree = buildTree(); inorder(tree); cout << "---------------- "; levelorder(tree); }